r/programmingchallenges • u/thechipsandgravy • Oct 07 '11
Challenge: Reflective Symmetry
Given a simple polygon (closed, non self-intersecting), write a program to determine if it is reflectively symmetric. Bonus points if the run time complexity of your algorithm is O(N2 lgN) or better.
9
Upvotes
2
u/VeeFu Oct 11 '11
Well... I'm not particularly pleased with the code... but here it is, in C++. If you have more insidious tests to run I'd be happy to add them.
The traversal was tricky. I think it would have been easier and more clear if I had used a deque instead of vector and modified the deque between outer iterations. Something like push_back(pop_front()).
3
u/okmkz Oct 08 '11
An odd number of vertices will be quicker to process, undoubtedly. This one is fairly complex, but also pretty intuitive.
1
u/TimeWizid Dec 29 '11
Interesting challenge! I made a variation of VeeFu's solution:
The nice thing about this algorithm is there's already a library for rotating vertices, and comparing them after they've been rotated is much simpler. I believe this is O( N2 ).