0

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

4

1 回答 1

5

不可以。这样的细分并不总是可能的：

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

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

考虑 的顶点集P1。必须有一个至少包含(N1)/6顶点的区域。调用顶点V1和区域R1。必须有一个区域至少包含 的(N2)/6顶点P2。将顶点V2称为 region 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 个正方形）分割成两个全等区域。如果人类很难将一个多格骨牌拆分为两个全等区域，那么您如何期望计算机将一个一般形状拆分为六个全等区域？

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

于 2012-10-28T08:57:38.783 回答