通过填充矩形来检查许多（小）多边形与一个（大）多边形的交集？
我有一个 2D 计算几何/GIS 问题，我认为这应该是常见的，我希望找到一些现有的代码/库来使用。
问题是检查一大组（数千个）小多边形的哪个子集与单个大多边形相交。 （我所说的“小”和“大”指的是多边形覆盖的空间量，而不是定义它们的点的数量，尽管通常假设定义多边形的点的数量大致与其几何尺寸成正比为了给出比例感，请将“大”视为美国某个州的多边形，将“小”视为城镇的多边形。）
假设使用标准 CheckIfPolygonsIntersect( P, p ) 的简单解决方案 。针对每个小多边形 p 针对一个大多边形 P 调用的函数太慢。似乎有一些方法可以预处理大多边形，以使大多数小多边形的相交检查变得微不足道。特别是，您似乎可以创建一小组部分/几乎填充大多边形的矩形。同样，您可以创建一小组矩形，部分/几乎填充大多边形的边界框区域，而该区域实际上不在大多边形内。然后，绝大多数小多边形都可以被简单地包含或排除：如果它们完全位于大多边形的边界矩形之外，则它们将被排除。如果它们完全位于内部边界矩形但外部多边形矩形之一的边界内，则将它们排除在外。如果它们的任何点位于任何内部矩形内，则将它们包括在内。仅当上述情况都不适用时，您才必须调用 CheckIfPolygonsIntersect( P, p ) 函数。
这是一个众所周知的算法吗？您是否知道现有代码可以计算任意（凸或凹）多边形的一组合理的内部/外部矩形？矩形不必在所有情况下都是完美的；它们只需要填充大部分多边形以及大部分内部边界矩形但外部多边形区域。
这是一个关于如何计算这些矩形的简单计划：
- 获取大多边形的边界框，并为每个点在其上构建一个 10x10 的点网格
- ，确定它是在多边形内部还是外部，
- 将每个点“生长”到一个矩形，通过在四个方向中的每一个方向上迭代扩展它，直到矩形边缘之一穿过多边形边缘之一，在这种情况下你已经走得太远了（这实际上是在“二分搜索”类型的迭代中完成的，所以只需几次迭代，您就可以找到在每个方向上扩展的正确量，当然存在一些问题：是否一次最大化边缘或彼此一致）
- 任何尚未扩展的网格点； 被另一个点的扩展覆盖就会消失
- 当所有点都扩展（或消失）时，
，您拥有一组内部和外部矩形当然，大多边形的某些疯狂凹形可能会导致一些较差/小的矩形。但是假设多边形大多是合理的（例如，假设它们是美国各州的形状），那么您似乎会得到一组很好的矩形，并且可以极大地优化您随后要做的数千个相交检查。
该算法有名称（和代码）吗？
编辑：我已经在使用四叉树来确定可能与大多边形的边界矩形相交的小多边形。因此，问题在于检查哪些多边形实际上与大多边形相交。
感谢您的任何帮助。
I have a 2D computational geometry / GIS problem that I think should be common and I'm hoping to find some existing code/library to use.
The problem is to check which subset of a big set (thousands) of small polygons intersect with a single large polygon. (By "small" and "large" I'm referring to the amount of space the polygons cover, not the number of points that define them, although in general suppose that the number of points defining a polygon is roughly proportional to its geometric size. And to give a sense of proportion, think of "large" as the polygon for a state in the United States, and "small" as the polygon for a town.)
Suppose the naive solution using a standard CheckIfPolygonsIntersect( P, p ) function, called for each small polygon p against the one large polygon P, is too slow. It seems that there are ways to pre-process the large polygon to make the intersection checks for the majority of the small polygons trivial. In particular, it seems like you could create a small set of rectangles that partially/almost fill the large polygon. And similarly you could create a small set of rectangles that partially/almost fill the area of the bounding box of the large polygon that is not actually within the large polygon. Then the vast majority of your small polygons could be trivially included or excluded: if they are fully outside the bounding rect of the large polygon, they are excluded. If they are fully inside the boundary of one of the inside-bounding-rect-but-outside-polygon rects, they are excluded. If any of their points are within any of the internal rects, they are included. And only if none of the above apply do you have to call the CheckIfPolygonsIntersect( P, p ) function.
Is that a well-known algorithm? Do you know of existing code to compute a reasonable set of interior/exterior rectangles for arbitrary (convex or concave) polygons? The rectangles don't have to be perfect in all cases; they just have to fill much of the polygon, and much of the inside-bounding-rect-but-outside-polygon area.
Here's a simple plan for how I might compute these rectangles:
- take the bounding box of the large polygon and construct a, say, 10x10 grid of points over it
- for each point, determine if it's inside or outside the polygon
- "grow" each point into a rectangle by iteratively expanding it in each of the four directions until one of the rect edges crosses one of the polygon edges, in which case you've gone too far (this would actually be done in a "binary search" kind of iteration so with just a few iterations you could find the correct amount to expand in each direction; and of course there is some question of whether to maximize the edges one at a time or in concert with one another)
- any not-yet-expanded grid point that get covered by another point's expansion just disappears
- when all points have been expanded (or have disappeared), you have your set of interior and exterior rectangles
Of course, certain crazy concave shapes for the large polygon could lead to some poor/small rectangles. But assuming the polygons are mostly reasonable (e.g., say they were the shapes of the states of the United States), it seems like you'd get a good set of rectangles and could greatly optimize those thousands of intersection checks you'd subsequently do.
Is there a name (and code) for that algorithm?
Edit: I am already using a quad-tree to determine the small polygons that are likely to intersect with the bounding rect of the large polygon. So the problem is about checking which of those polygons actually do intersect with the large polygon.
Thanks for any help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
在您的计划中，您描述了与符号距离图方法非常相似的方法。谷歌“距离地图算法”了解详细信息。我希望这就是您正在寻找的。
In your plan you described something very similar to the signed distance map method. Google 'distance map algorithm' for details. I hope it will be what you're looking for.