/***** uklirb:comp.graph / elrond!amamaral / 9:17 pm Jun 15, 1987*/

> 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.

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 %% \-------/ %%