From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,a9517107ce472fc7 X-Google-Attributes: gid103376,public From: mikeg2@my-dejanews.com Subject: Re: geometric utilities Date: 1998/06/05 Message-ID: <6l7roc$h2l$1@nnrp1.dejanews.com>#1/1 X-Deja-AN: 359701210 References: <6l6ihi$ivh$1@nnrp1.dejanews.com> X-Http-User-Agent: Mozilla/3.0 (Win95; U) Organization: Deja News - The Leader in Internet Discussion X-Article-Creation-Date: Fri Jun 05 04:21:33 1998 GMT Newsgroups: comp.lang.ada Date: 1998-06-05T00:00:00+00:00 List-Id: 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