Xref: utzoo comp.graphics:1818 comp.sys.ibm.pc:12485
Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!lll-tis!ames!hao!oddjob!uwvax!speedy!planting
From: planting@speedy.cs.wisc.edu (W. Harry Plantinga)
Newsgroups: comp.graphics,comp.sys.ibm.pc
Subject: Re: point-in-polygon again
Message-ID: <5305@spool.cs.wisc.edu>
Date: 26 Feb 88 20:16:48 GMT
References: <971@ut-emx.UUCP> <20533@amdcad.AMD.COM> <7626@pur-ee.UUCP>
Sender: news@spool.cs.wisc.edu
Reply-To: planting@speedy.cs.wisc.edu (W. Harry Plantinga)
Distribution: na
Organization: U of Wisconsin CS Dept
Lines: 25
Keywords: READ THIS ONLY IF YOUR IQ <<125
Summary: posted solution assumes convexity

In article <7626@pur-ee.UUCP> beatyr@pur-ee.UUCP (Robert Beaty) writes:
>In article <20533@amdcad.AMD.COM> msprick@amdcad.UUCP (Rick Dorris) writes:
>>In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC) writes:
>>>Have a nice one here:
>>>Have a boundary defined on the screen. Boundary is composed of points
>>>joined by lines... Now some random points are generated and I want to check
>>>if a given point is within or outside the existing boundary.. Any algorithm for
>> <rick suggests the infinite ray/intersection counting algorithm>
>
>I have seen this type of algorithm before and the one I thought up
>in an afternoon is FAR surperior and vastly simpler to code up.
>
><robert beaty suggests an algorithm that measures sums the angles of
>the lines connecting the poitns and the test point>

Haven't I seen this discussion of point-in-polygon algorithms about 15
times before? :-)

Robert, your algorithm is simpler only in the kind of problems it
handles.  It will only work for convex polygons, whereas the other
works for any polygons.  It's not even much simpler; measuring angles
and determining whether line segments intersect are of comparable
difficulty.

Maybe you should have said that althogh your algorithm is far
inferior, it's not any easier to code?