OpenEuphoria

Re: finding if point is inside irregular rectangle

• Posted by Jiri Babor <jbabor at PARADISE.NET.NZ> Feb 27, 2002
• 424 views

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