Distância antipodal (ou busca de polígono ou diâmetro de polígono) para polígonos côncavos

Estou trabalhando em alguns exemplos de classe em Python implementados no ArcMap para calcular a distância antipodal dentro de um polígono. Isso é bastante rotineiro para polígonos convexos, no entanto, para polígonos côncavos, desejo excluir soluções (formadas por um raio que conecta os pontos de contorno), que não estão completamente dentro do polígono e não no limite ou na interseção do polígono. Eu interpretei a definição errada ou esse animal tem outro nome?

Considere estes dois polígonos

pnts = [[0,0], [0,1], [1,4], [3,5], [5,4], [4,1], [0,0]] # um loop fechado convexo

pnts = [[0,0], [2,1], [1,4], [3,5], [5,4], [4,1], [0,0]] # um loop fechado polígono côncavo

Na minha interpretação, o ponto 0,0 não deve ter uma distância antipodal associada a ele, já que o vetor que o conecta aos outros pontos é auto-interceptando o polígono ou está no limite do polígono.

Se alguém tiver algum esclarecimento sobre a definição ou possíveis soluções, eu agradeceria.

Um visual do polígono convexo e das linhas desejadas (mostradas em vermelho) é anexado (vetores de exemplo do ponto 0 são mostrados apenas).

No exemplo convexo, o primeiro ponto não possui vetores antipodais; no entanto, o segundo ponto.

EDIT: Eu tive algum sucesso em pesquisar usando "busca de polígono" ou "diâmetro de polígono" na Web, suspeito que é isso que estou procurando.

Se eu estivesse escrevendo um algoritmo, simplesmente verificaria se uma linha entre dois vértices no polígono cruza qualquer linha que forma uma das arestas. Aqui está o meu pseudo-código:

1. Identifique todos os vértices, armazene em uma lista
2. Identifique todas as arestas e armazene em uma lista (como pares de vértices de 1, talvez)
3. para cada vértice, obtenha a distância de todos os outros vértices, exceto:
   1. excluir vértices vizinhos (aqueles que compartilham um pareamento com esse vértice em 2, talvez)
   2. exclua qualquer linha que cruze qualquer linha 2. usando algo daqui .

4. armazene todas as distâncias do valide com referência aos vértices em 1.

5. faça o que quiser com os resultados, escreva novas linhas, armazene a mais longa para cada polígono ...

Agora, não tenho certeza se é isso que você procura, mas você certamente pode fazer o acima no ArcPy.

Edição: código para o passo 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 )

Se h estiver entre 0 e 1, as linhas se cruzam, caso contrário não. Se F * P é zero, é claro que você não pode fazer o cálculo, mas neste caso as linhas são paralelas e, portanto, só se cruzam nos casos óbvios. Se h for 1, as linhas terminam no mesmo ponto. Lide com isso como quiser! (Eu diria que eles se cruzam, isso me facilita).

Outro exemplo para a etapa 2.2 daqui: http://en.wikipedia.org/wiki/Line-line_intersection

Primeiro verifique se o denominador não é igual a 0, o que significa que as linhas são paralelas.

Em seguida, verifique se as coordenadas encontradas acima não estão fora da caixa delimitadora das duas linhas.

Mais informações: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf

Eu ficaria tentado a fazer isso usando anjos, quase como uma linha de visão. Se ao iterar os vértices na forma, os ângulos entre o vértice de origem e o vértice de destino continuarem em uma direção consistente, todos os pontos serão candidatos ao antípoda. Se um ângulo muda de direção, esse ponto fica oculto ou oculta o ponto anterior. Se estiver oculto pelo ponto anterior, o ponto precisará ser ignorado. Se ocultar o ponto anterior, é necessário remover o (s) ponto (s) anterior (s) da lista de candidatos.

1. Criar uma lista PolygonCandidates
2. Para cada vértice (ponto k)
   1. Criar nova lista de candidatos (Ponto, Ângulo)
   2. Adicionar o vértice atual à lista de candidatos (ponto k)
   3. Iterar no sentido horário ao redor do polígono, para cada vértice restante (ponto i)
      1. Se o ângulo do ponto atual (do ponto k ao ponto i) continuar no sentido horário 1.adicione o ponto
      2. Se o ângulo para o ponto atual continuar no sentido anti-horário
      3. Se os dois candidatos anteriores apontarem, mais o ponto atual, formará uma curva à direita.
      4. Remova o último ponto da lista até que o ângulo atual e o último ângulo da lista de candidatos estejam no sentido anti-horário.
      5. Adicione o ponto atual à lista de candidatos
   4. Adicione todos, exceto os dois primeiros e o último candidato, a uma lista de PolygonCandidates
3. Encontre o ponto mais distante da lista PolygonCandidates.

Não sei o que fazer com casos em que a origem e dois outros vértices caem na mesma linha. Nesse caso, o ângulo seria o mesmo. Se você tivesse um polígono com orifícios, poderia encontrar o ângulo mínimo / máximo de cada orifício e remover qualquer ponto candidato que estivesse dentro desse intervalo.

A principal vantagem dessa abordagem seria que você não precisa testar a interseção de linha entre o segmento de linha atual e todas as arestas do polígono.

Isso funciona ... eu acho. Atualizei o pseudo-código acima e o python para facilitar a leitura.

Essa deve ser a última edição. O exemplo abaixo deve encontrar o maior anitólio para uma determinada geometria. Alterei o script para usar pontos e vetores, para tentar facilitar a leitura.

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

Talvez considere triangular o conjunto de dados. Quais linhas são comuns às arestas dos polígonos seriam fáceis de estabelecer e as demais poderiam ser comparadas para encontrar as mais longas? A questão, então, é qual algoritmo de triangulação você precisa.

É apenas um palpite, mas suspeito (ironicamente) que a triangulação de "menor qualidade" que se pode criar deve conter a linha que você está procurando, por exemplo, a Figura 1 em 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