Method to calculate the intersection of two quadrilaterals? [duplicate]

Question

Possible Duplicate:
A simple algorithm for polygon intersection

I'm looking for an outline on how to quickly calculate the intersection of two arbitrarily oriented quadrilaterals (no preset corner angle or side length constraints). I am not looking to simply check whether they intersect, but wish to get the points making up the resulting intersecting region. I know that in general polygon intersection isn't a trivial problem and there are libraries available that do a good job.

But since in this special case where I'm only concerned with four sided shapes, I was wondering if there was a quick method I could use without including an entire additional library in my application.

So far all I've thought of is:

1. Run 'point in polygon' on both shapes with respect to each other
2. Intersect each edge of each polygon with each other

Do the above two steps definitively get me all the points that make up the resulting intersection region? Is there a better method to use?

Also it would be nice if I could get the correct ordering of the points that make up the resulting region. It's not mandatory -- if you are aware of any clever/quick ways of doing this bit (convex hull?) I'd appreciate any suggestions.

Answer 1

You didn't state wether the 2 quadriliterals are convex or not; if they are, you could use a regular convex polygon intersection algorithm such as http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

From what I can gather, it doesn't require any exotic datastructures or operations, so it shouldn't be difficult to implement.

Answer 2

Intersection of convex polygons is relatively easy. Google it, there's a lot of resources both on SO and elsewhere.

Not all quadrilaterals are convex though. Intersection of two non-convex quadrilaterals can result in several disconnected polygons, having just their points will give you very little, but if that's what you need go ahead and intersect each pair of edges. It will be much easier and faster than any general method

Even for convex shapes, the dumb brute-force method may be faster. You have to do some testing to find out what works best for you.