1. Proceeding apace...
- Posted by Jeff Zeitlin <jzeitlin at CYBURBAN.COM> Mar 23, 2000
- 565 views
... but still getting stuck on issues with the fill routine. What I need now is a way to unambiguously determine a point which lies within the shape that is being drawn, so that the fill routine can be used. Every intuitive method I've come up with, I've been able to draw a figure that breaks the rule. There's also another problem I can see coming down the line, but I'll stumble over that rock when I come to it. (Rob, why didn't you just build in the routines with the Linux implementation, like you did with the mouse?) -- Jeff Zeitlin jzeitlin at cyburban.com
2. Re: Proceeding apace...
- Posted by simulat <simulat at INTERGATE.BC.CA> Mar 23, 2000
- 542 views
> ... but still getting stuck on issues with the fill routine. Hi Jeff This is pretty vague, but I remember some sort of odd/even rule that was used for fills: Start at the screen edge at the top If you are inside the your fill area at the start then start with the fill color turned on, otherwise off. When you hit a boundary between the fill zone and the non fill zone, toggle the fill color. Basically, an even number of boundary jumps means that the pixel colour is the same as the screen edge, and an odd number of jumps means that the pixel colour is the opposite of the screen edge. So basically, you just do a raster scan of all the pixels, toggling the fill colour whenever the boundary colour is encountered. Bye Martin
3. Re: Proceeding apace...
- Posted by Matthew Lewis <MatthewL at KAPCOUSA.COM> Mar 23, 2000
- 541 views
> -----Original Message----- > Jeff Zeitlin > What I need now is a way to unambiguously determine a point which > lies within the shape that is being drawn, so that the fill > routine can be used. Every intuitive method I've come up with, > I've been able to draw a figure that breaks the rule. 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: <C Code> int pnpoly(int npol, float *xp, float *yp, float x, float y) { int i, j, c = 0; for (i = 0, j = npol-1; i < npol; j = i++) { if ((((yp[i] <= y) && (y < yp[j])) || ((yp[j] <= y) && (y < yp[i]))) && (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) c = !c; } return c; } </C Code> 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. So in Euphoria: -- Untested code. Watch for typos!! -- poly = { {x1,y1}, {x2,y2},...,{xn,yn},{x1,y1} } -- point = {x_point, y_point} funciton pnpoly( sequence poly, sequence point ) atom x, y, c c = 0 x = point[1] y = point[2] for i = 1 to length(poly)-1 do if ((poly[i][2] <= y and poly[i+1][2] < y) or (poly[i][2] <= y and poly[i+1][2] < y)) and ( x < (poly[i+1][1] - poly[i][1]) * (y - poly[i][2]) ; ( poly[i+1][2] - poly[i][2] ) + poly[i][1])) then c = (c=0) end if end for return c end function It might be possible to optimize within the if statement, but this should do the trick. Matthew W Lewis
4. Re: Proceeding apace...
- Posted by Everett Williams <rett at GVTC.COM> Mar 23, 2000
- 538 views
Jeff Zeitlin wrote: >... but still getting stuck on issues with the fill routine. > >What I need now is a way to unambiguously determine a point which >lies within the shape that is being drawn, so that the fill >routine can be used. Every intuitive method I've come up with, >I've been able to draw a figure that breaks the rule. There's >also another problem I can see coming down the line, but I'll >stumble over that rock when I come to it. > snip Why do you think that paint programs suck up so many cycles and eat up so much ram to do what appear to be fairly trivial things like fill routines? Most mouse routines only work with well defined shapes that are easy to track...and they create enough problems with overlapping windows. As soon as the shape becomes jagged, simpleness goes away. Everett L.(Rett) Williams rett at gvtc.com
5. Re: Proceeding apace...
- Posted by Everett Williams <rett at GVTC.COM> Mar 23, 2000
- 525 views
- Last edited Mar 24, 2000
Matthew Lewis wrote: >> -----Original Message----- >> Jeff Zeitlin > >> What I need now is a way to unambiguously determine a point which >> lies within the shape that is being drawn, so that the fill >> routine can be used. Every intuitive method I've come up with, >> I've been able to draw a figure that breaks the rule. > snip > but then I found this on the web: > 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. snip >It might be possible to optimize within the if statement, but this should do >the trick. > >Matthew W Lewis With one caveat...unless I have misunderstood your example, this will only work for the simple case where there is only one polygon on the surface. More than one polygon will invalidate the code. Everett L.(Rett) Williams rett at gvtc.com
6. Re: Proceeding apace...
- Posted by Matt Lewis <matthewwalkerlewis at YAHOO.COM> Mar 24, 2000
- 500 views
--- Everett Williams <rett at GVTC.COM> wrote: > > With one caveat...unless I have misunderstood your example, this will only > work for the simple case where there is only one polygon on the surface. > More than one polygon will invalidate the code. > Depends on what you mean. If you are talking about 2 polygons, with no points of intersection, then there shouldn't be any problem, since the code only 'sees' the polygon you pass to it. If you're talking about 'inbedded' polygons (where you might have holes, like a doughnut type shape), then a few simple modifications are all that's needed. Actually, you might just 'wrap' the function when you know that your polygon has holes in it. First check to see if the point is within the outer polygon, and if so, make sure it isn't in any holes. I would think that Jeff's working on the polygon() routine, where he needs to either fill or not fill the polygon supplied to the user, so I doubt that these types of complications will occur. Matt Lewis __________________________________________________ Do You Yahoo!? Talk to your friends online with Yahoo! Messenger. http://im.yahoo.com
7. Re: Proceeding apace...
- Posted by Jeff Zeitlin <jzeitlin at CYBURBAN.COM> Mar 24, 2000
- 524 views
- Last edited Mar 25, 2000
On Fri, 24 Mar 2000 00:00:29 -0500, simulat <simulat at INTERGATE.BC.CA> wrote: >This is pretty vague, but I remember some sort of odd/even rule that was >used for fills: >Start at the screen edge at the top >If you are inside the your fill area at the start then > start with the fill color turned on, > otherwise off. >When you hit a boundary between the fill zone and the non fill zone, toggle >the fill color. > Basically, an even number of boundary jumps means that the pixel colour is >the same as the screen edge, and an odd number of jumps means that the pixel >colour is the opposite of the screen edge. So basically, you just do a >raster scan of all the pixels, toggling the fill colour whenever the >boundary colour is encountered. Yes, I forgot what this algorithm is called, but it's one possibility that I have - the major flaw with this one is that it doesn't handle self-intersecting figures properly. A secondary flaw is one that will appear with almost any algorithm that I've seen; what if there are two overlapping figures drawn in the same color? That's the bridge that I'll fall off when I come to it... -- Jeff Zeitlin jzeitlin at cyburban.com
8. Re: Proceeding apace...
- Posted by Jeff Zeitlin <jzeitlin at CYBURBAN.COM> Mar 24, 2000
- 544 views
- Last edited Mar 25, 2000
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
9. Re: Proceeding apace...
- Posted by simulat <simulat at INTERGATE.BC.CA> Mar 24, 2000
- 517 views
- Last edited Mar 25, 2000
Hi Jeff I'm not quite sure what you mean by "self intersecting shapes". Are these shapes with loops in the boundary? How are the shapes defined? Are the boundaries coloured lines that form a closed polygon? Do different polygons have the same boundary colour? Or are the shapes defined mathematically? Bye Martin
10. Re: Proceeding apace...
- Posted by Colin Taylor <ctaylor at RACSA.CO.CR> Mar 25, 2000
- 517 views
Jeff, What are you trying to do? 1. draw a polygon on screen, could be filled or unfilled, or 2. flood-fill a bounded area on screen. There are working examples of solutions to both problems posted in the Euphoria archives. If you could be a bit more specific, I would be happy to help you. - Colin Taylor ----- Original Message ----- From: Jeff Zeitlin <jzeitlin at CYBURBAN.COM> To: <EUPHORIA at LISTSERV.MUOHIO.EDU> Sent: Friday, March 24, 2000 10:52 PM Subject: 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] > > >http://www.swin.edu.au/astronomy/pbourke/geometry/insidepoly/ > > >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 >
11. Re: Proceeding apace...
- Posted by Jeff Zeitlin <jzeitlin at CYBURBAN.COM> Mar 25, 2000
- 563 views
- Last edited Mar 26, 2000
On Sat, 25 Mar 2000 00:00:27 -0500, simulat <simulat at INTERGATE.BC.CA> wrote: >I'm not quite sure what you mean by "self intersecting shapes". Are these >shapes with loops in the boundary? Yes. >How are the shapes defined? Are the boundaries coloured lines that form a >closed polygon? Do different polygons have the same boundary colour? Or are >the shapes defined mathematically? I would recommend that you look at the documentation for polygon() in refman.doc. This is the procedure I need to duplicate. -- Jeff Zeitlin jzeitlin at cyburban.com
12. Re: Proceeding apace...
- Posted by Jeff Zeitlin <jzeitlin at CYBURBAN.COM> Mar 26, 2000
- 516 views
On Sun, 26 Mar 2000 00:00:29 -0500, Colin Taylor <ctaylor at RACSA.CO.CR> wrote: >What are you trying to do? >1. draw a polygon on screen, could be filled or unfilled, or >2. flood-fill a bounded area on screen. >There are working examples of solutions to both problems posted in the >Euphoria archives. If you could be a bit more specific, I would be happy to >help you. (1) would be the technically correct answer; the actual goal is to write a Linux version of graphics.e that interfaces with libvga (since the current Linux release of Euphoria "doesn't support" pixel graphics). The second problem is merely a subset of the first, as if I can draw an unfilled polygon, and have a floodfill routine for a bounded area on the screen, I can draw a filled polygon - subject to the gotchas I've been mentionining in this thread. (BTW, I did get your code sent separately; will analyze during the week.) -- Jeff Zeitlin jzeitlin at cyburban.com
13. Re: Proceeding apace...
- Posted by Bernie Ryan <xotron at BUFFNET.NET> Mar 26, 2000
- 532 views
On Sun, 26 Mar 2000 16:15:12 -0500, Jeff Zeitlin <jzeitlin at CYBURBAN.COM> wrote: >(1) would be the technically correct answer; the actual goal is >to write a Linux version of graphics.e that interfaces with >libvga (since the current Linux release of Euphoria "doesn't >support" pixel graphics). The second problem is merely a subset >of the first, as if I can draw an unfilled polygon, and have a >floodfill routine for a bounded area on the screen, I can draw a >filled polygon - subject to the gotchas I've been mentionining in >this thread. (BTW, I did get your code sent separately; will >analyze during the week.) > >-- >Jeff Zeitlin >jzeitlin at cyburban.com Jeff: Goto Pete Eberlein Web page and check. I think he has a version of Neil for linux. I've noticed he has floodfill in some of his neil code that uses assembler. He is one of the sharpest programmers on this list and if he doesn't have what you need there I'am sure he will know a way to help you solve your problem. Bernie
14. Re: Proceeding apace...
- Posted by Pete Eberlein <xseal at HARBORSIDE.COM> Mar 26, 2000
- 563 views
On Sun, 26 Mar 2000 16:17:57 -0500, Bernie Ryan <xotron at BUFFNET.NET> wrote: >On Sun, 26 Mar 2000 16:15:12 -0500, Jeff Zeitlin <jzeitlin at CYBURBAN.COM> >wrote: > >>(1) would be the technically correct answer; the actual goal is >>to write a Linux version of graphics.e that interfaces with >>libvga (since the current Linux release of Euphoria "doesn't >>support" pixel graphics). The second problem is merely a subset >>of the first, as if I can draw an unfilled polygon, and have a >>floodfill routine for a bounded area on the screen, I can draw a >>filled polygon - subject to the gotchas I've been mentionining in >>this thread. (BTW, I did get your code sent separately; will >>analyze during the week.) >> >>-- >>Jeff Zeitlin >>jzeitlin at cyburban.com > > Jeff: > > Goto Pete Eberlein Web page and check. That's http://www.harborside.com/~xseal/euphoria/ > I think he has a version of Neil for linux. I've noticed he has > floodfill in some of his neil code that uses assembler. Neil doesn't have a asm polygonfill... yet. Jeff and I have been in contact, and I think I'm going to wait and see what algorithm he comes up with, and then possibly recode it in asm and so it works on Neil2 virtual screens.. Neil2 is totally platform-independent (as long as I test the code on each platform before I post it ... just the other day I coded the keyboard and mouse input routines to be completely identical regardless of platform... get_key(), get_mouse() and Michael Bolin's get_keys() return the same values on Linux X windows, DOS and Win32. Mike Hurley is helping with the mouse cursor routines, which should be useful in DOS and Linux Svgalib versions. > He is one of the sharpest programmers on this list and if > he doesn't have what you need there I'am sure he will know a way > to help you solve your problem. Dude! - thanks for the compliment, Bernie. > Bernie Laters, Pete