java - 计算不可淹没面积

Question

我有一个 2D 数组 (n * m) 作为 Canvas ，其中包含已用点 (startingPoints) 的坐标。我必须计算，其中有多少点无法从 Canvas 外部进行洪水填充。 field 只能向 4 个方向移动，积分分为三种类型:免费、已 field 、已使用。使用过的点不可在场上使用，场上也不会越过它。因此不可场点的数量为 n*m-fieldable-startingPoints。

现在我这样做:我从边界的每个点使用堆栈运行洪水填充，然后计算有多少个点被部署。

但这不适用于尺寸为 10^18*10^18 的 Canvas 。这需要大量内存，我必须找到比使用这个经典的洪水填充更好的解决方案。

有人可以帮忙提供更好的解决方案吗？

Answer 1

您可以翻转问题并使用 Point In Polygon 搜索出现在字段内部的点。技术。

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

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

在每次洪水填充期间，您都会保留填充点的计数，如果给定的洪水填充完成并且其叶子均不在边界上，则将该填充的计数包含在不可现场点的总数中.