🚀 go-pugleaf

In article <cscoging.3.717415284@unpcs1.cs.unp.ac.za>, cscoging@unpcs1.cs.unp.ac.za (Chris Scogings) writes:
|> I've been away and missed the first part of this discussion.  I would be 
|> most obliged if someone could mention some references in this area.

Some references:

"Computational Geometry" by Preparata & Shamos
"Interactive Computer Graphics" by Giloi
"An Introduction to Solid Modeling" by Mantyla
"Computer Graphics: principles and practice" by Foley, van Dam, Feiner, & Hughes

|> Why
|> can't we find a better algorithm than shooting rays all over the place?

I've only run across 3 ways to do the point-in-polygon test: 1) shoot a ray and
count crossings, 2) traverse the boundary of the polygon summing the signed
angles subtended by each segment with respect to the point, if the total angle
is non-zero then the point is inside, 3) represent polygons by a boolean sum of
half-planes, plug the point into the line equations (i.e. ax+by+c) for the half
plane boundaries, if the result is negative (assuming outward pointing normals)
for all of the half planes in any of the polygon's convex subregions then the
point is inside.

3) leads to the simplest code *if* you have your polygons represented as
boolean sums of half-planes and *if* you consider a point on the boundary to be
inside the polygon (if points on the border are considered outside you have to
do some non-trivial special case coding). 2) is generally thought to be the
slowest of the methods.  1) is the most common method but there are some
subtleties to coding an efficient and clean implementation.

In 3), for concave polygons, you don't always have to test all of the
planes making up the polygon, but you could decompose your polygons
into convex sub-polygons for the other 2 methods, which would negate
that advantage.

If you are doing this in floating point and you have no fpu then 1) is probably
faster than 3) since for the most part you are just doing comparisons instead
of floating point multiplications. The tricky part about 1) is when your ray
passes through a vertex of the polygon. The brute force approach (metioned in
all the references) is to pick another ray and try again. Alternatively, if you
are at an edge whose endpoint lies on the ray you can look for the next edge
not parallel to the ray and see if it is on the other side of the ray. This
leads to some very messy special case code. There is a way to implement 1)
cleanly: don't count any edge parallel to the ray, and of those edges with one
endpoint on the ray, only count the ones that lie on a particular (arbitrarily
chosen) side of the ray. Doing 1) this way my code consists of 2 routines
totalling about 40 lines.

Larry Edwards
edwards@sunrise.stanford.edu