N个边界点表示多边形的相交组快速查找：能否突破O(n²)复杂度？

Great question! Let's break this down clearly—yes, there absolutely are ways to do this better than a naive O(n²) pairwise check, especially since your polygons are capped at 10 points each. Here's the breakdown of the key strategies:

1. The Problem with O(n²) #

First, let's acknowledge why the naive approach is slow: checking every single pair of polygons means you're doing ~n²/2 intersection tests. For large n (like thousands of polygons), this becomes prohibitively slow. The goal is to eliminate as many non-intersecting pairs as possible without running a full intersection test.

2. Spatial Filtering: Cut Down Candidate Pairs #

The core optimization here is using spatial indexing to only consider polygons that are physically close enough to potentially intersect. Common techniques include:

• Grid Partitioning:

  • Divide your entire 2D space into a grid of cells (size should be chosen based on your average polygon size—aim for cells slightly larger than the biggest polygon's bounding box).
  • For each polygon, compute its axis-aligned bounding box (AABB) and assign the polygon to all grid cells its AABB overlaps.
  • Only check for intersections between polygons in the same cell or adjacent cells. This drastically reduces the number of pairs you need to evaluate, since most polygons won't share a cell with others.

• Quadtrees/R-Trees:

  • Quadtrees: Recursively split space into four quadrants, placing polygons into the smallest quadrant their AABB fits into. When checking for potential intersections, you only traverse the tree branches that could contain overlapping polygons.
  • R-Trees: A specialized index for multi-dimensional data that groups nearby objects into bounding boxes. It's perfect for quickly querying all polygons whose AABB overlaps with a given polygon's AABB—this gives you a small set of candidate pairs to validate.

These spatial indexing methods bring the candidate pair generation complexity down to O(n log n) in most cases, since inserting into and querying the index is logarithmic in the number of polygons.

3. Fast Intersection Validation for Candidate Pairs #

Once you have your candidate pairs, you need an efficient way to check if two polygons actually intersect. Since your polygons have at most 10 points, the Separating Axis Theorem (SAT) is ideal here:

• For two simple polygons, if there exists any axis (aligned to the edges of either polygon) where their projections don't overlap, the polygons don't intersect.
• With 10-point polygons, you only need to check up to 20 axes (10 from each polygon). For each axis, project all points of both polygons and check if the projection intervals overlap. If even one axis has non-overlapping projections, you can immediately rule out intersection.

SAT is fast (O(m + k) where m and k are the number of points in each polygon—here, max 20 operations per pair) and works perfectly for simple polygons.

4. Overall Complexity #

Putting it all together, the total complexity becomes O(n log n + k), where k is the number of actual intersecting polygon pairs. Since k is usually much smaller than n², this is a huge improvement over O(n²) for large datasets.

When Might O(n²) Still Be Okay? #

If your n is very small (like <100 polygons), the overhead of setting up a spatial index might not be worth it—sticking with pairwise checks could be simpler and just as fast. But for larger n, the optimized approach is a no-brainer.

内容的提问来源于stack exchange，提问作者wqm1800