algorithm - 用不超过 8 个顶点的多边形包围 map 上的零点簇

Question

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

Answer 1

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

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

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