Determining if a collection of convex polygons has nonempty intersection

I don't think you can avoid actually calculating the intersection region over and over. Imagine three polygons which intersect pairwise but don't share a common point: The yes/no answer from a pair-wise test will not help you there. You need the intersection from the first two to test against the third.

From a big-O view you need to consider each polygon at least once, so iterating (in any order) all of them and (re-)intersecting the remaining region sounds pretty optimal. But you are lucky: You can abort as soon as the temporary region is empty (early out).

Calculating the intersection of two polygons is probably best done using BSPs. For convex polygons a dynamic setup to generate balanced trees should not be that costly IMHO (bisection). Maybe a re-balancing after each intersection step proves useful.

Hope that helps

If you have a lot of polygons, you can think of them as the leaf nodes of a (balanced) binary tree. The interior nodes store the polygon of intersection of the child nodes (possibly empty). In this way, you can distribute the computations across multiple cores. The SAT can be used for a fast no-intersection. When SAT detects there is overlap, there is a linear time algorithm for intersection of convex polygons--see Joseph O'Rourke's book "Computational Geometry in C".

This is a better approach than BSPs, mainly because you avoid the unnecessary splitting of edges of polygons. In the BSP approach, splitting leads to lots of collinear points and polygons that are then deemed to have a large number of edges (even though many are collinear). When you have to then intersect polygons of intersection, the number of edges per intersecting polygon becomes quite large.

I wonder; are there any sweepline-style algorithms for this?

It's been said that computational geometry is the study of how to generalize sorting algorithms to more than one dimension. So how would one solve this problem in 1d?

In 1d, your polygons are line segments, and you want to know if any overlap.

You can do this in faster than O(n^2). First, you sort all the endpoints -- this takes O(n log(n)) -- and then you do an O(n) scan over them to actually detect the overlaps.

So, does this generalize to 2d? Can we do something like the trapezoidal decomposition to figure this out?

I feel that, if something like this were well-known, Dave would know about it... but maybe it's nevertheless possible...

E.g., something like...

- Sort vertices by x-coordinate.
- Sweep vertical line across region, keeping track of intersections with polygons. Note that each polygon will intersect the sweepline either once or twice (if everything is in general position; no completely vertical edges).
- At each step, check for interleaved intersections (overlapping segments) on the sweepline.

What complexity would this have?
- The sorting takes O(n log(n))
- At each of the n steps, we need to sort the O(n) intersections; that's n*nlog(n), for O(n^2 log(n) ). Or is it?
- The check for segment overlaps is then O(n).
So is the overall complexity O(n^2 log(n)) ? If it is, the O(n^2) algorithm is better. Or can we sort the y-coordinates too and somehow get O(n log(n)) complexity?

Is anyone aware of computational geometry work along these lines -- either to invert similar algorithms, or to prove that the fundamental complexity of the problem is higher?

[Edited by - Emergent on July 30, 2010 8:43:10 PM]

Quote:

Original post by Emergent I wonder; are there any sweepline-style algorithms for this?

The convex polygons are "solids". If convex polygon A is strictly contained in convex polygon B, then Intersection(A,B) = A, even though the polygon edges do not intersect. Your sweepline idea will need additional logic to make it work for this problem.

I may be totally off so if so please ignore this but...

If you knew that most of the time there would NOT be an intersection between all of the polygons, you could run the SAT to test if there was any shape that didn't overlap one of the other shapes.

If this is true, you could early out saying that since there exist at least 2 shapes that in no way overlap, that the intersection of all the shapes is empty.

You may also be able to calculate or store some useful info along the way while doing the SAT tests that may help you in the 2nd stage so it isn't just completely wasted effort.

Actually, I think a sweep-line algorithm would work well here. Maintain a list of segments intersecting the sweep line, along with how many polygons intersect the sweep line in the interval between each intersection. If any of those intervals goes up to the total number of polygons, you have your intersection point.

maybe you are looking for this paper:
M. Reichling. "On the detection of a common intersection of k convex objects in the plane". Inform. Process. Lett., 29:25-29, 1988.

It would (I say "would" because it's just an idea, not tested, so I may be totally off [embarrass]) also be possible to find explicitly the intersection in O(n*log(n)) where n is the total number of vertices:

It's looks like merge sort algorithm [smile]

I just had this idea, so I'm not sure it will work:

Each convex polygon can be described by the intersection of a set of half spaces (linear inequalities), and so the intersection of all those convex polygons will still be the intersection of a set of halfspaces, which means they intersect iff the resulting system has a solution. So to find out if they do, it's enough to find a single point that satisfies all inequalities.

So this already does sound pretty similar to linear programming:).

Now I think you can find a point in the intersection region as follows:
1. Pick any vertex from one of the polygons as your start point.
2. Move the point over one of it's adjacent lines, so that it stays on the positive side of the other adjacent line.
3. When the point hits any other line from it's front side, you stop
4. You take the direction of this new line as next direction, again so that you stay on the positive side of the previous line).
5. Go back to step 3

Now there are two cases:
- Either it spirals into the region where it's inside all polygons
- It keeps cycling, which means there's no solution.

It shouldn't be too hard to detect either case, so this should answer your question.

An easy way to implement this might be to use a matrix similar to the one used in linear programming, combined with it's pivoting rule.

[Edited by - quasar3d on August 2, 2010 5:14:22 PM]

knighty and quasar3d FTW!

quasar3d's point really needed to be made, and I'm kind of annoyed at myself for missing it. Yes, the union of several convex sets is not necessarily convex, but we don't care, since nilkn wanted the intersection! We've had a convex problem all along! Awesome, quasar3d.

And then knighty's algorithm (which is so very close to the O(n log(n)) divide-and-conquer halfplane-intersection algorithm -- and this ties back in to quasar3d's point) solves this pretty conclusively, I think.

Nice.