给定笛卡尔坐标中的多边形（不一定是凸的），我想知道是否有任何方法可以检查该多边形的对称性？
我可以想到一个 O(N) 解决方案：使用旋转卡尺检查每对相对边缘是否平行且大小相等。但是，我无法证明该算法的正确性。您能提出更好的解决方案吗？
问问题
2477 次
3 回答
1
- 您计算多边形的重心。
- 您将其转换为原点，以便您的重心具有 (0,0) 作为坐标。
- 然后对于坐标 (i, j) 的每个顶点，检查是否存在具有坐标 (-i, -j) 的顶点。
这将证明您的多边形确实是对称的。
复杂性：N，假设您可以从它们的坐标直接访问您的顶点。
于 2011-05-04T09:07:15.590 回答
1
你必须更清楚地说明允许什么样的对称。中心对称（又名 180 度旋转）？在其中一个轴上镜像对称？任何程度的旋转？在某些应用程序中，只允许旋转 0,90,180,270 + 镜像...答案在每种情况下都会有所不同。
仅对于中心对称，如果您假设多边形很好地表示（即边缘上没有额外的顶点，并且顶点包含在包含前向运算符的范围内，那么中心对称多边形将具有偶数 2*N 个顶点，并且您可以这样做：
设置 iter1 引用第 0 个顶点，设置 iter2 引用第 N 个顶点。
重复N次：
if( *iter1 != *iter2 ) 返回假；
返回真；
于 2013-09-01T19:32:51.963 回答
0
您首先需要定义要检查的对称类型（多边形应该不变的变换）。您提供的算法将检查凸多边形的中心对称性（因为旋转卡尺仅适用于凸多边形）。
于 2017-07-12T01:31:12.317 回答