java - 网格中的 JAVA 孔

Question

我需要在java中的二维网格中找到“洞”——你能指出我最好的算法吗？

输入以下几点：

5,3
5,4
8,4
5,5
6,3
7,3
7,4
6,5

我需要弄清楚这个网格中“洞”或包围空间的位置。我对如何做到这一点有点迷茫。

点的情节：

假设每个点是 1x1

Answer 1

这基本上是一个blob提取算法+一点额外的。做这个：

1) 找到放置任何实体的最西、最东、最北和最南。记住它们为 xmin xmax ymin ymax。

2) 分配具有这些维度的二维整数数组（初始化为 0），并将所有实心点作为值 -1 放置在其中。

3) 将计数器初始化为 1。扫描二维数组。每次找到一个为 0 的点时，将其设置为counter并填充counters 到每个不是 -1 的相邻点上，直到用完可以填充的点为止。（要进行填充，一种方法是保留一组尚未填充所有邻居的所有点，然后迭代这些点，将新点添加到集合中，直到集合用尽 -> 没有任何东西可以填充到.) 现在增加计数器并继续。

4) 扫描整个网格后，扫描周边。每次您在外围看到非 -1 时，将该 blob 标记为没有被包围（通过拥有与您找到的 blob 数量一样长的 bool 数组）。

5）你没有标记的每个编号的斑点都被包围了。

在此处阅读有关 blob 提取的信息：http ://en.wikipedia.org/wiki/Blob_extraction