1. intersection and ExoticaX
Hello all,
I thought I sent a message concerning this question already but haven't seen
any responses yet so here goes again: I need a formula or an Euphoria
function that can tell me where a line intersects with a polygon. I know
that a line can intersect with a polygon more than once so I want the
intersection that is closest to the line's starting point. Also, if it would
make for faster code the line can be defined with starting point and
directional vector rather than starting point and ending point. Here is a
skeleton function:
function IntersectPolygon( atom x, atom y, atom x2,
atom y2, sequence poly )
return {x,y} -- coordinates of intersection point
end function
This looks like a job for Jiri Babor or any of the gurus around here. I
mention Jiri simply becuase he is a master at writing fast executing code.
Jiri, please don't feel obligated to write a function for me simply because
I mentioned your name, I just thought this might be a pleasant challenge for
you.
Also I have some issues with ExoticaX that perhaps Chris Bensler can help me
with. I thought I had his email saved or I wouldn't post this to the list
but maybe others can help with this as well:
In the ExoticaX docs
gdi_get_charwodth( atom Char )
sould be:....^
gdi_get_charwidth( atom Char )
.............^
In Ddraw.ew
line 921 uses a sprintf format %D instead of %d
doesn't work with the captital D
In creation or loading of a bitmap in ExoticaX the memory
mode can be set to hardware or software memorry. what is
hardware/software memory? Is it the difference between Video
memory and regular RAM or RAM and virtual memory or what?
I need a draw-line procedure (needs to work on bitmaps at least)
draw_line_bitmap( BMP_ID, x1,y1,x2,y2, COLOR )
or
draw_line_bitmap( atom BMP_ID, sequence points, atom color )
other basic drawing routines wouldn't go amiss either.
16bit colors work fine for loaded images but not for specifying color
values. It seems it uses a different format for 16bit color in specifying a
hex color value. For instance #888888 is a medium gray in truecolor modes.
In 16 bit mode it is a dark pink. These things aught not to be! I don't want
to have to programatically test for color depth and then convert to a
different color value format every time I need to specify a color with a hex
number.
Thanks in advance for any help from anyone on either the polygon
intersection problem or the ExoticaX issues.
2. Re: intersection and ExoticaX
-- cut.ex : find all intersection points of a line and a polygon
-- jiri babor
-- jbabor at paradise.net.nz
-- homepages.paradise.net.nz/~jbabor/euphoria.html
-- 01-07-06
function round(object x) -- recursive
if atom(x) then
return floor(x+0.5)
end if
for i=1 to length(x) do
x[i] = round(x[i])
end for
return x
end function
function cut(sequence line, sequence poly)
-- line is a two point line sequence {{x1, y1}, {x2, y2}}
-- poly is a vertices sequence in the form {{x1, y1}, ... {xn,
yn}}
-- defining the polygon
-- return sequence of intersection points
sequence s
atom a1,a2, b1,b2, c1,c2, D, x,x1,x2, y,y1,y2
integer n
n = length(poly) -- number of vertices
poly = append(poly, poly[1]) -- just convenience
s = {}
a1 = line[1][2] - line[2][2]
b1 = line[2][1] - line[1][1]
c1 = -a1*line[1][1] - b1*line[1][2]
for i = 1 to n do
x1 = poly[i][1]
x2 = poly[i+1][1]
y1 = poly[i][2]
y2 = poly[i+1][2]
a2 = y1 - y2
b2 = x2 - x1
D = a1*b2 - a2*b1 -- determinant
if D then -- if line and side not
parallel
c2 = -a2*x1 - b2*y1
x = (b1*c2 - b2*c1)/D
y = (a2*c1 - a1*c2)/D
if b2 then -- if side not vertical
if (x >= x1 and x <= x2) or (x <= x1 and x >= x2) then
s = append(s, {x,y})
end if
else -- vertical side
if (y >= y1 and y <= y2) or (y <= y1 and y >= y2) then
s = append(s, {x, y})
end if
end if
end if
end for
return round(s) -- rounding is optional
end function
include graphics.e
include get.e -- wait_key()
constant poly = {{200,160},{320,300},{440,120},{400,400},{180,320}}
object o
sequence s, line
integer co, key
procedure draw_circles(sequence s)
integer x,y
for i = 1 to length(s) do
x = s[i][1]
y = s[i][2]
ellipse(co,1, {x-3,y-3}, {x+3, y+3})
end for
end procedure
o = graphics_mode(18) -- 640x480x16
polygon(15, 0, poly)
co = YELLOW
text_color(co)
line = {{0,180}, {600,0}} -- yellow line
draw_line(co, line)
s = cut(line, poly)
? s
draw_circles(s)
co = BRIGHT_BLUE
text_color(co)
line = {{0,220},{639,300}} -- blue line
draw_line(co, line)
s = cut(line, poly)
? s
draw_circles(s)
co = GREEN
text_color(co)
line = {{0,400}, {639,320}} -- green line
draw_line(co, line)
s = cut(line, poly)
? s
draw_circles(s)
key = wait_key() -- waste time
o = graphics_mode(-1) -- return to text mode
----- Original Message -----
From: "Lewis Townsend" <keroltarr at HOTMAIL.COM>
To: "EUforum" <EUforum at topica.com>
Sent: Thursday, 5 July 2001 09:45
Subject: intersection and ExoticaX
> Hello all,
>
> I thought I sent a message concerning this question already but
haven't seen
> any responses yet so here goes again: I need a formula or an
Euphoria
> function that can tell me where a line intersects with a polygon. I
know
> that a line can intersect with a polygon more than once so I want
the
> intersection that is closest to the line's starting point. Also, if
it would
> make for faster code the line can be defined with starting point and
> directional vector rather than starting point and ending point. Here
is a
> skeleton function:
>
> function IntersectPolygon( atom x, atom y, atom x2,
> atom y2, sequence poly )
> return {x,y} -- coordinates of intersection point
> end function
>
> This looks like a job for Jiri Babor or any of the gurus around
here. I
> mention Jiri simply becuase he is a master at writing fast executing
code.
> Jiri, please don't feel obligated to write a function for me simply
because
> I mentioned your name, I just thought this might be a pleasant
challenge for
> you.
<snip>
4. Re: intersection and ExoticaX
>
> Hello all,
>
> I thought I sent a message concerning this question already but haven't
seen
> any responses yet so here goes again: I need a formula or an Euphoria
> function that can tell me where a line intersects with a polygon. I know
> that a line can intersect with a polygon more than once so I want the
> intersection that is closest to the line's starting point. Also, if it
would
> make for faster code the line can be defined with starting point and
> directional vector rather than starting point and ending point. Here is a
> skeleton function:
>
> function IntersectPolygon( atom x, atom y, atom x2,
> atom y2, sequence poly )
> return {x,y} -- coordinates of intersection point
> end function
>
> This looks like a job for Jiri Babor or any of the gurus around here. I
> mention Jiri simply becuase he is a master at writing fast executing code.
> Jiri, please don't feel obligated to write a function for me simply
because
> I mentioned your name, I just thought this might be a pleasant challenge
for
> you.
>
>
Hello,
I've written this Intersection routine,
it has some unfinished parts and sometimes
do not give intersection where it should be.
Maybe I will improve it if you are interested.
It is based on converting lines into linear functions
(y = ax + b) and then finding their common point.
Martin
*-CODE BEGINS-*
include graphics.e
function
ersectPolygon(
atom x1, atom y1,
atom x2, atom y2,
sequence poly )
atom a1, a2, b1, b2
atom x, y
sequence result
result = {}
if x1 = x2 then
--! SPECIAL CASE : a= inf => VERTICAL LINE
-- ADD CODE HERE
else
a1 = (y2-y1)/(x2-x1)
b1 = y1-a1*x1
for i=1 to length(poly)-1 by 2 do
-- ADD CHECHING FOR DIVIDER NOT TO BE ZERO - VERTICAL LINE
a2 = (poly[i+1][2]-poly[i][2]) / (poly[i+1][1]-poly[i][1])
if a1 = a2 then
-- this lines can never meet
else
b2 = poly[i][2] - a2*poly[i][1]
x = (b2-b1)/(a1-a2)
if poly[i][1] > poly[i+1][1] then
if x < poly[i][1] and x > poly[i+1][1] then
y = a1*x + b1
result &= {{x,y}}
end if
else
if x > poly[i][1] and x < poly[i+1][1] then
y = a1*x + b1
result &= {{x,y}}
end if
end if
end if
end for
end if
return result
end function
atom x1,y1,x2,y2
sequence poly
sequence inter
x1 = rand(320)
y1 = rand(200)
x2 = x1 + rand(50) - 25
y2 = y1 + rand(50) - 25
poly = {}
for i=1 to 5 + rand(5) do
poly &= {{rand(320),rand(200)}}
end for
poly &= {poly[1]}
if graphics_mode(19) then end if
draw_line(BLUE, {{x1,y1},{x2,y2}})
draw_line(WHITE, poly)
inter = IntersectPolygon(x1,y1,x2,y2,poly)
for i=1 to length(inter) do
pixel(RED, inter[i])
end for
5. Re: intersection and ExoticaX
Jeff,
if the line and side are parallel, or even identical, the case can be
ignored, because the entry and exit points will be obtained as
intersections with the adjacent sides.
BTW, Jeff, I would like to have a look at your solution, unfortunately
Lewis' note with it was truncated.
jiri
----- Original Message -----
From: "Jeffrey Fielding" <jjprog at earthlink.net>
To: "EUforum" <EUforum at topica.com>
Sent: Saturday, 7 July 2001 06:15
Subject: Re: intersection and ExoticaX
>
>
> On 2001.07.06 07:52 Jiri Babor wrote:
> <snip>
> > if D then -- if line and side not
> > parallel
> > c2 = -a2*x1 - b2*y1
> > x = (b1*c2 - b2*c1)/D
> > y = (a2*c1 - a1*c2)/D
> > if b2 then -- if side not vertical
> > if (x >= x1 and x <= x2) or (x <= x1 and x >= x2)
then
> > s = append(s, {x,y})
> > end if
> > else -- vertical side
> > if (y >= y1 and y <= y2) or (y <= y1 and y >= y2)
then
> > s = append(s, {x, y})
> > end if
> > end if
> > end if
> </snip>
>
> Nice. But what if the line and side are parallel?
>
> Jeff
>
>
>
>
>
>
6. Re: intersection and ExoticaX
Hello Martin,
>Hello,
>I've written this Intersection routine,
>it has some unfinished parts and sometimes
>do not give intersection where it should be.
>Maybe I will improve it if you are interested.
Thanks for this solution. I am interested in you improving it. I need a
function that always works. Thanks. :)
later,
Lewis Townsend
7. Re: intersection and ExoticaX
Hello Jiri, Jeff,
>BTW, Jeff, I would like to have a look at your solution, unfortunately
>Lewis' note with it was truncated.
>
>jiri
Oops, I wonder how that happened. Here it is again. It looks whole to me
right now, so if it is truncated again it must be hotmail or Topica that is
doing it.
later,
Lewis Townsend
function poly_to_lines(sequence poly)
sequence lines
lines = repeat(0, length(poly))
for i = 1 to length(poly)-1 do
lines[i] = {poly[i],poly[i+1]}
end for
lines[length(lines)] = {poly[length(poly)],poly[1]}
return lines
end function
function distance(atom x1, atom y1, atom x2, atom y2)
atom dx, dy
dx = x2-x1
dy = y2-y1
return sqrt((dx*dx)+(dy*dy))
end function
function round(atom x)
if x-floor(x) >= 0.5 then
return floor(x)+1
else
return floor(x)
end if
end function
function fix(atom x)
return round(x * 1000)
end function
function between(atom v, atom top, atom bottom)
v = fix(v)
top = fix(top)
bottom = fix(bottom)
return ((v <= top) and (v >= bottom)) or ((v >= top) and (v <=
bottom))
end function
function IntersectPolygon(atom x1, atom y1, atom x2, atom y2, sequence
poly)
sequence lines
atom dx, dy, ray_slope, line_slope, tmp2, lx1, lx2, ly1, ly2
object tmp, best
atom best_distance, dst
best = 0
best_distance = -1
if x1 = x2 then
for i = 1 to length(poly) do
poly[i] = {poly[i][2],poly[i][1]}
end for
tmp = IntersectPolygon(y1,x1,y2,x2,poly)
if sequence(tmp) then
return {tmp[2],tmp[1]}
else
return 0
end if
end if
dx = x2-x1
dy = y2-y1
ray_slope = dy/dx
lines = poly_to_lines(poly)
for i = 1 to length(lines) do
lx1 = lines[i][1][1]
ly1 = lines[i][1][2]
lx2 = lines[i][2][1]
ly2 = lines[i][2][2]
if lx1 = lx2 and ((lx1-x1)*dx) >= 0 then
tmp = y1 + (ray_slope * (lx1 - x1))
if between(tmp,ly1,ly2) then
dst = distance(x1,y1,lx1,tmp)
if integer(best) or dst < best_distance then
best = {lx1,tmp}
best_distance = dst
if dst = 0 then
return best
end if
end if
end if
elsif lx1 != lx2 then
line_slope = (ly2-ly1)/(lx2-lx1)
if ray_slope = line_slope then
if (y1 - (x1 * ray_slope)) = (ly1 - (lx1 * line_slope))
then
if between(x1, lx1, lx2) then
return {x1, y1}
else
tmp = 0
if (lx1-x1)*dx >= 0 then
tmp = lines[i][1]
end if
if (lx2-x1)*dx >= 0 then
if integer(tmp) then
tmp = lines[i][2]
else
if ((tmp[1]-x1)*dx) > ((lx2-x1)*dx) then
tmp = lines[i][2]
end if
end if
end if
if sequence(tmp) then
dst = distance(x1,y1,tmp[1],tmp[2])
if integer(best) or dst < best_distance then
best = tmp
best_distance = dst
end if
end if
end if
end if
else
tmp = (ly1 - (line_slope * lx1) - y1 + (ray_slope *
x1))/(ray_slope - line_slope)
tmp2 = y1 + (ray_slope * (tmp - x1))
if ((tmp-x1)*dx) >= 0 then
if between(tmp,lx1,lx2) and
between(tmp2,ly1,ly2) then
dst = distance(x1,y1,tmp,tmp2)
if integer(best) or dst < best_distance then
best = {tmp,tmp2}
best_distance = dst
if dst = 0 then
return best
end if
end if
end if
end if
end if
end if
end for
return best
end function
