algorithm - 用不超过 8 个顶点的多边形围绕地图上的零簇

Question

在图像映射（500 x 500）上，我只有零和一。大多数情况下，一切都是一个，但我有几个带零的集群（代表障碍，所以玩家不能越过，比如山丘）。障碍物可以有任意形状，因此需要简化，我决定找到一种方法，用不超过 8 个顶点的多边形包围每个这样的障碍物（周围的多边形内部可以有一些 1，但障碍物的所有 0 都必须在里面那个多边形）。对于每个障碍物，我需要生成一个多边形。我可以连接障碍物外边界上的每个 0，但它会产生具有 n ( n >> 8 ) 个顶点的多边形。我正在寻求任何建议如何做到这一点或一些类似算法的名称。

Answer 1

您应该最初构建集群的凸包。在此之后，您可以使用以下策略将顶点数量减少到 8 个：

您可以找到任何一对连接点的交叉点。在提供的图像点 8 和 9 上替换为一个 10，但增加多边形大小。

注意：这种方法不能保证这个多边形不会与另一个“零”簇重叠。有时，如果没有另一个簇的交集，具有 8 个顶点的多边形可能无法覆盖一个簇。

Answer 2

您可以将 S、SW、W、NW、N、NE、E 和 SE 最远点作为障碍物，并通过在垂直方向上通过这些点的线段创建一个八边形集。即适当地：WE，NW-SE，等等。我认为，这将是最快和最简单的算法，与@Толя 的解决方案相反，它永远不会给你超长的星光状顶点。