-----------------------------------

Windsurfer

Wed Aug 30, 2006 10:59 pm


Intersections of two lines

-----------------------------------

Okay, a while back i had been messing with this line intersect function... It is supposed to return true if two lines are intersecting. For some reason, it gives false positives, but no false negatives. Any help by anyone? I can't get a concrete example of when it gives the false positive, as it relies on real numbers and happens infrequently... but it has quite an impact when checking multiple lines.

function Pt_In_Rec (h, v, rec_x1, rec_y1, rec_x2, rec_y2 : real) : boolean
    %more complex and thorugh than original
    result (((h >= rec_x1) and (h = rec_y1) and (v  v2) or (point_y > v1 and point_y < v2)) then
                result true
            else
                result false
            end if
        end if
        b1 := y1 - m1 * x1
        b2 := v1 - m2 * h1
    else     %line 1 is vertical
        if h2 not= h1 then     %if line 2 is not vertical, find slope and y-int
            m2 := (v2 - v1) / (h2 - h1)
            b2 := v1 - m2 * h1
        else
            %line 2 is vertical!
            if h1 = x1 then     %if lines are overlapping, return true
                %lines overlap!
                point_x := x1
                point_y := (y1 + y2 + v1 + v2) / 4
                result true
            else
                %lines are not overlapping!
                result false
            end if
        end if

        %line 2 is not vertical here
        point_x := x1
        point_y := b2 + m2 * point_x
        if Pt_In_Rec (point_x, point_y, h1, v1, h2, v2) and
                ((point_y < y1 and point_y > y2) or (point_y > y1 and point_y < y2)) then
            result true
        else
            result false
        end if
    end if

    if m1 not= m2 then     %if parallel
        point_x := - (b1 - b2) / (m1 - m2)
    else
        if x1 = h1 and x2 = h2 and y1 = v1 and y2 = v2 then
            %find average point(yeah, not mathematic, but meh, it works for games)
            point_x := (x1 + x2 + h1 + h2) / 4
            point_y := (y1 + y2 + v1 + v2) / 4
            result true
        else
            result false  %it's dead! can't intersect
        end if
    end if

    point_y := b1 + m1 * point_x %find second point if all is good

    if Pt_In_Rec (point_x, point_y, x1, y1, x2, y2) and Pt_In_Rec (point_x, point_y, h1, v1, h2, v2) then
        %is the point inside the lines?
        result true %it is!
    else
        result false %it's not!
    end if
end Intersect_Seg

function Out_Of_Bounds (h1, v1, x1, y1, x2, y2 : real, var point_x : real, var point_y : real) : boolean
    if Pt_In_Rec (h1, v1, x1, y1, x2, y2) then
        result false
    else
        const C_X := (x2 - x1) / 2
        const C_Y := (y2 - y1) / 2
        if Intersect_Seg (C_X, C_Y, h1, v1, x1, y1, x1, y2, point_x, point_y) then
        elsif Intersect_Seg (C_X, C_Y, h1, v1, x1, y2, x2, y2, point_x, point_y) then
        elsif Intersect_Seg (C_X, C_Y, h1, v1, x2, y2, x2, y1, point_x, point_y) then
        elsif Intersect_Seg (C_X, C_Y, h1, v1, x2, y1, x1, y1, point_x, point_y) then
        else
            result false
        end if
        result true
    end if
end Out_Of_Bounds

loop
    Mouse.Where (mouse_x, mouse_y, button)
    if not Pt_In_Rec (mouse_x, mouse_y, 0, 0, X_SCREEN, Y_SCREEN) then
        var x1, y1 : real := 0

        if Out_Of_Bounds (mouse_x, mouse_y, 20, 20, X_SCREEN - 20, Y_SCREEN - 20, x1, y1) then

            var x2, y2 : real := 0
            var dist : real := Pt_Dist (C_X, C_Y, mouse_x, mouse_y)
            const size := dist / 5
            x2 := (C_X - mouse_x) / dist * size
            y2 := (C_Y - mouse_y) / dist * size
            drawline (round (x1), round (y1), round (x1 + x2), round (y1 + y2), black)
        end if
    end if
    View.Update
    delay (10)
    cls
end loop



-----------------------------------

zylum

Fri Sep 01, 2006 12:01 am



-----------------------------------

i dont see any flicker either. here's a simple function thats a little easier to read:

fcn intercept (x1, y1, x2, y2, x3, y3, x4, y4 : int, var px, py : int) : boolean
    var m1 := (y2 - y1) / (x2 - x1 + 1e-5)
    var m2 := (y4 - y3) / (x4 - x3 + 1e-5)
    var b1 := y1 - m1 * x1
    var b2 := y3 - m2 * x3

    var x := (b1 - b2) / (m2 - m1)

    px := round (x)
    py := round (m1 * x + b1)

    result px >= min (x1, x2) & px = min (x3, x4) & px = rec_x1) and (h = rec_y1) and (v = min (x1, x2) & px = min (x3, x4) & px = min (x1, x2) & px = min (x3, x4) & px = min (y1, y2) & py = min (y3, y4) & py