OpenEuphoria

Re: finding if point is inside irregular rectangle

• Posted by tone.skoda at siol.net Feb 27, 2002
• 574 views

Here is program to test it, it works.

-- begin code

include graphics.e
include get.e

function inpoly(sequence poly, integer x, integer y)
    -- return 1 (true) if point x,y is inside polygon

    sequence s
    integer m,n,xi,x1,x2,y1,y2

    s = {}
    m = length(poly)
    n = 0
    x2 = poly[m][1]
    y2 = poly[m][2]
    for i = 1 to m do
        x1 = x2
        y1 = y2
        if x = x1 and y = y1 then   -- vertices are tricky...
            return 1
        end if
        x2 = poly[i][1]
        y2 = poly[i][2]
        if y1 = y2 and y = y1 then  -- horizontal side
            if y = y1 then
                return (x1<=x and x2>=x) or (x2<=x and x1>=x)
            end if
        elsif (y1 < y and y2 > y) or (y2 < y and y1 > y) then
            xi = x1 + floor((x2-x1)*(y-y1)/(y2-y1))
            s &= xi
        end if
    end for
    for i = 1 to length(s) do
        if s[i] <  x then
            n += 1
        end if
    end for
    return and_bits(n, 1)           -- odd
end function


---- test ----

if graphics_mode(261) then
end if

function get_rand_polygon ()
    atom a, b, c, d, e, f, g, h
    a = rand (100)
    b = 100 + rand (100)
    c = a + rand (100)
    d = 100 + rand (100)
 e = 200 + rand (100)
    f = 100 + 200 + rand (100)
    g = rand (100)
    h = 100 + 200 + rand (100)
    return {{a, b}, {c, d}, {e, f}, {g, h}}
end function

sequence rand_point
sequence rand_polygon
integer is_inside

while 1 do
    rand_point  = {rand (300), 100 + rand (300)}
    rand_polygon = get_rand_polygon ()
    ellipse (MAGENTA, 1, {rand_point [1] - 2,
        rand_point [2] - 2}, {rand_point [1] + 2, rand_point [2] + 2})
    is_inside = inpoly (rand_polygon, rand_point [1], rand_point [2])
    if is_inside then
        polygon (GREEN, 0, rand_polygon)
        text_color (GREEN)
        puts (1, "point is inside polygon\n")
        text_color (WHITE)
    else
        polygon (RED, 0, rand_polygon)
        text_color (RED)
        puts (1, "point is not inside polygon\n")
        text_color (WHITE)
    end if
    puts(1, "\nPress spacebar for next or any other key to exit.\n")
    if wait_key() = 32 then
        clear_screen()
    else
        exit
    end if
end while

-- end code

----- Original Message -----
From: "Jiri Babor" <jbabor at PARADISE.NET.NZ>
To: "EUforum" <EUforum at topica.com>
Sent: Wednesday, February 27, 2002 10:56 AM
Subject: Re: finding if point is inside irregular rectangle


>
> A lot of wise words has been wasted on the subject. But talk is cheap, and
I
> have not seen any usable code so far. The function below is, roughly, what
I
> proposed four or five years ago, when the subject cropped up for the first
> time in this forum. It's only my vague recollection, just to get the ball
> rolling again - sorry I have not kept the original copy.
>
> jiri
>
> function inpoly(sequence poly, integer x, integer y)
>     -- return 1 (true) if point x,y is inside polygon
>
>     sequence s
>     integer m,n,xi,x1,x2,y1,y2
>
>     s = {}
>     m = length(poly)
>     n = 0
>     x2 = poly[m][1]
>     y2 = poly[m][2]
>     for i = 1 to m do
>         x1 = x2
>         y1 = y2
>         if x = x1 and y = y1 then   -- vertices are tricky...
>             return 1
>         end if
>         x2 = poly[i][1]
>         y2 = poly[i][2]
>         if y1 = y2 and y = y1 then  -- horizontal side
>             if y = y1 then
>                 return (x1<=x and x2>=x) or (x2<=x and x1>=x)
>             end if
>         elsif (y1 < y and y2 > y) or (y2 < y and y1 > y) then
>             xi = x1 + floor((x2-x1)*(y-y1)/(y2-y1))
>             s &= xi
>         end if
>     end for
>     for i = 1 to length(s) do
>         if s[i] <  x then
>             n += 1
>         end if
>     end for
>     return and_bits(n, 1)           -- odd
> end function
>
>
>
>