Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!jarthur!ucivax!ucla-cs!twinsun!rusmin
From: rusmin@twinsun.com (Rusmin Dirgantoro)
Newsgroups: comp.graphics
Subject: Re: Point in Polygon Problem
Message-ID: <1990Aug22.022743.4139@twinsun.com>
Date: 22 Aug 90 02:27:43 GMT
References: <5990@milton.u.washington.edu>
Sender: usenet@twinsun.com
Distribution: comp.graphics
Organization: Twin Sun, Inc
Lines: 68

In article <5990@milton.u.washington.edu> benson@blake.acs.washington.edu (Dan Benson) writes:
>I know this has been asked before but I missed the answers.  I want to
>know the best way to determine whether a point is inside of a polygon
>where the polygon is represented as a set of ordered floating point
>numbers (its boundary).  I'm actually using 3D points but the polygons
>are defined on 2D planes.  Also, the polygons can be any shape, concave,
>convex.

First of all, I missed the answers of previous postings as well.
So.. this idea I'm posting might not be new to you guys.

I was working on something like this some time ago for my Geometric
Modeling class. The idea I was using was adapted from some good
articles of some journals. I don't remember the exact name and date of
the journals by heart.

The idea is..
	0. Assume your polygon is PG and your point is PT.
	1. Create a coordinate frame CF, where the XY plane is the plane
	   of PG. We'll be working with this coordinate system from now on.
	2. Transform PT's coordinate into CF coordinate, say we get (CF)PT.
	3. If (CF)PTz != 0, PT IS OUTSIDE PG; DONE.
	   If (CF)PTz == 0, PT may be inside PG; continue step 4.
	4. Transform PG's boundary (the set of ordered points) into CF
	   coordinates. The points should then have Z == 0, of course.
	5. Build segment equations S1..Sn for each segment on the boundary.
	   S1..Sn are line eqs with endpoints. They don't go from/to 
	   infinity. S1..Sn are based on CF coordinate system, so they
	   are simply 2D-eqs since we don't care about Z anymore
	   (Z is always 0).
	6. Build a random (yes, random) ray equation R. R starts from
	   (CF)PT to infinity. R is on the XY plane of CF. Again,
	   we don't care about Z anymore.
	7. Find intersections between R and S1..Sn. Say the number of
	   intersections is NI.
	8. If NI is even or zero, PT IS OUTSIDE PG; DONE.
	   If NI is odd, PT IS INSIDE PG; DONE.

Please note here that there's a very special case, that is..
	Somehow R intersects any of the ordered points (the corners of PG),
	so step 8 won't necessary give the right answer.
One of the solutions for this special case is..
	Add step 7 with:
	  When intersecting R with S1..Sn,
	    if R intersects Si at an Si's endpoint, back to step 6
	    (try another random R).
This solution may look dumb to you. But.. believe me..
it works just fine.

Here, I assume we are all aware of computation errors, such as round-up
errors, floating point errors, etc. So appropiate floating point
comparisons should be applied.

Of course there are many other ideas on this problem.
I'd like to hear them as well.

BTW, I'm sure I still have some piece of code doing this problem.
And I still have hardcopies of the articles I mentioned above.
If anyone is desperate, I'm willing to search those resources in my
hayestacks. Just let me know.

Ciao.

--
--
Rusmin Dirgantoro                     rusmin@twinsun.com
Twin Sun Inc.                         1(213)640-6885 voice
El Segundo, California                ---