Re: geometric utilities

[mikeg2@my-dejanews.com]

Probably to my detriment, I've continued to try variations rather
than post what I've got so far - but, I'm really starting to
wonder if the algorithm actually works in all cases.

First, I think the lp.p1 := p[i] and lp.p2 := p[i] on line 10 (I
think that's where it was) is intentional per the text - i.e., ignore
*points* that are on the test line.  As it turns out, the intersect
procedure provided in the book doesn't appear to work in this case
(i.e., a point and a line) maybe because my stuff is floating point.
At any rate, I fixed this so that my code does properly detect
intersection of the test line with the ith point.

Using polygon ((1.0, 0.0), (0.0, 1.0), (-1.0, 0.0), (0.0, -1.0))
(a square around 0.0 on a 45 degree angle), and test point (0.0, 0.9),
the algorithm just doesn't seem to work, even when I do it by hand.
Maybe has something to do with j happening to start out at point
3 since point 4 passes the anchor rule (smallest x coordinate among
points with smallest y coordinate).  Point 3 happens to be collinear
with the test line...

Tomorrow I will post my code (not trying to be coy, I just have no way
here at home to get it from my laptop to my PC) - but was hoping in the
meantime someone might have taken a good look at the algorithm.  I did,
by the way, check with Addison Wesley for an errata sheet and sent a
note to Dr. Sedgewick to see if per chance there was a known problem
with the algorithm - but couldn't find anything and haven't yet heard
back from the good Doctor.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading