Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!pacbell.com!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: <6140@crash.cts.com>
Date: 7 Dec 90 02:06:57 GMT
References: <111@gem.stack.urc.tue.nl> <6080@crash.cts.com> <11695@alice.att.com>
Organization: Crash TimeSharing, El Cajon, CA
Lines: 19

In <11695@alice.att.com> td@alice.att.com (Tom Duff) writes:

[stuff deleted]

>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.

  The Sutherland-Hodgman algorithm will clip any polygon (convex or
concave) to any convex polygon. It's really simple to code, and can
also be used as the primary 2D or 3D screen clipper. But, doing a
pointwise compare (using cross products or winding points algorithms),
of points in a polygon will probably be faster. But, if you're out for
speed, skip this step, or if you have a fast polygon machine, use a BSP
(or if objects are moving, use BSPs for each object, then sort the objects).


  John


Brought to you by Super Global Mega Corp .com