Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!samsung!uunet!jarthur!ucivax!orion.oac.uci.edu!ucsd!nosc!crash!jcs
From: jcs@crash.cts.com (John Schultz)
Newsgroups: comp.graphics
Subject: Re: checking whether 2 2D polygons overlap
Keywords: polygon overlap 2D
Message-ID: <6080@crash.cts.com>
Date: 4 Dec 90 19:04:20 GMT
References: <111@gem.stack.urc.tue.nl>
Organization: Crash TimeSharing, El Cajon, CA
Lines: 30

In <111@gem.stack.urc.tue.nl> hugo@gem.stack.urc.tue.nl (Hugo Lyppens) writes:


>I've partly implemented the Newell-Newell-Sancha hidden surface algorithm on the Amiga for a real-time 3D animation package I've written. This algorithm is also known as the Painter's algorithm, for it establishes a priority list and draws polygons from the back to the front.

>The program allows scenes composed of planar polygons which have no holes. I 
>don't however get perfect results because there's one step in the algorithm I
> don't know how to implement: to check if the projections of two polygons on 
>the screen overlap or not. I haven't been able to find an article on this 
>subject, not even in articles from the authors of the painter's algorithm
>themselves!

>So please could anyone help me with some hints or source code to determine QUICKLY whether two 2D polygons overlap or not? Then I'll be able to implement the algorithm completely.

  Two steps: Check to see if their extents overlap (minX,maxX,minY,maxY of
the polygon). This step requires only boolean comparisons. You can compute
the extents in your 2D clipping code. If you're in for speed, this step
may be all you need.
  The next step, if the extents overlap, is to find out if the polygons
actually overlap. One way is to use a clipping algorithm to clip one
polygon against another (Instead of clipping against a rectangle, clip
against a polygon. Most screen clippers are just special case clippers
for rectangles). You might also be able to analyze the relationship
between the area of the extent of *both* polygons and the areas of each
polygon within that extent (overlapping polygons will have less area than
non-overlapping polygons).


  John
 


Brought to you by Super Global Mega Corp .com