Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!husc6!linus!raybed2!applicon!bambi!garrity!garrity
From: garrity@garrity.UUCP
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited..
Message-ID: <31500005@garrity>
Date: Wed, 17-Jun-87 09:07:00 EDT
Article-I.D.: garrity.31500005
Posted: Wed Jun 17 09:07:00 1987
Date-Received: Sat, 20-Jun-87 07:04:32 EDT
References: <948@elrond.CalComp.COM>
Lines: 28
Nf-ID: #R:elrond.CalComp.COM:-94800:garrity:31500005:000:1278
Nf-From: garrity.applicon.UUCP!garrity    Jun 17 09:07:00 1987


> Has anyone solved this particular problem, or do you just ignore it?
> I have tried all sorts of schemes to work around this particular problem,
> but have always been able to come up with some kind of pathological case
> where a concave polygon will fail.

  Yes, we encountered it.  Someone here came up with a solution which works 
quite well.  When the ray intersects a vertex of the line (i.e. the parameter
of the intersection is 0 or 1), then "tweak" the ray to one side.  This means
that you offset the ray by a "small" amount to one side.  You must be 
consistent about which side you tweak to.  You then recompute the intersection.
This seems to work in all cases.  In fact, since our implementation worked 
with things other than lines (arcs, B-splines, etc.) I happen to know that it
works in the nasty case where the ray goes through the start-end vertex of a
circle.  Hope this helps.


--                                                          -MPG-
-- Mike Garrity
--
--
-- snail: Applicon, a division of Schlumberger Systems, Inc.
--        829 Middlesex Tpk.
--        P.O. box 7004
--        Billerica MA, 01821
--
-- uucp: {allegra|decvax|mit-eddie|utzoo}!linus!raybed2!applicon!garrity
--       {amd|bbncca|cbosgd|wjh12|ihnp4|yale}!ima!applicon!garrity