Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!columbia!rutgers!sri-spam!sri-unix!hplabs!hao!noao!arizona!megaron!johnk
From: johnk@megaron.UUCP
Newsgroups: sci.math
Subject: Re: point inside a polygon (triangl
Message-ID: <1276@megaron.UUCP>
Date: Mon, 3-Nov-86 11:42:16 EST
Article-I.D.: megaron.1276
Posted: Mon Nov  3 11:42:16 1986
Date-Received: Tue, 4-Nov-86 08:38:04 EST
References: <1482@jade.BERKELEY.EDU> <8900037@osiris> <5299@dartvax.UUCP> <1284@ttrdc.UUCP>
Organization: Dept of CS, U of Arizona, Tucson
Lines: 30

> In article <5299@dartvax.UUCP>, kevins@dartvax.UUCP (Kevin M. Schofield) writes:
> >In article <8900037@osiris> kaden@osiris.CSO.UIUC.EDU writes:
> >>	   Count Vector on Sesame Street says: I love watching
> >>	   the ray crossing the curve and creating either an
> >>	   odd or even number of intersection points that I
> >>	   may count! Very splendid! Very splendid! HA! HA!
> >
> >Close, but not quite. You get a nasty exception to the rule when your
> >ray hits a vertex of the polygon. 
> 
> So what?  Perturb the ray a little to get it off of the vertex and try again.

This method of counting intersections is based, I believe, on the Jordan
Curve Theorem.  It *doesn't* break down for a ray intersecting a vertex.
Your intersection algorithm, upon encountering an intersecting vertex,
must distinguish whether or not the slope of the contour changes sign
at the vertex.  If the sign indeed changes, count the intersection twice
or not at all, depending on whether you think the glass is half full,
or half empty; otherwise, count the intersection once.

This points out the difficulties (which are rarely appreciated) in
actually implementing an algorithm from computational geometry.  Often
the algorithm does not address certain critical boundary cases, such
as vertical lines, overlapping line segments, etc.  The paper in which
the algorithm is described often deals with all these cases at once
with something like ``perturb the point set through a small rotation
epsilon ....''
-- 
John Kececioglu / arizona!johnk
"Chess, like love, like music, has the power to make men happy." -- S. Tarrasch