给定一个笛卡尔坐标下的多边形(不一定是凸的)，我想知道是否有任何方法可以检查该多边形的对称性？
我可以想到一个复杂度为 O(N) 的解决方案:使用旋转卡尺检查每对对边是否平行且大小相等。但是，我无法证明该算法的正确性。您能提出更好的解决方案吗？
最佳答案
- 您计算多边形的重心。
- 你将它平移到原点，这样你的重心就以 (0,0) 为坐标。
- 然后对于坐标为 (i, j) 的每个顶点，检查是否存在坐标为 (-i, -j) 的顶点。
这将证明您的多边形确实是对称的。
复杂度:N，假设您可以直接从坐标访问顶点。
关于algorithm - 检查多边形是否对称，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5881009/