计算非洪水可填充区域

问题描述 投票:0回答:2

我有一个2D数组(n * m)作为画布和其中的使用点(startingPoints)的坐标。我必须计算,它中有多少点不能从画布外部填充洪水。场只能在4个方向上进行,有三种类型的点:自由,现场,使用。使用的点不可现场,而字段不能覆盖它。因此,不可销售点数是n * m-fieldable-startingPoints。

现在我这样做:我从边界的每个点运行堆栈填充,我计算,有多少点被派出。

但这不适用于帆布,尺寸为10 ^ 18 * 10 ^ 18。这需要大量的内存,我必须找到比使用这种经典的floodfill更好的解决方案。

有人可以帮助更好的解决方案?

java matrix graphics field flood-fill
2个回答
1
投票

您可以通过使用Point In Polygon技术来解决问题,并搜索出现在字段内的点。

一旦确定了这一点,就从它开始进行洪水填充。如果洪水填充曾经触及边界,那么你的点和由这一次洪水填充所填充的所有点都将从候选者中丢弃,因为这些点是可现场的。

您可以通过查找尚未填充的字段内的点来重复此过程。

在每次填充填充时,您可以保留填充点的数量,如果给定填充填充并且没有任何叶子在边界上,则包括填充总计数不可分段点的计数。


0
投票

我不是100%肯定我明白你想要什么。

我想象的是一个迷宫,在外边缘有多个可能的起点,你想知道从外面可以访问/填充的所有可能区域吗?

使其更有效的解决方案是缓存值,以便您不会重新计算已计算的填充。

制作一个相同大小的另一个2d数组,以跟踪已填充的点。

byte[][] filledPoints = new byte[n][m];这样的东西用0初始化,意思是未填充。

仅举例如:

final byte UNFILLED = 0;
final byte RED = 1;
final byte BLUE = 2;

当您进行填充时,对于您访问的每个点,使用“填充颜色”标记该点以表示它已经计算过。

例如。 filledPoints[0][1] = RED

但是,当进行填充时,如果您正在开始的点已经填充,那么您将要执行的整个填充已经由先前填充计算。

if(filledPoints[x][y] != UNFILLED){
    // Then this fill was already filled with the color of filledPoint[x][y]
}

因此,如果它已经计算过,那么您不需要再次计算它,因此请转到您要尝试填充的下一个起始点并检查是否已填充。

当您找到尚未填充的填充区域时,请开始使用新的“颜色”填充它,并跟踪填充的区域。

例如。 filledPoints[0][386] = BLUE

非洪水可填充区域当然是总面积减去所有洪水填充区域的总和。

© www.soinside.com 2019 - 2024. All rights reserved.