1. Proceeding apace...
... 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...
> ... 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...
> -----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...
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
-
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...
--- 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
-
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
-
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
-
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...
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
-
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...
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...
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...
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
