检查一个多边形是否对称

Question

给定笛卡尔坐标系中的多边形（不一定是凸多边形），我想知道有没有办法检查该多边形的对称性？

我可以想到一个O(N)的解决方案：使用旋转卡尺来检查每对相反边是否平行且大小相等。但是，我无法证明该算法的正确性。您能否提供更好的解决方案？

- Chan Le

---

根据您对所提出解决方案的描述，我认为您只需要寻找180°旋转对称性，而不是其他任何类型（例如120°旋转对称性、镜像等）。 - Damien_The_Unbeliever

只有边数为偶数的多边形才能使用检查对方法。 - Sjoerd C. de Vries

我认为所有边数为奇数的多边形都不能对称？@@ - Chan Le

它们可以具有旋转对称性。 - Sjoerd C. de Vries

一个等边三角形不对称吗？你肯定可以将其对折，这是对称的一种定义。 - JCooper

Answer 1

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

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

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

- user703016

---

这只会检查沿垂直轴的对称性。 - Ezku

@Ezku - Heandel 正在翻转两个坐标，所以我认为这个解决方案是检查旋转对称性，而不是像原始提议中那样的反射对称性。 - Damien_The_Unbeliever

如果多边形的一侧上有一个点位于边缘上，而另一侧的多边形上没有该点，或者多边形具有相同的边缘，会发生什么情况呢？例如，A具有点(0,0),(0,1),(0,2)，而B具有边缘(2,0),(2,2)。通过x=2的反射线，它们可以是相同的。您需要先确保多边形没有多余的点... - Sam Holder

这检查了多边形是否具有相同的顶点，但不能保证它们按相同的顺序连接。 - Damien_The_Unbeliever

显然，并不是每个三角形都具有对称性。但是等边三角形，例如，具有三个镜像和三个旋转对称性，这些都不会被你的算法发现。 - ackb

Answer 2

您需要更清楚地说明允许哪种对称性。中心对称（也称为180度旋转）？关于其中一个轴的镜像对称？任意角度的旋转？在某些应用中，只允许进行0、90、180、270度旋转和镜像操作... 在每种情况下，答案都不同。

对于仅限于中心对称的情况，如果假设多边形被很好地表示（即边缘上没有额外的顶点，并且顶点被包含在具有前向运算符的容器中），则中心对称的多边形将具有偶数2*N个顶点，您可以这样做：

1. 将iter1引用设置为第0个顶点，将iter2引用设置为第N个顶点。 2. 重复N次： 如果(* iter1！= * iter2)返回false; 3. 返回true;

- Michael

Answer 3

首先，您需要定义要检查的对称类型（多边形应该保持不变的转换方式）。您提供的算法将检查凸多边形的中心对称性（因为旋转卡尺只适用于凸多边形）。

- Carlos Alegría