检查多边形是否对称

Question

给定笛卡尔坐标中的多边形(不是必要的凸面),我想知道是否有任何方法可以检查该多边形的对称性？

我可以想到一个O(N)解决方案:使用旋转卡尺检查每对相对边是否平行并且大小相等.但是,我无法证明该算法的正确性.你能建议更好的解决方案吗？

Answer 1

• 您计算多边形的重心。
• 您将其平移到原点，以便您的重心坐标为 (0,0)。
• 然后，对于坐标 (i, j) 的每个顶点，检查是否存在具有坐标 (-i, -j) 的顶点。

这将证明你的多边形确实是对称的。

复杂度：N，假设您可以从坐标直接访问顶点。