Find all polygons from a set that overlap a given polygon (convex case)

Question

Problem: Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, find all polygons $S_i$ that overlap with $P$. Assume an algorithm to test whether a pair of polygons overlap already exists.

Constraints: We are allowed to perform operations of $O(N \log N)$ on $\{S_i\}$ without knowledge of $P$ (initialization step). After that, given an arbitrary $P$ the algorithm should perform in approximately $O(\log N)$ time when $S$ consists of polygons of uniform size. Hence, an algorithm that just tests $P$ against every $S_i$ will be rejected.

Solution idea: On initialization, insert all vertices of the polygons of $\{S_i\}$ into a kd-tree $K$ and associate each vertex with its associated polygon. Store the diameter $dS$ of the largest polygon in $\{S_i\}$. Then given a polygon $P$, calculate the diameter $dP$ of $P$. Find all vertices in $K$ that are no farther than $\max(dS,dP)/2$ (?) from any vertex in $P$. Test $P$ against only faces that contain the vertices in $K$.

Since lookup in $K$ is a $\log(N)$ operation, then if $N$ is large and $dP$ is approximately equal to dS then the number of tests should be $<< N$.

Any other solution ideas? Google is yielding nothing of value.

Similar to How to find polygons overlap reign but with additional constraints.

Answer 1

Suppose all the polygons $S_1,\dots,S_n,P_1,\dots,P_n$ are given in advance. Then I can propose an algorithm that might often be efficient in practice (though it can degenerate to quadratic-time behavior if you get a sufficiently nasty configuration of polygons).

In particular, the polygon $P_i$ overlaps with some $S_j$ if and only if:

(1) some line segment of the perimeter of $P_i$ crosses some line segment of the perimeter of $S_j$; or,

(2) some vertex of $P_i$ is inside $S_j$, or some vertex of $S_j$ is inside $P_i$.

So, it suffices to check both conditions separately.

Crossings between perimeters

You can check find all crossings between the perimeters of the polygons as follows. Decompose the perimeter of each polygon $P_i$ into a collection of line segments. Do the same for each $S_j$. Then, use the Bentley-Ottmann algorithm (or some other similar algorithm) to find all crossings between these line segments. This will tell you, for each $P_i$, whether its perimeter crosses any of the $S_j$ perimeters. If it does, then you know that $P_i$ has an overlap with some $S_j$.

The running time will be $O((n+k) \log n)$, where $k$ is the number of crossing between these line segments. In practice, you can hope that $k$ won't be too large (it probably often will be fairly small, unless you get really unlucky with how the polygons are arranged).

Vertex inside a polygon

So we have a bunch of polygons, and a bunch of points. I suggest using the Bentley-Ottman sweepline algorithm on the line segments corresponding to the perimeters of the polygons. In addition to an "event" happening at each two intersection between two line segments and at each endpoint of each line segment, create another event at the location of each point. In addition to a binary search tree storing the locations of the line segments that intersect the sweepline, also use an interval tree to store an interval for each polygon that intersects the sweepline (namely, the range of $y$-coordinate values where the sweepline intersects that polygon). Now, when you hit an event corresponding to a point, you can check which intervals in the segment tree contain that point, i.e., which polygons contain that point, using a stabbing query.

By using self-balancing trees, you can arrange that each step of this algorithm can be done in $O(\log n)$ time. Thus, the total running time will again be $O((n+k)\log n)$.

Online queries?

The above describes how to solve your problem in "batch mode", where all polygons are given in advance. What if only $S_1,\dots,S_n$ are given in advance and the $P_i$'s are provided one at a time, and we have to check for overlap in an online fashion? I don't know how to handle that.

I might be able to get you started on an idea for half of it, but I don't see how to flesh it out into a full algorithm. For part of it, I think it might be possible to do something for that case as well, using partially persistent data structures.

Apply the sweepline algorithms above to the polygons $S_1,\dots,S_n$, and store all copies of the binary tree and interval tree at each event. Naively, this would require $\Omega(n^2)$ space (since there are $\Omega(n)$ events and each tree is $\Theta(n)$ in size), which is horrible. Fortunately, each tree differs from the previous tree by only $O(1)$ modifications. Therefore, we can use a persistent data structure to store all of the trees, using standard path copying techniques, and in that way we'll be able to store all of the trees in $O((n+k) \log n)$ space. Moreover, if we keep an array of all of the roots of these trees, then given any x-coordinate, we'll be able to look up the appropriate tree for that x-coordinate in $O(\log (n+k))$ time using binary search.

Given a polygon $P_i$, we'll first look up each vertex of $P_i$ in this data structure to see if it is contained in any of the $S_j$'s. This can be done by taking each vertex, looking up the Bentley-Ottman trees for the x-coordinate of that vertex, and looking up the y-coordinate of that vertex in the interval tree to see if any of the $S_j$s contain it.

Next, we need to go through each line segment in the perimeter of $P_i$ and check whether it intersects any of the line segments of the $S_j$'s. However, I don't know how to do this in a way that supports online queries for the $P_i$'s. So, that's the part you'd need to find a way to fill in.