Distance antipodal (ou extraction de polygone ou diamètre de polygone) pour les polygones concaves

Je travaille sur quelques exemples de classe en Python implémentés dans ArcMap pour calculer la distance antipodale dans un polygone. Ceci est assez courant pour les polygones convexes, cependant, pour les polygones concaves, je souhaite exclure les solutions (formées par un rayon reliant les points limites), qui ne sont pas complètement à l'intérieur du polygone et pas sur la limite du polygone ou qui le coupent. Ai-je mal interprété la définition ou cette bête porte-t-elle un autre nom?

Considérez ces deux polygones

pnts = [[0,0], [0,1], [1,4], [3,5], [5,4], [4,1], [0,0]] # a boucle fermée convexe

pnts = [[0,0], [2,1], [1,4], [3,5], [5,4], [4,1], [0,0]] # a boucle fermée polygone concave

Selon mon interprétation, le point 0,0 ne devrait pas être associé à une distance antipodale, car le vecteur le reliant aux autres points est lui-même coupant le polygone ou se trouve sur la frontière du polygone.

Si quelqu'un a des éclaircissements sur la définition ou les solutions potentielles, je l'apprécierais.

Un visuel du polygone convexe et des lignes souhaitées (montrées en rouge) est inclus (les exemples de vecteurs du point 0 ne sont montrés que).

Dans l'exemple convexe, le premier point n'a pas de vecteurs antipodaux, cependant, le deuxième en a.

EDIT J'ai réussi à chercher en utilisant "polygon fetch" ou "polygon diamètre" sur le web, je soupçonne que c'est ce que je recherche.

Si j'écrivais un algorithme, je vérifierais simplement si une ligne entre deux sommets du polygone coupe une ligne qui forme l'un des bords. Voici mon pseudo code:

1. Identifier tous les sommets, stocker dans une liste
2. Identifiez toutes les arêtes, stockez-les dans une liste (comme des paires de sommets à partir de 1, peut-être)
3. pour chaque sommet, obtenez la distance à tous les autres sommets, sauf:
   1. exclure les sommets voisins (ceux qui partagent un appariement avec ce sommet en 2, peut-être)
   2. exclure toute ligne qui coupe n'importe quelle ligne dans 2. en utilisant quelque chose d' ici .

4. mémoriser toutes les distances valides en référence aux sommets en 1.

5. faites ce que vous voulez avec les résultats, écrivez de nouvelles lignes, stockez la plus longue pour chaque polygone ...

Maintenant, je ne sais pas si c'est ce que vous recherchez, mais vous pouvez certainement faire ce qui précède dans ArcPy.

EDIT: Code pour l'étape 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 compris entre 0 et 1, les lignes se coupent, sinon elles ne le sont pas. Si F * P est nul, vous ne pouvez bien sûr pas faire le calcul, mais dans ce cas, les lignes sont parallèles et ne se coupent donc que dans les cas évidents. Si h est 1, les lignes se terminent au même point. Manipulez cela comme vous voulez! (Je dirais qu'ils se croisent, ça me facilite les choses.)

Un autre exemple pour l'étape 2.2 à partir d'ici: http://en.wikipedia.org/wiki/Line-line_intersection

Vérifiez d'abord que le dénominateur n'est pas égal à 0, ce qui signifie que les lignes sont parallèles.

Vérifiez ensuite que les coordonnées ci-dessus ne se trouvent pas en dehors du cadre de délimitation de l'une ou l'autre ligne.

Plus de lecture: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf

Je serais tenté de le faire en utilisant des anges, presque comme une ligne de vue. Si, tout en itérant les sommets de la forme, les angles entre le sommet d'origine et le sommet de destination continuent dans une direction cohérente, tous les points sont candidats à l'antipode. Si un angle change de direction, ce point est masqué ou masque le point précédent. S'il est masqué par le point précédent, le point doit être ignoré. S'il masque le point précédent, le ou les points précédents doivent être supprimés de la liste des candidats.

1. Créer une liste PolygonCandidates
2. Pour chaque sommet (point k)
   1. Créer une nouvelle liste pour les candidats (point, angle)
   2. Ajouter le sommet actuel à la liste des candidats (point k)
   3. Itérer dans le sens horaire autour du polygone, pour chaque sommet restant (point i)
      1. Si l'angle par rapport au point actuel (du point k au point i) continue dans le sens des aiguilles d'une montre 1. ajoutez le point
      2. Si l'angle par rapport au point actuel continue dans le sens antihoraire
      3. Si les deux points candidats précédents, plus le point actuel forment un virage à droite.
      4. Supprimez le dernier point de la liste jusqu'à ce que l'angle actuel et le dernier angle de la liste candidate soient dans le sens antihoraire.
      5. Ajouter le point actuel à la liste des candidats
   4. Ajouter tous les points, sauf les deux premiers et les derniers candidats, à une liste PolygonCandidates
3. Recherchez le point le plus éloigné dans la liste PolygonCandidates.

Je ne sais pas quoi faire avec les cas où l'origine et deux autres sommets tombent tous sur la même ligne. Dans ce cas, l'angle serait le même. Si vous aviez un polygone avec des trous, vous pouvez trouver l'angle min / max de chaque trou et supprimer tout point candidat se trouvant dans cette plage.

Le principal avantage de cette approche est que vous n'avez pas à tester l'intersection de lignes entre le segment de ligne actuel et toutes les arêtes du polygone.

Cela fonctionne ... je pense. J'ai mis à jour le pseudo code ci-dessus et le python afin de le rendre plus facile à lire.

Ce devrait être la dernière modification. L'exemple ci-dessous devrait trouver le plus grand anitpole pour une géométrie donnée. J'ai modifié le script pour qu'il utilise des points et des vecteurs, pour essayer de le rendre plus facile à lire.

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

Pensez peut-être à trianguler l'ensemble de données. Quelles lignes sont communes aux polygones, les arêtes seraient faciles à établir et les autres pourraient être comparées pour trouver les plus longues? La question est alors de savoir de quel algorithme de triangulation vous avez besoin.

Ce n'est qu'une intuition mais je soupçonne (ironiquement) que la triangulation de "qualité la plus basse" que l'on puisse créer doit contenir la ligne que vous recherchez, par exemple Fig 1 dans 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 = AFQjCJVKVF