找到布尔网格多边形

-1

我有布尔的这样找到布尔网格多边形

2-dimensional array of bool

二维阵列的形状不会有任何漏洞 - 即使它有 - 我会忽略他们。现在，我想找到的多边形拥抱我的形状：

embracing polygon

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

来源

2013-09-16 user2033412

它看起来好像你找到了多边形。但也许你可以更多地解释你有什么和你想要什么。你的阵列代表了什么？你想要为你想要找到的多边形表示什么样的表示？ –

我手动找到了多边形，但我想让我的程序找到它。我想找到代表多边形的x-y坐标列表。 – user2033412

由于你有包括正方形的坐标这个问题的答案 - http://stackoverflow.com/questions/17862162/sort-anticlockwise-the-points-of-rectilinear-polygon#comment26081406_17862162 - 会让你其余的路程。 –

-1

考虑了更多一点后，我发现它并且有一个O（n）方法来执行此操作：按行搜索包含至少一个相邻字段的第一个坐标，并将其设置为true。从那里你可以明确地向右迈出第一步。从现在开始，只要在四个相邻的场地的基础上走一圈，决定接下来走什么方向。

来源

2013-09-18 07:26:38 user2033412

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

来源

2013-09-16 14:15:07 Bytemain

delaunay-triangulation是O（n * log（n）），我认为这对我的任务来说太昂贵了。我敢打赌，有一个O（n） - 做到这一点。 – user2033412

找到布尔网格多边形

回答

相关问题