arrays - 从布尔网格中查找多边形

Question

我有一个像这样的二维布尔数组

这个形状不会有任何洞——即使它有——我会忽略它们。现在我想找到包含我的形状的多边形：

有没有准备好用于这种情况的算法？我找不到任何内容，但我不确定我是否知道此任务的正确搜索词。

Answer 1

您可以使用 delaunay 三角剖分，然后删除最长的边。我使用所有边的平均值乘以一个常数。

Answer 2

在考虑了更多之后，我发现了它并且有一个 O(n) 方式来做到这一点：逐行搜索包含至少一个相邻字段设置为 true 的第一个坐标。从那里你肯定可以迈出向右的第一步。从现在开始，只需在场地周围走动，根据四个相邻的场地决定下一步走的方向。