Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!orion.oac.uci.edu!ucivax!ucla-cs!twinsun!rusmin
From: rusmin@twinsun.com (Rusmin Dirgantoro)
Newsgroups: comp.graphics
Subject: Re: Point in Polygon Problem
Message-ID: <1990Aug24.014840.18610@twinsun.com>
Date: 24 Aug 90 01:48:40 GMT
References: <2034@idunno.Princeton.EDU> <1990Aug23.174650.3592@odin.corp.sgi.com> <1990Aug23.181401.2258@jarvis.csri.toronto.edu>
Sender: usenet@twinsun.com
Distribution: comp.graphics
Organization: Twin Sun, Inc
Lines: 46

In article <1990Aug23.181401.2258@jarvis.csri.toronto.edu> corkum@csri.toronto.edu (Brent Thomas Corkum) writes:
>
>There's one question I have concerning this algorithm that I hope someone
>can answer. It seems to me that a point exactly on an edge can evaluate
>either inside or outside depending on which edge your on.
>ie.
>        +----A----+
>        |         |
>        |         |
>        +----B----+
>Using the algorithm I've seen, A would evaluate inside and B outside. Is
>there a quick and dirty way to handle points exactly on edges? I realize
>that a seperate calculation can be done to determine whether a point
>is on a line but this is expensive computationally isn't it?

I'm not sure what you mean by 'handle'.
But.. if I'm allowed to add something here, I believe this would lead to
a discussion of PMC (Point Membership Classification), a classic issue
in Geometric Modeling.

Points on boundaries (here, edges) always have two neighborhoods,
inside the object (here, polygon) and outside. For this reason people
give points on boundaries *ON* classification, not *IN* nor *OUT*.

Ex:
    In your problem..
	A has *IN* neighborhood *BELOW* and *OUT* neighborhood *ABOVE*.
	B has *IN* neighborhood *ABOVE* and *OUT* neighborhood *BELOW*.
    So, both A & B have *ON* classification.

Since we ought to pick either above or below on the ray (re: Eric/Mark's
algorithm), the algorithm doesn't explore enough information for points 
with *ON* classification. It was meant to decide only either *IN* or *OUT*.
That's why the algorithm could give different answers for *ON* points.
What do you think Eric? Mark?

Sorry, I am not answering your questions..
just sharing a little old idea.

G'day..


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