OpenEuphoria

Re: intersection and ExoticaX

• Posted by Jiri Babor <jbabor at PARADISE.NET.NZ> Jul 06, 2001
• 417 views

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