Distancia antipodal (o búsqueda de polígono o diámetro de polígono) para polígonos cóncavos

8

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).

Ejemplo de distancia antipodal interior

En el ejemplo convexo, el primer punto no tiene vectores antipodales, sin embargo, el segundo punto sí.

Ejemplo antipodal cóncavo

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.

PolyGeo
fuente
1
Hola dan ¿Qué definición de "distancia antipodal" está utilizando? Una posibilidad sería el punto más alejado medido por el recorrido a lo largo del límite del polígono, pero eso no parece ser consistente con su descripción. Otra definición es un punto más alejado donde el viaje puede ocurrir en cualquier lugar dentro o fuera del polígono. Sin embargo, un tercero es el punto más alejado donde se permite viajar solo dentro del interior y el límite del polígono.
whuber
1
@whuber, estaba buscando una solución que solo viajara dentro del polígono, excluyendo los segmentos de línea que forman el límite del polígono. En el ejemplo convexo que di, no se permitiría el movimiento desde los puntos p0 a p1, o p0 a p5, ya que son parte del borde del polígono, sin embargo, lo serían p0 a p2, p3, p4. Por lo tanto, mi preocupación de que "antipodal" puede no ser el término correcto. Tenga en cuenta que solo me interesan los polígonos convexos de una sola parte sin agujeros en este momento. Si estoy atascado con segmentos de borde en la solución, siempre puedo eliminarlos más tarde.
1
Aquí hay un tema delicado, Dan: aunque tales segmentos pueden descartarse, sin embargo, le dicen cuál será el infimum de todas las distancias posibles (simplemente evitan que ese infimum se realice realmente). Las soluciones prácticas se mantendrían en el interior de esos segmentos pero permanecerían infinitamente cerca de ellos. Por lo tanto, para los polígonos convexos el algoritmo es simple: encuentra un vértice más alejado del punto de partida (puede haber muchos de ellos: imagina un semicírculo y comienza en el centro del círculo original).
whuber
1
Todavía no entiendo tu definición, Dan, porque no hay un "camino más largo" dentro de ningún polígono: puedes serpentear para hacer caminos arbitrariamente largos. Posiblemente lo que pretende es lo siguiente: defina la distancia entre los puntos P y Q en un polígono (conectado) para que sea la longitud mínima de todas las rutas desde P a Q que se encuentran completamente dentro del polígono. Entonces, una "antípoda" plausible para un polígono P compacto conectado sería cualquier punto Q a la distancia máxima de P. (Cuando P es un vértice de un polígono convexo, sus antípodas nuevamente son vértices a la distancia euclidiana máxima de P.)
whuber
2
El punto más alejado se caracteriza rigurosamente utilizando la definición "plausible" en mi comentario anterior. Tenga en cuenta que al encontrarlo, puede asumir que puede viajar a lo largo de los bordes. En su segunda figura, E es antipodal para A y B; A es antipodal para C, D y E; y D y A son antipodales a F. Usando la analogía de la canoa, donde el interior del polígono es un lago, un punto P es antipodal a tu punto de partida Q cuando estás en una carrera en canoa desde Q contra un oponente que intenta alcanzar P antes de llegar a algún punto P ', no tienen ventaja sobre ti sin importar dónde esté P'.
whuber

Respuestas:

4

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:

  1. Identificar todos los vértices, almacenar en una lista.
  2. Identifique todos los bordes, almacénelos en una lista (como pares de vértices de 1, tal vez)
  3. para cada vértice, obtenga la distancia a todos los demás vértices, excepto:
    1. excluir vértices vecinos (los que comparten un emparejamiento con este vértice en 2, tal vez)
    2. excluya cualquier línea que interseque cualquier línea en 2. usando algo de aquí .
  4. almacenar todas las distancias validas con referencia a los vértices en 1.

  5. 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:

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy ) 
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

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 ingrese la descripción de la imagen aquí

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

