🚀 go-pugleaf

In article <1992Sep27.001515.28523@leland.Stanford.EDU>, ledwards@leland.Stanford.EDU (Laurence James Edwards) writes:
|> 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?
|> 
|> [.......]
|> 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.
|> [......]
|> 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
|> [.......]

Oops, actually Preparata&Shamos mention the clean way ... it's been a while
since I looked at that book.

Preparata&Shamos also show that with preprocessed convex or star shaped
polygons the test is O(log n) ... Eric Wong also mentions this in article 4643.
The preprocessing is basically sorting and is O(n) ... you can sort by angle
or by position ... in one case you do a binary search to a particular wedge, in
the other you binary search to a trapezoidal strip. Sorting by angles is
probably preferable since then the final test (once you have it narrowed
down to a particular wedge) is faster.

Wow! I had forgotten what a godly book Preparata&Shamos is.

Larry Edwards
edwards@sunrise.stanford.edu