Comment trier des points dans un polygone Google Maps afin que les lignes ne se croisent pas?

Question

J'essaye de faire une carte où un utilisateur peut décrire n'importe quelle forme qu'ils aimeraient. Mais je suis confronté à un problème où les utilisateurs peuvent sélectionner des points qui feront croiser les lignes du polygone et exclure la zone que je voudrais inclure.

Pour voir ce que je parle aller à this page et prendre les mesures suivantes:

1. cliquez sur 4 points à faire les 4 coins d'une boîte
2. cliquez entre chacun des 4 points que vous venez de faire à plus définir la perimter de la boîte
3. cliquez
fait

vous Sh ould voir quelque chose comme ceci:

alt text http://polygon.abemiester.com/1.bmp

est-il un moyen facile de résoudre ce problème, ou suis-je affaire au fond une situation de type « Traveling Salesman » ici? Toute la logique est faite en javascript alors n'hésitez pas à "voir la source" si vous voulez voir comment je le fais.

Answer 1

Une coque convexe peut inclure des zones que l'utilisateur souhaite exclure. Voici une autre façon d'aborder cela qui pourrait donner des résultats plus satisfaisants. Vérifiez chaque ligne pour voir lesquelles se croisent (il y a beaucoup de façons de le faire). Puis inversez la sous-séquence des points qui apparaissent entre ces deux lignes. Par exemple, supposons que l'on vous attribue les points A-B-C-D-E-F-A, où B-C et E-F se croisent. Vous pouvez les décroiser en inversant la sous-séquence C..E résultant en A-B-E-D-C-F-A.

C'est quelque chose à essayer quand même.

Answer 2

J'ai résolu un problème similaire dans le passé et j'ai rencontré le problème que Jeffrey a mentionné à propos de ne pas savoir exactement quelle forme attend l'utilisateur. J'ai fini par résoudre ce problème en demandant à l'utilisateur de sélectionner les deux points entre lesquels il voulait que le nouveau point soit entre. Il nécessite plus de clics (3 contre 1), mais l'utilisateur contrôle entièrement la forme qu'il souhaite. Je pourrais toujours avoir le code que j'ai utilisé quelque part (c'était pour Google Maps) si vous êtes intéressé.

Answer 3

Ce n'est pas une coque convexe. Imaginez si vous avez fait un arrêt à "Linfield Oaks" près de l'endroit où ces deux lignes se croisent. Une coque convexe sauterait ceci et tracerait une ligne droite entre "international" et "82"

Ce que vous essayez de faire est de déterminer si chaque nouveau point est à l'intérieur du polygone formé par les points existants - si c'est alors besoin de casser le côté polygone le plus proche et insérez le nouveau point dans ce bord. Voir http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm pour le point dans les tests polygonaux.