Alex Leith
fuente
El código en mi blog hace todo excepto 3.2 y devuelve el resultado al programa de llamadas para realizar más cálculos que funcionan bien para los polígonos convexos. Me gustaría algunas referencias si es posible y si el número de bobinado sería eficiente para determinar las intersecciones de línea o si debería ir a otra ruta.
2
Agregué un ejemplo del cálculo de intersección del artículo al que me vinculé. ¡Creo que no me preocuparía por la eficiencia hasta que fuera un problema! ¡Haga que algo funcione, luego arréglelo si no es lo suficientemente bueno!
Alex Leith
Gracias Alex, lo comprobaré ... la eficiencia no es un problema ya que este es solo un ejemplo para no ejecutarse en miles de polígonos
Aunque es difícil saber qué describe esta respuesta, parece ser una comprobación de si un polígono es convexo. Es particularmente confuso que parece usar "línea" en lugar de "segmento de línea". El código proporcionado no parece ser una verificación válida para la intersección de segmentos
whuber
Hola whuber, esto comprueba los segmentos de línea. El segundo ejemplo que agregué quizás lo aclara, ya que las matemáticas calculan el punto intersectino para líneas infinitas y luego deben verificar si ese punto de intersección está dentro del cuadro delimitador de una de las líneas. Como todas las matemáticas vectoriales, seguramente hay una biblioteca que hace esto, pero no es tan compleja, y creo que es necesario para lo que OP quiere hacer.
Alex Leith el
3

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.

  1. Crear una lista de PolygonCandidates
  2. Para cada vértice (punto k)
    1. Crear una nueva lista de candidatos (punto, ángulo)
    2. Agregar el vértice actual a la lista de candidatos (punto k)
    3. Iterar en sentido horario alrededor del polígono, para cada vértice restante (punto i)
      1. Si el ángulo al punto actual (del punto k al punto i) continúa en el sentido de las agujas del reloj 1.agregue el punto
      2. Si el ángulo del punto actual continúa en sentido antihorario
      3. Si los dos puntos candidatos anteriores, más el punto actual, forman un giro a la derecha.
      4. Elimine el último punto de la lista hasta que el ángulo actual y el último ángulo de la lista de candidatos estén en sentido antihorario.
      5. Agregar el punto actual a la lista de candidatos
    4. Agregue todos menos los dos primeros, y el último candidato apunta a una lista de PolygonCandidates
  3. Encuentre el punto más alejado en la lista de PolygonCandidates.

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.

import math
from collections import namedtuple


Point = namedtuple("Point", "position x y")
Vector = namedtuple("Vector", "source dest angle")

def isClockwise(angle1, angle2):
    diff = angle2 - angle1
    #print("         angle1:%s angle2:%s diff: %s" % (angle1, angle2, diff))
    if(diff > math.pi/2):
        diff = diff - math.pi/2
    elif (diff < -math.pi/2):
        diff = diff + math.pi/2
    #print("         diff:%s" % (diff)) 
    if(diff > 0):
        return False
    return True

def getAngle(origin, point):
    return math.atan2(point.y - origin.y, point.x-origin.x)

#returns a list of candidate vertcies.  This will include the first, second, and second to last points 
#the first and last points in the polygon must be the same
#k is the starting position, only vertices after this position will be evaluated
def getCandidates (k, polygon):

    origin = polygon[k]
    candidates = [Vector(k,k,0)]
    prevAngle = 0;
    currentAngle = 0;
    for i in range(k + 1, len(polygon) - 1):

        current = polygon[i]
        #print("vertex i:%s x:%s y:%s  " % (i, current.x, current.y))

        if(i == k+1):
            prevAngle = getAngle(origin, current)
            candidates.append(Vector(k,i,prevAngle))
        else:   
            currentAngle = getAngle(origin, current)
            #print("     prevAngle:%s currentAngle:%s  " % (prevAngle, currentAngle))
            if isClockwise(prevAngle, currentAngle):
                #print("     append")
                candidates.append(Vector(k,i,currentAngle))
                prevAngle = currentAngle
            else:
                #look at the angle between current, candidate-1 and candidate-2
                if(i >= 2):
                    lastCandinate = polygon[candidates[len(candidates) - 1].dest]
                    secondLastCandidate = polygon[candidates[len(candidates) - 2].dest]
                    isleft = ((lastCandinate.x - secondLastCandidate.x)*(current.y - secondLastCandidate.y) - (lastCandinate.y - secondLastCandidate.y)*(current.x - secondLastCandidate.x)) > 0
                    #print("     test for what side of polygon %s" % (isleft))
                    if(i-k >= 2 and not isleft):
                        while isClockwise(currentAngle, candidates[len(candidates) - 1].angle):
                            #print("     remove %s" % (len(candidates) - 1))
                            candidates.pop()
                        #print("     append (after remove)")
                        candidates.append(Vector(k,i,currentAngle))
                        prevAngle = currentAngle

        #for i in range(len(candidates)):
        #   print("candidate i:%s x:%s y:%s a:%s " % (candidates[i][0], candidates[i][1], candidates[i][2], candidates[i][3]))

    return candidates

