网格中的 JAVA 孔
我需要在 Java 中的 2D 网格中找到洞" - 你能告诉我最好的算法吗?
I need to find "holes" in a 2D grid in java - can you point me toward the best sort of algorithm to do this?
输入以下几点:
5,3
5,4
8,4
5,5
6,3
7,3
7,4
6,5
我需要找出这个网格中洞"或包围空间的位置.我对如何做到这一点有点迷茫.
I need to figure out the positions of the "hole" or surrounded space in this grid. I'm a bit lost as to how to do this.
点的情节:
假设每个点是 1x1
推荐答案
这基本上是一个blob提取算法+一点额外的.这样做:
This is basically a blob extraction algorithm + a bit extra. Do this:
1) 找到放置任何实体的最西、最东、最北和最南.记住它们为 xmin xmax ymin ymax.
1) Find the westmost, eastmost, northmost and southmost any solid is placed. Remember them as xmin xmax ymin ymax.
2) 分配具有这些维度的二维整数数组(初始化为 0)，并将所有实心点作为值 -1 放入其中.
2) Allocate an 2d array of integers (initialized to 0) with those dimensions, and place all solid points in it as the value -1.
3) 将计数器初始化为 1.扫描二维数组.每次找到一个为 0 的点时，将其设置为 counter 并将 counters 填充到每个不是 -1 的相邻点上，直到用完点为止洪水填充到.(要进行填充，一种方法是保留一组尚未填充所有邻居的所有点，然后迭代这些点，将新点添加到集合中，直到集合用完 -> 没有任何东西可以填充到.) 现在增加计数器并继续.
3) Make a counter initialized to 1. Scan the 2d array. Every time you find a point that is 0, set it to counter and floodfill counters onto every adjacent point that is not a -1 until you've run out of points to floodfill onto. (To do a floodfill, one way is to keep a set of all points you haven't floodfilled all the neighbours of yet, and iterate over these, adding new points to the set until the set is exhausted -> nothing left to floodfill onto.) Now increment the counter and continue.
4) 扫描整个网格后，扫描周边.每次您在外围看到非 -1 时，将该 blob 标记为没有被包围(通过与您找到的 blob 数量一样长的 bool 数组).
4) When you've scanned the whole grid, scan the perimeter. Every time you see a non -1 on the perimeter, mark that blob as not being surrounded (by having an array of bools as long as the number of blobs you found).
5) 您未标记的每个编号的 blob 都会被包围.
5) Every numbered blob you have not marked is surrounded.
在此处了解 blob 提取:http://en.wikipedia.org/wiki/Blob_extraction
Read about blob extraction here: http://en.wikipedia.org/wiki/Blob_extraction
相关文章