通过填充矩形检查许多（小）多边形与一个（大）多边形的交集？

Question

我有一个2D计算几何/ GIS问题，我认为应该是常见的，我希望找到一些现有的代码/库来使用。

的问题是，以检查其中大集的一个子集小多边形（千）有一个大的多边形相交。 （通过“小”和“大”我指的是多边形覆盖的空间量，而不是定义它们的点的数量，尽管通常假设定义多边形的点的数量大致与其几何尺寸成比例。为了给人一种比例感，把“大”看作美国州的多边形，将“小”看作小镇的多边形）。

假设使用标准CheckIfPolygonsIntersect（ P，p）函数，对于每个小多边形p对一个大的多边形P要求，太慢了。似乎有办法预先处理大的多边形，以使交叉点检查大多数小多边形不重要。特别是，您似乎可以创建一小部分矩形，部分/几乎填满大多边形。类似地，您可以创建一小部分矩形，部分/几乎填充实际上不在大多边形内的大多边形的边界框的区域。那么绝大多数小多边形都可以被包含或排除在外：如果它们完全位于大多边形的边界矩之外，则将它们排除在外。如果它们完全位于内边界矩形边界之内但是外部多边形矩形的边界内，则它们被排除。如果他们的任何观点都在任何内部观点之内，那么它们都包含在内。只有以上都不适用，你必须调用CheckIfPolygonsIntersect（P，p）函数。

那是一个众所周知的算法？你知道现有的代码来计算任意（凸或凹）多边形的一组合理的内/外矩形吗？在所有情况下，矩形不一定是完美的;他们只需要填充大部分多边形，以及大部分内部边界但是外部多边形区域。

下面是我怎么可能会计算这些矩形一个简单的计划：

• 采取大多边形的边框和构建点的，比如，10×10格在它
• 每个点，确定如果是内部还是多边形
• 在四个方向的反复扩张，直到矩形边缘之一穿过的多边形边一个“成长”的每个点成长方形，在这种情况下，你已经走得太远了外（这实际上是在“二分搜索”类型的迭代中完成的，因此只需几次迭代就可以找到正确的数额在每个方向扩大;当然还有一些问题是否要一次最大化一个边或者一个边是否一致）
• 任何尚未扩展的网格点被另一个点的扩展覆盖消失
• 当所有点已经扩大（或已经消失），你有你的一套内部和外部矩形

当然，大的多边形某些疯狂的凹形可能会导致一些穷/小的矩形。但假设多边形大部分是合理的（比如说，它们是美国各州的形状），看起来你会得到一组好的矩形，并且可以大大地优化你随后做的数千次相交检查。

是否有该算法的名称（和代码）？

编辑：我已经在使用四叉树来确定可能与大多边形的边界矩相交的小多边形。所以问题是检查多边形实际上是否与大多边形相交的那些。

感谢您的任何帮助。

Answer 1

在你的计划中，你描述了一些非常类似于签名的距离图方法。详细信息请参阅Google的“距离图算法”。我希望这将是你要找的。