def calcDistance(point1, point2):
    return math.sqrt(math.pow(point2.x - point1.x, 2) + math.pow(point2.y - point1.y, 2))

def findMaxDistance(polygon, candidates):
    #ignore the first 2 and last result
    maxDistance = 0
    maxVector = Vector(0,0,0);
    for i in range(len(candidates)):
        currentDistance = calcDistance(polygon[candidates[i].source], polygon[candidates[i].dest])
        if(currentDistance > maxDistance):
            maxDistance = currentDistance
            maxVector = candidates[i];
    if(maxDistance > 0):
        print ("The Antipodal distance is %s from %s to %s" % (maxDistance, polygon[candidates[i].source], polygon[candidates[i].dest]))
    else:
        print ("There is no Antipodal distance")

def getAntipodalDist(polygon):
    polygonCandidates = []
    for j in range(0, len(polygon) - 1):
        candidates = getCandidates(j, polygon)
        for i in range(2, len(candidates) - 1):
            #print("candidate i:%s->%s x:%s y:%s  " % (candidates[i].source, candidates[i].dest, candidates[i].x, candidates[i].y))
            polygonCandidates.append(candidates[i])

    for i in range(len(polygonCandidates)):
        print("candidate i:%s->%s" % (polygonCandidates[i].source, polygonCandidates[i].dest))
    findMaxDistance(polygon, polygonCandidates)


getAntipodalDist([Point(0,0,0),Point(1,-2,0),Point(2,-2,3),Point(3,2,2),Point(4,-1,1),Point(5,4,0),Point(6,0,0)])
getAntipodalDist([Point(0,0,0),Point(1,2,1),Point(2,1,4),Point(3,3,5),Point(4,5,4),Point(5,4,1),Point(6,0,0)])
getAntipodalDist([Point(0,0,0),Point(1,1,1),Point(2,2,1),Point(3,1,4),Point(4,3,5),Point(5,5,4),Point(6,4,1),Point(7,0,0)])
getAntipodalDist([Point(0,0,0),Point(1,-1,3),Point(2,1,4),Point(3,3,3),Point(4,2,0),Point(5,-2,-1),Point(6,0,0)])
travis
fuente
¿Este algoritmo realmente funciona? ¿Podría ilustrarlo con un ejemplo simple, como el hexágono ((0,0), (- 2,0), (- 2,3), (2,2), (- 1,1), (4 , 0), (0,0))? ¿Qué sucede cuando comienzas a (0,0)? ¿Y qué pretende hacer este algoritmo? Por ejemplo, no encuentra el segmento de línea más largo en el polígono (de longitud 1.2 * sqrt (26)).
whuber
Gracias por el comentario Travis, sin embargo, esto no funcionará en todos los casos (ver ejemplo de casco cóncavo), de isRightTurn (A, B, C) sería falso, y AC no sería un segmento candidato. Si B estuviera más al norte, posiblemente podría ser uno para un segmento AE, por lo que no me gustaría descartar el punto A por completo hasta que se hayan verificado todos los demás puntos.
@whuber, dada esa geometría, no veo cómo el segmento de línea más largo es 1.2 * sqrt (26). A menos que haya extrañado por completo de qué se trata esta pregunta. ¿No sería sqrt (2), ya sea desde (0,0) -> (- 1,1) o (-2,0) -> (- 1,1).
travis
1
@DanPatterson, puedo haber perdido lo que estás preguntando. Mi entendimiento fue: ¿cuál es la distancia más grande entre un vértice dado y cualquier otro vértice, que no interseque el límite del polígono? Actualicé mi script para encontrar la distancia máxima del polígono.
travis
Los polígonos convexos no parecen ser un problema dados los ejemplos simplistas que se pueden encontrar en la web y en los textos. El diámetro del polígono para los cascos cóncavos parece tener varias interpretaciones y buscar polígonos, ahora estoy empezando a darme cuenta de que es otra caldera de peces. En cualquier caso, lo que no busco es lo que busco. Mi preocupación es mi falta de definiciones claras y ejemplos con ejemplos del mundo real. Puedo cubrir los convexos, pero los cóncavos están resultando problemáticos y están más allá de mi experiencia matemática / computacional, como lo respaldan / destacan algunas de las sugerencias de Bill.
1

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

AnserGIS
fuente
Mi código en mi blog funciona efectivamente, es la terminología que necesito aclarar, así como qué hacer en el caso de un casco cóncavo.
Una triangulación manejará inherentemente un casco cóncavo (en la medida en que no creará ningún borde triangular que cruce un límite de polígono)
AnserGIS