Re: Proceeding apace...
On Fri, 24 Mar 2000 00:00:29 -0500, Matthew Lewis
<MatthewL at KAPCOUSA.COM> wrote:
>Funny you should ask. I was working on this problem a while ago (had to
>write something in Visual Basic, tho). I came up with an algorithm that
>worked (fast enough for what I needed, but doesn't really touch the speed or
>elegance fo this), but then I found this on the web:
[code snip]
>The heuristics of the test are as follows:
>Draw a ray from the point in some direction. Then count the number of
>intersections with the polygon. Even means you're outside, odd means you're
>inside. This one works for all sorts of polygons. The web reference has
>some more detail on the mathematics. There are other references out on the
>web for more well behaved polygons (regular, convex, etc), but this routine
>will work with arbitrary shapes.
[code snip]
This is the so-called "winding number" algorithm, and you _can't_
start from an "arbitrary" point; you have to know whether the
starting point in question is inside or outside the shape (which
can actually be arranged in most cases, by starting outside the
shape's bounding box, guaranteeing that you are starting outside
the shape). It also has a problem with self-intersecting shapes,
and with overlapping shapes drawn in the same color.
--
Jeff Zeitlin
jzeitlin at cyburban.com
|
Not Categorized, Please Help
|
|
