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

Question

Estoy trabajando en algunos de los ejemplos de la clase en Python implementado dentro de ArcMap para calcular el antipodal a distancia dentro de un polígono. Esto es algo de rutina para los polígonos convexos, sin embargo, para los polígonos cóncavos, yo quiero excluir a las soluciones de (formado por un rayo conexión de los puntos de límite), que no están completamente dentro del polígono y no en el polígono límite o una intersección. He interpretado la definición de mal o es que esta bestia ir por otro nombre.

Considerar 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 debe tener un antipodal distancia asociada con ella desde el vector que conecta con el resto de los puntos es auto cruza el polígono o está en el polígono límite.

Si alguien tiene alguna aclaración sobre la definición de la o las posibles soluciones, te lo agradecería.

Una representación visual del polígono convexo y las líneas deseadas (en rojo) es cerrado (por ejemplo los vectores desde el punto 0 sólo se muestran).

En el convexo ejemplo, el primer punto no tiene antipodal vectores, sin embargo, el segundo punto.

EDITAR He tenido algo de éxito de la búsqueda usando "polígono de búsqueda" o "polígono de diámetro" en la web, me imagino que esto es lo que yo busco.

Answer 1

Si yo fuera a escribir un algoritmo solo quiero comprobar si una línea entre los dos vértices de la poligonal se cruza con cualquier línea que constituye uno de los bordes. Aquí está mi pseudo código:

1. Identificar todos los vértices, almacenar en una lista
2. Identificar todos los bordes, almacenar en una lista (como los pares de vértices de 1, tal vez)
3. para cada vértice, obtener la distancia a todos los demás vértices, excepto:
   1. excluir a los vecinos de vértices (aquellos que comparten una vinculación con este vértice en 2, tal vez)
   2. excluir cualquier línea que se cruza con cualquier línea 2. el uso de algo de aquí.

4. almacenar todos los valide distancias con referencia a los vértices en 1.

5. hacer lo que quiera con los resultados, escribir nuevas líneas de salida, guardar el más largo para cada polígono ...

Ahora, no estoy seguro si esto es lo que está después, pero que sin duda puede hacer lo anterior en ArcPy.

EDIT: Código del 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. Si F*P es cero, por supuesto, usted no puede hacer el cálculo, pero en este caso las rectas son paralelas y por lo tanto sólo se cruzan en los casos obvios. Si h es 1, luego las líneas terminan en el mismo punto. Manejar esto como usted! (Yo diría que se cruzan, se me hace más fácil.)

Otro ejemplo para el paso 2.2 desde aquí: http://en.wikipedia.org/wiki/Line-line_intersection

Compruebe primero que el denominador no sea igual a 0, lo que significa que las líneas son paralelas.

A continuación, compruebe que las coordenadas se encuentra por encima no están fuera del cuadro delimitador de la línea.

Leer más: http://compgeom.cs.uiuc.edu/~jeffe/docencia/373/notas/x06-sweepline.pdf

Answer 2

Yo estaría tentado a hacer esto utilizando los ángeles, casi como la línea de visión. Si durante la iteración de los vértices en la forma de los ángulos entre el vértice origen y destino vértice continuar en una dirección consistente, todos los puntos son candidatos para el antipodal. Si un ángulo cambia de dirección, entonces ese punto se oculta o se esconde en el punto anterior. Si está oculto por el punto anterior, el punto debe ser omitido. Si se oculta el punto anterior, el anterior punto(s) necesita ser removido de la lista de candidatos.

1. Crear una lista PolygonCandidates
2. Para cada vértice (punto k)
   1. Crear nueva lista de candidatos (Punto, Ángulo)
   2. Añadir el vértice actual a la lista de candidatos (punto k)
   3. Recorrer las agujas del reloj alrededor del polígono, para cada vértice (punto i)
      1. Si el ángulo del punto actual (desde el punto de k para el punto i) continúa en sentido horario 1.añadir el punto
      2. Si el ángulo de la corriente de punto continúa en dirección contra reloj
      3. Si las dos anteriores candidato puntos, y con el actual punto de formar un girar a la derecha.
      4. Eliminar el último punto de la lista, hasta que el ángulo actual y el último de la lista de candidatos ángulo en sentido antihorario.
      5. Agregar el punto actual a la lista de candidatos
   4. Agregar todos, pero los dos primeros, y el último candidato apunta a un PolygonCandidates lista
3. Encontrar el punto más alejado en la PolygonCandidates lista.

No estoy seguro de qué hacer con los casos donde el origen y el de los otros dos vértices todos caen a lo largo de la misma línea. En ese caso, el ángulo sería el mismo. Si usted tuvo un polígono con agujeros, usted podría encontrar el min/max ángulo de cada agujero, y eliminar cualquier candidato punto que se encuentra dentro de ese rango.

La principal ventaja de este enfoque sería que usted no tiene que probar la línea de intersección entre el segmento de línea actual y todo el polígono bordes.

Esto funciona...creo. He actualizado el pseudo código de arriba y el de python con el fin de hacer más fácil la lectura.

---

Esta debe ser la última edición. El ejemplo de abajo, deben encontrar la mayor anitpole para una determinada geometría. He modificado la receta para que se utiliza los Puntos y Vectores, para intentar hacer más fácil la lectura.

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

Answer 3

Tal vez considerar la triangulación del conjunto de datos. Las líneas a las que son comunes a los bordes de los polígonos sería fácil establecer y el resto podría ser comparado a encontrar la más larga? La pregunta entonces es ¿qué algoritmo de triangulación que usted necesita.

Es sólo una corazonada, pero sospecho que (irónicamente) el "menor calidad" de la triangulación se puede crear debe contener la línea que usted 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=AFQjCNHIaykVRBAvv9hlaFJIBlfPLGHKtQ