网格中的JAVA孔 [英] JAVA Hole in Grid

问题描述

我需要在java的二维网格中找到漏洞 - 你能指出我采用哪种算法来做到这一点？

以下几点：

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

我需要弄清楚这个网格中洞或包围空间的位置。我有点失落，至于如何做到这一点。

积分点：

假设每个点都是1x1 p>

解决方案

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

<1>找到最西边，最东边，最北边和最南边的任何固体。记住它们为xmin xmax ymin ymax。

2）用这些尺寸分配一个2d的整数数组（初始化为0），并将其中的所有实心点作为值-1。

3）将计数器初始化为1.扫描2d数组。每当你找到一个0点时，将它设置为 counter 和floodfill counter s到每个相邻的点除非你用尽了积分才能填充，否则不是-1。 （要进行填充，一种方法是保留一组尚未填满所有邻居的点，然后迭代这些点，为该集添加新点，直到该集耗尽 - >没有剩下的要填充到。）现在增加计数器并继续。

4）当扫描整个网格时，扫描周边。每当你在外围看到一个非-1时，将该blob标记为没有被包围（只要你找到的blob数量有一个bools数组）。

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

阅读关于blob提取的信息： http://en.wikipedia.org/wiki/Blob_extraction

I need to find "holes" in a 2D grid in java - can you point me toward the best sort of algorithm to do this?

With the input of the following points:

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.

Plot of the points:

Assuming each point is 1x1

解决方案

This is basically a blob extraction algorithm + a bit extra. Do this:

1) Find the westmost, eastmost, northmost and southmost any solid is placed. Remember them as xmin xmax ymin ymax.

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) 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) 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) Every numbered blob you have not marked is surrounded.

Read about blob extraction here: http://en.wikipedia.org/wiki/Blob_extraction

这篇关于网格中的JAVA孔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！