Verifique se um polígono é simétrico

Question

Dado um polígono (não necessariamente convexo) na coordenada cartesiana, eu me pergunto se há alguma maneira de verificar a simetria desse polígono?

Posso pensar em uma solução O (N): usar cursores rotativos para verificar se cada par de arestas opostas é paralelo e igual em tamanho.No entanto, não posso provar a exatidão desse algoritmo.Você pode sugerir alguma solução melhor?

Answer 1

• Você calcula o centro de gravidade do seu polígono.
• Você o traduz para a origem de modo que seu centro de gravidade tenha (0,0) como coordenada.
• Em seguida, para cada vértice da coordenada (i, j), você verifica se há um vértice que possui coordenadas (-i, -j).

Isso vai provar que o seu polígono é simétrico de fato.

Complexidade: N, presumindo que você possa acessar diretamente seus vértices a partir de suas coordenadas.

Answer 2

Você precisa deixar mais claro que tipo de simetria é permitida.Simetria central (a.k.a. rotação de 180 graus)?Simetria de espelho sobre um dos eixos?Rotação em algum grau?Em algumas aplicações, apenas rotações de 0,90,180,270 + espelhamento são permitidas ... A resposta seria diferente em cada caso.

Apenas para simetria central, se você assumir que o polígono é bem representado (ou seja, nenhum vértice extra nas arestas e os vértices são mantidos em um contido com um operador direto, então o polígono centralmente simétrico teria um número par 2 * N vértices, e você pode fazer isso:

1. Defina iter1 como referência 0º vértice e iter2 como referência Nº vértice.

2. Repita N vezes:

   if (* iter1!= * iter2) retorna falso;

3. return true;

Answer 3

Primeiro você precisa definir o tipo de simetria que deseja verificar (a qual transformação seu polígono deve ser invariante).O algoritmo que você fornecer irá verificar a simetria central para polígonos convexos (já que cursores rotativos só funcionam com polígonos convexos).