[gameprogrammer] Vector graphics filling woes

Heya,

I've been struggling w/ a problem for a while and am not getting
anywhere so I'm posting it to the list in hopes that someone can help.

The problem I'm having is that I have a lot of line data in the form
of 2d line segments like this...

Line 0 has 5 verts
V1 = 3,5
V2 = 6,7
V3 = 10,10
V4 = 0,0
V5 = 50,-20

Line 1 has 2 verts
V1 = 0,0
V2 = 24,25

Line m has n verts
...
(etc)

What i'm trying to do is if I'm given a point (such as 5,5), I want to
find the outline of the shape that encloses that point (if there is
such a shape).

All this line data is in memory and is generated by the end user...



Here's the best I've been able come up with so far but it's not quite
there yet...

A) I know the bounding box of the line data so i shoot a horizontal or
vertical line to the nearest edge of the bounding box (to hopefully
minimize false positives), and i find the line segment that collides
with that line, that is closest to the fill origin.

B) From there i look to see which side of the line segment is closer
to the fill point, either the low numbered side or the high number
side and at this point call a recursive function to search the lower
side and if that side fails, call the recursive function to search the
higher side.

C) What the recursive function does is iterate down the line segment
until any of a couple of things happen...
1) The end of the line segment is reached which means it failed and it
returns false
2) The starting point is reached again, which means it succeeded and
it returns true
3) An intersection is reached.

D) When an intersection is reached it has 3 possible paths that it can
choose from, so what it does is calculate the distance that the next
segment on each path lies from the fill origin, and it recurses to the
closest one, and if that fails, to the next closest one, and if that
fails, to the farthest one.


Upon success, as the function is uncoiling the recursion, I have it
store the vertex information in a buffer so that the outline can be
known and then the fun part happens where another function breaks that
outline into triangle fans and actually fills it in.

Sheesh!

The above algorithm isn't working for me and i don't know if it's
because i'm forgetting some important case or because i didn't
implement it correctly (it's alot more code than you would think to do
this!!!).

Does it sound solid? Is there any easier way?

BTW i don't have access to the pixels directly so i can't do scaline
conversions, i have to come up with geometry to fill it ):

Thanks so much for any help!
Alan

---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html

Other related posts: