Controlla se un poligono è simmetrico
-
28-10-2019 - |
Domanda
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?
Soluzione
- 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.
Altri suggerimenti
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:
-
Imposta iter1 riferimento 0 ° vertice e iter2 per fare riferimento a N ° vertice.
-
Ripeti N volte:
if (* iter1!= * iter2) restituisce false;
-
return true;
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).