Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!mcvax!unido!uklirb!mdoerr
From: mdoerr@uklirb.UUCP
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited... - (nf)
Message-ID: <23800003@uklirb.UUCP>
Date: Thu, 25-Jun-87 06:14:00 EDT
Article-I.D.: uklirb.23800003
Posted: Thu Jun 25 06:14:00 1987
Date-Received: Sat, 27-Jun-87 06:59:07 EDT
References: <948@elrond.UUCP>
Lines: 50
Nf-ID: #R:elrond:-94800:uklirb:23800003:000:2292
Nf-From: uklirb!mdoerr    Jun 25 11:14:00 1987

/***** uklirb:comp.graph / elrond!amamaral /  9:17 pm  Jun 15, 1987*/
In article <948@elrond.CalComp.COM>, amamaral@elrond.CalComp.COM (Alan Amaral) writes:
> 
> A while ago someone asked for a method for determining whether or not
> a point was inside or outside of a polygon.  I have the replies, and
> am in the process of implementing just such a function, but have come
> up against what I view as a significant problem.
> 

I forgot to say in that last message that I am working in 3 space, so the
concepts of local minima and maxima are not as straight forward as in 2 space.
(are they?) I have been working on this particular problem on and off for a
while now, with no luck.

Thanks for any help...


-- 
uucp:	 ...decvax!elrond!amamaral		I would rather be a
phone:	 (603) 885-8075				fool than a king...
us mail: Calcomp/Sanders DPD (PTP2-2D01)
	 Hudson NH 	03051-0908
/* ---------- */

While researching the literature for clipping algorithms (concave 2D-polys with
holes against concave 2D-polys with holes) I found the following paper that
might be of help to you:
Yehuda E. Kalay: Determining the Spatial Containment of a Point in 
General Polyhedra, Computer Graphics and Image Processing, Vol. 19,
pp. 303-334, 1982
He first introduces a 2D-point-inside-polygon-test that is suitable for
concave polygons with holes. Then he extends that algorithm to 3D by reducing
the 3D problem in two different ways to the 2D case. This isn't as straight
forward as it may sound. His 2D test is similiar to the solution proposed
by Ed Post (hplabs!lewey!evp) in this news group.

Hope this helps ...

BTW: Has anyone REALLY UNDERSTOOD how Weiler's polygon comparision algorithm
works? (see K. Weiler: Polygon Comparison using a Graph Representation,
SIGGRAPH-80 proceedings in Computer Graphics, Vol. 14, pp. 10-18, 1980)
I've understood the overall concept, but those difficult details have 
confused me as much as a potion of confusion :-) Who could enlighten me?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Michael "The Turtle" Doerr			%% /-------\ %%
CS Department (FB Informatik)			  %  o   o  %
University of Kaiserslautern			-{ o   o   o }==O
D-6750 Kaiserslautern (West Germany)		  %  o   o  %
uucp: ...!seismo!unido!uklirb!mdoerr		%% \-------/ %%