Point inside of polygon revisited... - (nf)

Point inside of polygon revisited... - (nf)

Post by mdo.. » Sat, 02 Jun 1990 07:14:00



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

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

 
 
 

1. Point inside of polygon revisited...

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.

To recap, the theorum put forth was that given a bounded area on a plane
and a point on the plane, one could determine whether the point was inside
the area, or outside the area by determining how many edges an arbitrary
ray starting at the given point crossed. (and a partridge in a pear tree...)
If the ray crossed an even number of edges, then the point is outside of the
area, and it's inside if the number of crossings is odd.

This all works well and good, EXCEPT for one particular case. What if the
ray happens to cross 2 edges at exactly the same point (i.e. at a corner)?
Take the two following cases:

                       +
                      /|
                   1 / |
                    /  |
                   /   |
          <-------+--x | 3
                   \   |
                    \  |
                   2 \ |
                      \|
                       +

Intersection point (x) is inside of the bounded area, but there are 2 crossings.
You could count only 1 crossing at a corner (i.e. crossing is only valid if edge
T value is 0 < T <= 1) but that fails in the next case:

            <-----+--------x
                  |\
                  | \
                 1|  \2
                  |   \
                  +----+
                     3

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.

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

2. Field connections to SoSFPlane

3. ? Algorithm for decision wheher a point is inside polygon or outside polygon

4. 3d-animatieproject

5. Point inside a polygon 3D

6. To hole background

7. fast random point inside closed polygon

8. new version, convex hull/Delaunay/Voronoi

9. Is a point inside a polygon

10. point inside a polygon?

11. Algorithm needed to determine if a point is inside a polygon

12. Help: Is a point inside a polygon?

13. looking for way to find all points inside polygon