¿Cómo ordenar puntos en un polígono de Google Maps para que las líneas no se crucen?

Question

Estoy tratando de hacer un mapa donde un usuario pueda delinear cualquier forma que desee. Pero me estoy encontrando con un problema donde los usuarios pueden seleccionar puntos que harán que las líneas del polígono se crucen y excluyan áreas que me gustaría incluir.

Para ver lo que estoy hablando de ir a this page y seguir los siguientes pasos:

1. clic 4 puntos para hacer las 4 esquinas de una caja
2. clic en cada uno de entre el 4 puntos que acaba de hacer a más definir el Perímetro de la caja
3. clic hecho

usted sh Ould ver algo como esto:

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

¿Hay una manera fácil de resolver este problema, o estoy básicamente tratando con una situación tipo "Traveling Salesman" aquí? Toda la lógica está hecha en JavaScript, así que siéntete libre de "ver la fuente" si quieres ver cómo estoy haciendo esto.

Answer 1

Un casco convexo puede incluir áreas que el usuario desea excluir. Aquí hay otra forma de abordar esto que podría dar resultados más satisfactorios. Verifique cada línea para ver cuáles cruzan (hay muchas maneras de hacerlo). A continuación, invierta la subsecuencia de puntos que aparecen entre esas dos líneas.

Por ejemplo, supongamos que le dan puntos A-B-C-D-E-F-A, donde se cruzan B-C y E-F. Puede desentrañarlos invirtiendo la subsecuencia C..E que resulta en A-B-E-D-C-F-A.

Es algo que intentar de todos modos.

Answer 2

Resolví un problema similar en el pasado y me encontré con el problema que Jeffrey mencionó sobre no saber exactamente qué forma está esperando el usuario. Terminé resolviendo ese problema solicitando al usuario que seleccionara los dos puntos en los que deseaba que estuviera el nuevo punto. Requiere más clics (3 contra 1), pero el usuario tiene el control total sobre la forma que desea. Todavía podría tener el código que usé en alguna parte (fue para Google Maps) si está interesado.

Answer 3

No es un casco convexo.

Imagine si tiene una parada en "Linfield Oaks" cerca de donde se cruzan esas dos líneas. Un casco convexo saltaría esto y dibujaría una línea recta entre "internacional" y "82"

Lo que está tratando de hacer es determinar si cada punto nuevo está dentro del polígono formado por los puntos existentes, si es entonces usted necesita romper el lado del polígono más cercano e insertar el nuevo punto en ese borde. Ver http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm para el punto en las pruebas de polígono.