Estoy trabajando en algunos ejemplos de clase en Python implementados dentro de ArcMap para calcular la distancia antipodal dentro de un polígono. Esto es bastante rutinario para los polígonos convexos, sin embargo, para los polígonos cóncavos, deseo excluir las soluciones (formadas por un rayo que conecta los puntos de límite), que no están completamente dentro del polígono y no en el límite del polígono o que no lo intersecan. ¿He interpretado mal la definición o esta bestia tiene otro nombre?
Considera estos dos polígonos
pnts = [[0,0], [0,1], [1,4], [3,5], [5,4], [4,1], [0,0]] # un circuito cerrado convexo
pnts = [[0,0], [2,1], [1,4], [3,5], [5,4], [4,1], [0,0]] # un circuito cerrado polígono cóncavo
En mi interpretación, el punto 0,0 no debería tener una distancia antipodal asociada a él, ya que el vector que lo conecta con los otros puntos se cruza por sí mismo con el polígono o está en el límite del polígono.
Si alguien tiene alguna aclaración sobre la definición o las posibles soluciones, se lo agradecería.
Se adjunta una representación visual del polígono convexo y las líneas deseadas (que se muestran en rojo) (solo se muestran vectores de ejemplo desde el punto 0).
En el ejemplo convexo, el primer punto no tiene vectores antipodales, sin embargo, el segundo punto sí.
EDITAR He tenido algo de éxito al buscar usando "búsqueda de polígono" o "diámetro de polígono" en la web, sospecho que esto es lo que busco.
fuente
Respuestas:
Si estuviera escribiendo un algoritmo, simplemente verificaría si una línea entre dos vértices en el polígono se cruza con cualquier línea que forme uno de los bordes. Aquí está mi pseudocódigo:
almacenar todas las distancias validas con referencia a los vértices en 1.
haga lo que quiera con los resultados, escriba nuevas líneas, almacene la más larga para cada polígono ...
Ahora, no estoy seguro de si esto es lo que buscas, pero ciertamente puedes hacer lo anterior en ArcPy.
EDITAR: Código para el paso 2.2:
Si h está entre 0 y 1, las líneas se cruzan, de lo contrario no lo hacen. Si F * P es cero, por supuesto, no puede hacer el cálculo, pero en este caso las líneas son paralelas y, por lo tanto, solo se cruzan en los casos obvios. Si h es 1, entonces las líneas terminan en el mismo punto. ¡Maneja esto como quieras! (Diría que se cruzan, me hace más fácil).
Otro ejemplo para el paso 2.2 desde aquí: http://en.wikipedia.org/wiki/Line-line_intersection
Primero verifique que el denominador no sea igual a 0, lo que significa que las líneas son paralelas.
Luego verifique que las coordenadas que se encuentran arriba no estén fuera del cuadro delimitador de cualquiera de las líneas.
Más lectura: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf
fuente
Estaría tentado a hacer esto usando ángeles, casi como una línea de visión. Si mientras itera los vértices en la forma, los ángulos entre el vértice de origen y el vértice de destino continúan en una dirección consistente, todos los puntos son candidatos para el antípoda. Si un ángulo cambia de dirección, ese punto está oculto u oculta el punto anterior. Si está oculto por el punto anterior, se debe omitir el punto. Si oculta el punto anterior, los puntos anteriores deben eliminarse de la lista de candidatos.
No estoy seguro de qué hacer con los casos en que el origen y otros dos vértices caen en la misma línea. En ese caso, el ángulo sería el mismo. Si tuviera un polígono con agujeros, podría encontrar el ángulo mínimo / máximo de cada agujero y eliminar cualquier punto candidato que se encuentre dentro de ese rango.
La principal ventaja de este enfoque sería que no tiene que probar la intersección de línea entre el segmento de línea actual y todos los bordes del polígono.
Esto funciona ... creo. He actualizado el pseudocódigo anterior y el python para que sea más fácil de leer.
Esta debería ser la última edición. El siguiente ejemplo debería encontrar el mayor anitpole para una geometría dada. Modifiqué el script para que use Puntos y Vectores, para intentar que sea más fácil de leer.
fuente
Quizás considere triangular el conjunto de datos. ¿Qué líneas son comunes a los bordes de los polígonos serían fáciles de establecer y las restantes podrían compararse para encontrar la más larga? La pregunta entonces es qué algoritmo de triangulación necesita.
Es solo una corazonada, pero sospecho (irónicamente) que la triangulación de "menor calidad" que uno puede crear debe contener la línea que está buscando, por ejemplo, la figura 1 en https://www.google.co.uk/url?sa=t&rct= j & q = & esrc = s & source = web & cd = 6 & ved = 0CEoQFjAF & url = http% 3A% 2F% 2Fhrcak.srce.hr% 2Ffile% 2F69457 & ei = alIcUsb6HsLnswbfnYHoDw & usg = QvHFHFHHFHFQFVCFQCFQAFQQFVC
fuente