Como posso eficientemente determinar se um polígono é convexo, não-convexa ou complexa?
https://stackoverflow.com/questions/471962
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
A partir da página de manual para XFillPolygon :
Se
shapeé Complexo , o caminho pode auto-intersecção. Note que pontos coincidentes contíguos no caminho não são tratados como auto-intersecção.Se
shapeé Convex , para cada par de pontos dentro do polígono, o segmento de linha conectando-os não cruza o caminho. Se for conhecida pelo cliente, especificando Convex pode melhorar o desempenho. Se você especificar Convex para um caminho que não é convexo, os gráficos resultados são indefinido.Se
shapeé não convexo , o caminho não se auto-intersecção, mas a forma não é totalmente convexo. Se for conhecida pelo cliente, especificando não convexo em vez de Complexo desempenho pode melhorar. Se você especificar não convexo para um caminho de auto-interseção, os resultados gráficos são indefinido.
Estou tendo problemas de desempenho com XFillPolygon preenchimento e, como a página do manual sugere, o primeiro passo que eu quero ter é a de especificar a forma correta do polígono. Atualmente, estou usando Complexo para estar no lado seguro.
Existe um algoritmo eficiente para determinar se um polígono (definida por uma série de coordenadas) é convexa, não-convexa ou complexa?
Solução
Stackoverflow não me deixa apagar uma resposta aceita, mas eu diria que confira Rory Daulton resposta .
Outras dicas
Você pode tornar as coisas muito mais fácil do que o algoritmo de embrulho ... que é uma resposta boa quando você tem um conjunto de pontos w / o qualquer fronteira em particular e necessidade de encontrar o casco convexo.
Em contraste, considere o caso em que o polígono não é auto-interseção, e consiste em um conjunto de pontos em uma lista onde os pontos consecutivos formam a fronteira. Neste caso, é muito mais fácil de descobrir se um polígono é convexo ou não (e você não tem que calcular qualquer ângulo, qualquer um):
Para cada par consecutivo de bordas do polígono (cada tripleto de pontos), calcular o z-componente do produto transversal dos vectores definidos pelas extremidades que apontam para os pontos em ordem crescente. Leve o produto cruzado desses vetores:
given p[k], p[k+1], p[k+2] each with coordinates x, y:
dx1 = x[k+1]-x[k]
dy1 = y[k+1]-y[k]
dx2 = x[k+2]-x[k+1]
dy2 = y[k+2]-y[k+1]
zcrossproduct = dx1*dy2 - dy1*dx2
O polígono é convexo se os Z-componentes dos produtos transversais são ou todos positivos, ou todos negativos. Caso contrário, o polígono é convexo.
Se houver N pontos, certifique-se de calcular produtos cruzados N, por exemplo, ser-se de usar as tripletos (p [N-2], P [N-1], P [0]) e (p [n-1], P [0], p [1]).
Se o polígono é auto-interseção, então ele falhar a definição técnica de convexidade mesmo se seus ângulos dirigidos estão todos na mesma direção, caso em que a abordagem acima não produziria o resultado correto.
Esta questão é agora o primeiro item em qualquer Bing ou o Google quando você procura "determinar polígono convexo." No entanto, nenhuma das respostas são bons o suficiente.
O aceito resposta por @EugeneYokota trabalha verificando se um conjunto não ordenado de pontos pode ser feita em um polígono convexo, mas não é isso que o OP pediu. Ele pediu um método para verificar se um determinado polígono é convexo ou não. (A "polígono" em ciência da computação é normalmente definido [como no XFillPolygon documentação ] como uma matriz ordenada de pontos 2D, com pontos consecutivos unidas com um lado, bem como o último ponto ao primeiro.) além disso, o algoritmo de embrulho, neste caso, teria o tempo-complexidade do O(n^2) para pontos n -. que é muito maior do que realmente necessário para resolver este problema, enquanto a questão pede um algoritmo eficiente
@ jasons de responder , juntamente com as outras respostas que seguem sua idéia, aceita , como um pentagrama ou a um em @ de Zenna comentário, mas estrela polígonos não são consideradas como ser convexo. Como notas @plasmacel em um comentário, esta é uma abordagem boa para usar se você tem conhecimento prévio de que o polígono não é auto-interseção, mas pode falhar se você não tem esse conhecimento.
@ Sekhat de responder está correto, mas também tem o tempo-complexidade do O(n^2) e, portanto, é ineficiente.
@ LorenPechtel de resposta adicionado depois de sua edição é o melhor aqui, mas é vaga.
Um algoritmo correta com ótimo complexidade
O algoritmo que apresentamos aqui tem o tempo complexidade do O(n), corretamente testa se um polígono é convexo ou não, e passa todos os testes eu tenho jogado nele. A idéia é percorrer os lados do polígono, observando a direção de cada lado e a mudança assinado de direção entre os lados consecutivos. "Assinado" aqui significa deixou-ward é positivo e direito do ala é negativo (ou o inverso) e straight-ahead é zero. Esses ângulos são normalizados para estar entre minus-pi (exclusive) e PI (inclusive). Summing todos esses ângulos direção de mudança (também conhecido como o deflexão ângulos) juntos irá resultar em mais-ou-menos uma volta (ou seja, 360 graus) para um polígono convexo, enquanto uma estrela-como polígono (ou um loop auto-interseção) terá uma soma diferente ( n * 360 graus, para n se transforma em geral, para polígonos onde todos os ângulos da deflexão são do mesmo sinal). Portanto, temos de verificar que a soma dos ângulos direção de mudança é mais-ou-menos um turno. Também verifique se os ângulos de direção de mudança são todos positivos ou todos os reveses negativos e não (pi radianos), todos os pontos são reais 2D pontos, e que há vértices consecutivos são idênticos. . (Esse último ponto é discutível -. Você pode querer permitir vértices repetidas, mas eu prefiro proibi-los) A combinação desses controlos pega todos os polígonos convexos e não convexos
Aqui está o código para Python 3 que implementa o algoritmo e inclui algumas eficiências menores. O código é mais do que realmente é due às linhas de comentário e a contabilidade envolvidos em evitar acessos ponto repetidas.
TWO_PI = 2 * pi
def is_convex_polygon(polygon):
"""Return True if the polynomial defined by the sequence of 2D
points is 'strictly convex': points are valid, side lengths non-
zero, interior angles are strictly between zero and a straight
angle, and the polygon does not intersect itself.
NOTES: 1. Algorithm: the signed changes of the direction angles
from one side to the next side must be all positive or
all negative, and their sum must equal plus-or-minus
one full turn (2 pi radians). Also check for too few,
invalid, or repeated points.
2. No check is explicitly done for zero internal angles
(180 degree direction-change angle) as this is covered
in other ways, including the `n < 3` check.
"""
try: # needed for any bad points or direction changes
# Check for too few points
if len(polygon) < 3:
return False
# Get starting information
old_x, old_y = polygon[-2]
new_x, new_y = polygon[-1]
new_direction = atan2(new_y - old_y, new_x - old_x)
angle_sum = 0.0
# Check each point (the side ending there, its angle) and accum. angles
for ndx, newpoint in enumerate(polygon):
# Update point coordinates and side directions, check side length
old_x, old_y, old_direction = new_x, new_y, new_direction
new_x, new_y = newpoint
new_direction = atan2(new_y - old_y, new_x - old_x)
if old_x == new_x and old_y == new_y:
return False # repeated consecutive points
# Calculate & check the normalized direction-change angle
angle = new_direction - old_direction
if angle <= -pi:
angle += TWO_PI # make it in half-open interval (-Pi, Pi]
elif angle > pi:
angle -= TWO_PI
if ndx == 0: # if first time through loop, initialize orientation
if angle == 0.0:
return False
orientation = 1.0 if angle > 0.0 else -1.0
else: # if other time through loop, check orientation is stable
if orientation * angle <= 0.0: # not both pos. or both neg.
return False
# Accumulate the direction-change angle
angle_sum += angle
# Check that the total number of full turns is plus-or-minus 1
return abs(round(angle_sum / TWO_PI)) == 1
except (ArithmeticError, TypeError, ValueError):
return False # any exception means not a proper convex polygon
A seguinte função Java / método é uma implementação do algoritmo descrito no esta resposta .
public boolean isConvex()
{
if (_vertices.size() < 4)
return true;
boolean sign = false;
int n = _vertices.size();
for(int i = 0; i < n; i++)
{
double dx1 = _vertices.get((i + 2) % n).X - _vertices.get((i + 1) % n).X;
double dy1 = _vertices.get((i + 2) % n).Y - _vertices.get((i + 1) % n).Y;
double dx2 = _vertices.get(i).X - _vertices.get((i + 1) % n).X;
double dy2 = _vertices.get(i).Y - _vertices.get((i + 1) % n).Y;
double zcrossproduct = dx1 * dy2 - dy1 * dx2;
if (i == 0)
sign = zcrossproduct > 0;
else if (sign != (zcrossproduct > 0))
return false;
}
return true;
}
O algoritmo é garantido para trabalho, enquanto os vértices são ordenados (no sentido horário ou anti-horário), e você não tem auto-interseção bordas (ou seja, ele só funciona para polígono simples ).
Aqui está um teste para verificar se um polígono é convexo .
Considere cada conjunto de três pontos ao longo do polígono. Se cada ângulo é de 180 graus ou menos você tem um polígono convexo. Quando você descobrir cada ângulo, também manter uma execução total de (180 - angular). Para um polígono convexo, este terá um total de 360.
Este teste é executado em O (n).
Note, também, que na maioria dos casos este cálculo é algo que você pode fazer uma vez e salvar - a maior parte do tempo que você tem um conjunto de polígonos para trabalhar com que não vá mudando o tempo todo
.Para testar se um polígono é convexo, cada ponto do polígono deve estar nivelado com ou atrás de cada linha.
Aqui está uma imagem exemplo:
O por @RoryDaulton parece ser o melhor para mim, mas o que se um dos ângulos é exatamente 0? Alguns podem querer tal um caso extremo para retornar True, no caso, a mudança que "<=" para "<" na linha:
if orientation * angle < 0.0: # not both pos. or both neg.
Aqui estão os meus casos de teste que destacam a questão:
# A square
assert is_convex_polygon( ((0,0), (1,0), (1,1), (0,1)) )
# This LOOKS like a square, but it has an extra point on one of the edges.
assert is_convex_polygon( ((0,0), (0.5,0), (1,0), (1,1), (0,1)) )
O segundo assert falhar na resposta original. Deveria? Para o meu caso de uso, eu preferiria que não.
Eu implementado ambos os algoritmos: o postado por @UriGoren (com uma pequena melhora - única inteiro matemática) eo de @RoryDaulton, em Java. Eu tive alguns problemas, porque o meu polígono é fechado, então ambos os algoritmos foram considerando o segundo como côncavo, quando era convexo. Então eu mudei para evitar tal situação. Meus métodos também usa um índice de base (que pode ser ou não 0).
Estas são as minhas vértices de teste:
// concave
int []x = {0,100,200,200,100,0,0};
int []y = {50,0,50,200,50,200,50};
// convex
int []x = {0,100,200,100,0,0};
int []y = {50,0,50,200,200,50};
E agora os algoritmos:
private boolean isConvex1(int[] x, int[] y, int base, int n) // Rory Daulton
{
final double TWO_PI = 2 * Math.PI;
// points is 'strictly convex': points are valid, side lengths non-zero, interior angles are strictly between zero and a straight
// angle, and the polygon does not intersect itself.
// NOTES: 1. Algorithm: the signed changes of the direction angles from one side to the next side must be all positive or
// all negative, and their sum must equal plus-or-minus one full turn (2 pi radians). Also check for too few,
// invalid, or repeated points.
// 2. No check is explicitly done for zero internal angles(180 degree direction-change angle) as this is covered
// in other ways, including the `n < 3` check.
// needed for any bad points or direction changes
// Check for too few points
if (n <= 3) return true;
if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex
n--;
// Get starting information
int old_x = x[n-2], old_y = y[n-2];
int new_x = x[n-1], new_y = y[n-1];
double new_direction = Math.atan2(new_y - old_y, new_x - old_x), old_direction;
double angle_sum = 0.0, orientation=0;
// Check each point (the side ending there, its angle) and accum. angles for ndx, newpoint in enumerate(polygon):
for (int i = 0; i < n; i++)
{
// Update point coordinates and side directions, check side length
old_x = new_x; old_y = new_y; old_direction = new_direction;
int p = base++;
new_x = x[p]; new_y = y[p];
new_direction = Math.atan2(new_y - old_y, new_x - old_x);
if (old_x == new_x && old_y == new_y)
return false; // repeated consecutive points
// Calculate & check the normalized direction-change angle
double angle = new_direction - old_direction;
if (angle <= -Math.PI)
angle += TWO_PI; // make it in half-open interval (-Pi, Pi]
else if (angle > Math.PI)
angle -= TWO_PI;
if (i == 0) // if first time through loop, initialize orientation
{
if (angle == 0.0) return false;
orientation = angle > 0 ? 1 : -1;
}
else // if other time through loop, check orientation is stable
if (orientation * angle <= 0) // not both pos. or both neg.
return false;
// Accumulate the direction-change angle
angle_sum += angle;
// Check that the total number of full turns is plus-or-minus 1
}
return Math.abs(Math.round(angle_sum / TWO_PI)) == 1;
}
E agora de Uri Goren
private boolean isConvex2(int[] x, int[] y, int base, int n)
{
if (n < 4)
return true;
boolean sign = false;
if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex
n--;
for(int p=0; p < n; p++)
{
int i = base++;
int i1 = i+1; if (i1 >= n) i1 = base + i1-n;
int i2 = i+2; if (i2 >= n) i2 = base + i2-n;
int dx1 = x[i1] - x[i];
int dy1 = y[i1] - y[i];
int dx2 = x[i2] - x[i1];
int dy2 = y[i2] - y[i1];
int crossproduct = dx1*dy2 - dy1*dx2;
if (i == base)
sign = crossproduct > 0;
else
if (sign != (crossproduct > 0))
return false;
}
return true;
}
Este método iria trabalhar em polígono simples (sem auto interseção bordas) assumindo que os vértices são ordenados (sentido horário ou anti)
Para uma disposição de vértices:
vertices = [(0,0),(1,0),(1,1),(0,1)]
As seguintes verificações de implementação python se o componente z de todos os produtos transversais têm o mesmo sinal
def zCrossProduct(a,b,c):
return (a[0]-b[0])*(b[1]-c[1])-(a[1]-b[1])*(b[0]-c[0])
def isConvex(vertices):
if len(vertices)<4:
return True
signs= [zCrossProduct(a,b,c)>0 for a,b,c in zip(vertices[2:],vertices[1:],vertices)]
return all(signs) or not any(signs)
Adaptado código de Uri em Matlab. Esperamos que esta ajuda pode.
Esteja ciente de que o algoritmo de Uri só funciona para polígono simples ! Então, certifique-se de testar se o polígono é simples em primeiro lugar!
% M [ x1 x2 x3 ...
% y1 y2 y3 ...]
% test if a polygon is convex
function ret = isConvex(M)
N = size(M,2);
if (N<4)
ret = 1;
return;
end
x0 = M(1, 1:end);
x1 = [x0(2:end), x0(1)];
x2 = [x0(3:end), x0(1:2)];
y0 = M(2, 1:end);
y1 = [y0(2:end), y0(1)];
y2 = [y0(3:end), y0(1:2)];
dx1 = x2 - x1;
dy1 = y2 - y1;
dx2 = x0 - x1;
dy2 = y0 - y1;
zcrossproduct = dx1 .* dy2 - dy1 .* dx2;
% equality allows two consecutive edges to be parallel
t1 = sum(zcrossproduct >= 0);
t2 = sum(zcrossproduct <= 0);
ret = t1 == N || t2 == N;
end
