Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!rpi!bu.edu!att!att!dptg!ulysses!andante!alice!td
From: td@alice.att.com (Tom Duff)
Newsgroups: comp.graphics
Subject: Re: checking whether 2 2D polygons overlap
Summary: simple algorithm
Keywords: polygon overlap 2D
Message-ID: <11695@alice.att.com>
Date: 5 Dec 90 13:57:01 GMT
References: <111@gem.stack.urc.tue.nl> <6080@crash.cts.com>
Organization: AT&T Bell Laboratories, Murray Hill NJ
Lines: 19

Checking two polygons for overlap is fairly easy:
either some edge of one polygon crosses an edge of the other,
or one of the polygons is completely contained within the other.

You can check for containment by picking a single vertex of each
polygon and checking it for containment in the other.  (You
know how to do this, right?  If not, check the FAQs.)  If these
tests fail, you can just test each pair of edges for intersection.
The obvious method of doing this takes time proportional to n^2.
Since two polygons can intersect in O(n^2) points, you probably
can't do better than this, worst case.

Of course, as has been already pointed out, a bounding box cull
will usually save much work.

The previous posting that suggested using a general polygon clipper
(like Weiler-Atherton) to test for overlap was overkill.  It's
Very Hard to get Weiler-Atherton to work properly; it's dead easy
to check polygons for overlap.


Brought to you by Super Global Mega Corp .com