Polygon analysis - insight requested

[EagleKeeper]

I have two polygons and need to determine if they intersect.

In a nutshell the original algorithm

Check if Poly1 encompasses Poly2 - Yes Returns TRUE
Check if Poly2 encompasses Poly1 - Yes Returns TRUE


Loop over Poly1 sides checking if intersecting anything in Poly2 - Yes Returns TRUE


A rare exception based on alignment of the objects on the display can cause a failure (intersection) when the algorithm tests for enclosure.

What are recommendations for efficient processing algorithms to use. This is in a high use execution code block - embedded avionics system in C.

Thanks

 

[tatteredpotato]

There's probably a lot of material on this in Gaming/Graphics books.

 

[eLiu]

"A rare exception based on alignment of the objects on the display can cause a failure (intersection) when the algorithm tests for enclosure."

Can you elaborate on that? I don't understand what you're saying here...'

Also are the polygons convex?

 

[Kirby]

if they're convex you could use the separating axis theorem i think

 

[EagleKeeper]

Think of Poly1 being the outline of a octogon (sides are not equal) Example: a congressional gerrymangered district. Lines connected, but all over the place.
Poly1 does not have to be convex.

Poly2 is always the outline of a rectangle.


I need to know if the octogon (congressional district) is inside the rectangle
I need to know if the rectangle is inside the octogon.

I need to know if the rectangle intersects the octogon.

The position of the two polygons are constant in relation to each other;however they can also rotate around any axis.

The existing algorithm to test if one is inside the other, draws an imaginary line from a corner from Poly1 to the corner of the screen. A check is made if the line intersects Poly2. If so are the number of intersections odd/even. If odd, the assumption is that the poly is inside the other - the line is crossing the boundary. If even, the line passes in one edge and out another edge - not inside.

What is happening is that a corner point of Poly2 is being clipped, returning an intersection count of 1.

 

[eLiu]

Oh I see what you mean now (I think). To solve the issue, you could cast 2 more lines, each offset some small angle from the original line (so one line +delta degrees clockwise & another +delta degrees counterclockwise). One of those lines will be far enough from the corner if you pick delta appropriately. This is of course still not perfect.

I think a better approach is to do something like... if the intersection point is determined to be very close to the endpoint of a line segment (if you know 2 segments intersect, it's trivial to find the location), then explicitly check whether every point of poly1 is on the interior of poly2 (or vice versa). In this way you only do extra work on the 'dangerous' cases where you might be having this clipping issue.

Non-convex polygons suck. To solve the intersection problem, I can think of a few choices.
1) Triangulate the octagon (delaunay comes to mind). With a very small # of checks you should be able to determine whether a triangle intersects a rectangle and perform this check on each triangle.
2) Decompose the octagon into convex polygons. Chazelle proposed a polynomial time algorithm for finding the minimal number of convex components some years ago. I have no idea how this performs in practice though. Anyway, once you have convex polygons, you can use the theorem nkgreen was referring to (which is why I asked about convexity in the first place).
3) The above two options might be too costly since an octagon isn't so big. Another possibility is to consider a line-segment intersection problem. Throw in all 12 edges as line-segments & apply a sweep-line algorithm. (If you don't know what that is, google around or find a book on computational geometry; it's a classic example.) You can do some pruning b/c you know a priori that the octagon edges don't intersect each other (same for rectangle), etc. This should be cheaper than checking all pairs (well I dunno how you're doing it right now), but maybe not cheap enough to be worth the effort.

 

[EagleKeeper]

Thanks eLiu

Youi gave me an idea.

When there is an reported intersection; I can find the segment that it is on and then check against the opposing poly sides for truthfullness.

I will also do some digging on the web.

Anyone else that has ideas and can point me onward, please do so.

 

[KIAman]

I've never worked with polygon analysis before but if I were given this as an assignment, I would try the following.

Make 2D int arrays that represent poly1, poly2 and environment.

Use a polygon area filling algorithm (I have no clue how fast these are) then fill the respective 2D arrays representing poly1 and poly2.

Assign the environment array value of 0.

Assign each "dot" of poly1 a value of +2 and each "dot" of poly2 a value of -1 and the empty space of 0.

Then you can interpolate both arrays into the environment array.

Search environment array.

If any value returned = 1, that means an intersection happened.
If any value returned = 2 and 1, that means poly1 does not encompass poly2
If any value returned = -1 and 1, that means poly2 does not encompass poly1.

Downfall will be resolution of the respective 2D arrays (and the speed of polygon area fill).