Come ordinare i punti in un poligono di Google Maps in modo che le linee non si incrocino?

Question

Sto provando a creare una mappa in cui un utente può delineare qualsiasi forma che vorrebbero. Ma sto incontrando un problema in cui gli utenti possono selezionare punti che faranno incrociare le linee del poligono ed escludere quelle che vorrei includere.

per vedere che cosa sto parlando andare a this page e adottare le seguenti misure:

1. click 4 punti per fare i 4 angoli di una scatola
2. click tra ciascuna delle 4 punti che hai appena fatto un ulteriore definire il Perimetro della scatola
3. click fatto

È SH ould vedere qualcosa del genere:

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

C'è un modo semplice per risolvere questo problema, o sto fondamentalmente a che fare con un tipo di situazione "Traveling Salesman" qui? Tutta la logica è fatta in javascript quindi sentiti libero di "vedere la fonte" se vuoi vedere come sto facendo questo.

Answer 1

Uno scafo convesso può includere aree che l'utente desidera escludere. Ecco un altro modo di affrontare questo che potrebbe dare risultati più soddisfacenti. Controlla ogni riga per vedere quali attraversano (ci sono molti modi per farlo). Quindi inverti la sottosequenza dei punti che appaiono tra quelle due linee.

Ad esempio, si supponga di ricevere i punti A-B-C-D-E-F-A, dove incrociano B-C ed E-F. È possibile annullarli invertendo la sottosequenza C..E risultante in A-B-E-D-C-F-A.

È comunque qualcosa da provare.

Answer 2

ho risolto un problema simile in passato e corse in questione che Jeffrey detto di non sapere esattamente che cosa la forma che l'utente si aspetta. Ho finito per risolvere quel problema richiedendo all'utente di selezionare i due punti in cui volevano che il nuovo punto fosse in mezzo. Richiede più clic (3 contro 1), ma l'utente ha completamente il controllo sulla forma che desidera. Potrei avere ancora il codice che ho usato da qualche parte (era per Google Maps) se sei interessato.

Answer 3

Non è uno scafo convesso.

Immagina se tu avessi una sosta al "Linfield Oaks" vicino a dove queste due linee si incrociano. Uno scafo convesso salta questo e traccia una linea retta tra "internazionale" e "82"

Quello che stai cercando di fare è determinare se ogni nuovo punto è all'interno del poligono formato dai punti esistenti - se è allora tu è necessario rompere il lato poligono più vicino e inserire il nuovo punto in quel bordo. Vedere http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm per il punto nei test dei poligoni.