Controlla se un poligono è simmetrico

Question

Dato un poligono (non necessario convesso) nella coordinata cartesiana, mi chiedo se ci sia un modo per verificare la simmetria di quel poligono?

Posso pensare a una soluzione O (N): usare calibri rotanti per verificare se ogni coppia di spigoli opposti è parallela e di dimensioni uguali.Tuttavia, non posso provare la correttezza di quell'algoritmo.Potete suggerire una soluzione migliore?

Answer 1

• Calcoli il centro di gravità del poligono.
• Lo traduci nell'origine in modo che il tuo centro di gravità abbia (0,0) come coordinata.
• Quindi per ogni vertice di coordinate (i, j) si controlla che ci sia un vertice che ha coordinate (-i, -j).

Questo dimostrerà che il tuo poligono è davvero simmetrico.

Complessità: N, assumendo che tu possa accedere direttamente ai tuoi vertici dalle loro coordinate.

Answer 2

Devi rendere più chiaro quale tipo di simmetria è consentita.Simmetria centrale (ovvero rotazione di 180 gradi)?Simmetria speculare su uno degli assi?Rotazione di qualsiasi grado?In alcune applicazioni sono consentite solo rotazioni di 0,90,180,270 + mirroring ... La risposta sarebbe diversa in ogni caso.

Solo per la simmetria centrale, se presumi che il poligono sia ben rappresentativo (cioè nessun vertice extra sugli spigoli, e i vertici sono contenuti in un contenuto con un operatore diretto, allora il poligono simmetrico centrale avrebbe un numero pari 2 * N verticie puoi farlo:

1. Imposta iter1 riferimento 0 ° vertice e iter2 per fare riferimento a N ° vertice.

2. Ripeti N volte:

   if (* iter1!= * iter2) restituisce false;

3. return true;

Answer 3

Prima devi definire il tipo di simmetria che vuoi controllare (a quale trasformazione il tuo poligono dovrebbe essere invariante).L'algoritmo fornito controllerà la simmetria centrale per i poligoni convessi (poiché i calibri rotanti funzionano solo con i poligoni convessi).