将形状划分为全等子区域

Question

给定一个边相等的不规则多面多边形。有没有什么算法可以把它分成六个大小相等的全等区域？？

Answer 1

不可以。这种细分并不总是可行的：

考虑P通过连接两个正多边形获得的多边形，P1并且P2具有不同且非常多的边N1和N2。该多边形近似于一对圆盘，C1并C2在任意精度范围内。

考虑将其细分为六个全等区域。

考虑 的顶点集P1。必须有一个区域至少包含(N1)/6顶点。调用顶点V1和区域R1。必须有一个区域至少包含 的(N2)/6顶点P2。将顶点V2称为区域R2。

如果R1 != R2，那么必须有一个同余映射R2到R1。如果2*N1 < N2，这种映射是不可能的。选择 N2 远大于 N1。

因此，R1 == R2。有一个区域同时包含V1和V2。每个区域的直径必须大于 的直径P2。

使用两圆近似。每个区域必须包含至少为 1/6 周长C1的弧和至少为 1/6 周长的弧C2。此外，至少有一个区域位于两个圆圈内，并且没有区域完全位于较小的圆圈内。

考虑 的可能同余R1。任何同余 1) 是沿主轴的反射或 2) 将 P1 或 P2 映射到 P 外部或 3) 将周边的某些部分映射到 P 的内部。反射是不够的，因此任何细分都必须包含同余将 P1 的某些部分映射到 P1 的内部。

因此，每个区域边界必须包含一个直径为 的凹弧12。直观地，这表明这种细分是不存在的。

您可以检测多种类型的多边形：

• 6 阶旋转对称C6。这些可以按照旋转对称性的任何方式细分。
• 3 阶二面角对称D6（3 阶旋转 + 反射镜）。沿着镜子剪开。
• 用四个多边形在一个顶点相交的平移平铺平面的形状。这些是具有两对匹配相反路径的形状。在一个方向复制切削刃，在另一个方向复制三次。
• 有些形状具有反射对称性，每个单独的一半具有 3 阶旋转对称性。这些也可以被检测和切割。
• 一些形状具有 2 阶旋转对称性，可以切割成两个具有 3 阶旋转对称性的全等区域。沿边界寻找重复的图案。
• 有些形状具有 3 阶旋转对称性，并且可以对称地分成三个区域。我不确定我能否可靠地检测到这些形状（检测C3很容易，随后的切割则不然）而且我是一个人。
• ...
• polyominoes 是由正方形组成的形状，polyhexes 是由六边形组成的形状，polyiamonds 是由三角形组成的形状。它们很容易被发现，有些甚至有细分。细分（如果存在）也可能难以检测，但至少您可以枚举所有符合正确大小的对齐网格的细分，以查看它们是否一致。
• ...

为了证明问题的复杂性：有一类逻辑谜题，其目标是将复杂的形状（60 个正方形）分成两个全等区域。如果它是不容易的人拆分四角的2米全等的区域，你怎么能指望一个计算机拆分一般形状在6个全等地区？

如果您确实想检测可能进行细分的大多数情况，则必须在编程时间（以支持越来越多的特殊情况）和测试强度之间进行权衡。对于初学者，坚持使用C6, D3 and checkerboard tiles => easy to subdivide; polyforms => maybe possible; the rest => probably no subdivision.