OpenEuphoria

Re: intersection and ExoticaX

• Posted by martin.stachon at worldonline.cz Jul 06, 2001
• 412 views

>
> 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