3

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.

Community
  • 1
  • 1
Prismatic
  • 3,338
  • 5
  • 36
  • 59
  • Quadrilaterals are a special case (IIRC you can always divide them into two triangles, even when concave) so a generic algorithm may be overkill. – MSalters Oct 30 '12 at 07:34
  • Note that the result will not necessarily be a quadrilateral. If the inputs are non-convex you may get two non-connected quadrilaterals as the result. If they are convex you may still get a hexagon as the result. – finnw Oct 30 '12 at 08:52

2 Answers2

4

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.

Leon Bouquiet
  • 4,159
  • 3
  • 25
  • 36
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.

n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243