Computer Science Canada

Intersections of two lines
Author:  Windsurfer [ Wed Aug 30, 2006 10:59 pm ]
Post subject:  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.
code:

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_x2)) or ((h <= rec_x1) and (h >= rec_x2))) and
        (((v >= rec_y1) and (v <= rec_y2)) or ((v <= rec_y1) and (v >= rec_y2)))
end Pt_In_Rec

function Intersect_Seg (x1, y1, x2, y2, h1, v1, h2, v2 : real, var point_x : real, var point_y : real) : boolean
    %This function returns true if the segments intersect
    %if they don't, this **should** be able to find the point that the "lines" intersect
    %if they don't intersect at all (eg. parallel lines not overlapping), then the point will be 0,0
    %uses form y = m*x + b
    if x1 = x2 and y1 = y2 then % if the "line" is a point
        if ((x1 = h1) or (x1 = h2)) and ((y1 = v1) or (y1 = v2)) then
            point_x := x1
            point_y := y1
            result true
        end if
    end if
    if h1 = h2 and v1 = v2 then     % if the "line" is a point
        if ((h1 = x1) or (h1 = x2)) and ((v1 = y1) or (v1 = y2)) then
            point_x := h1
            point_y := v1
            result true
        end if
    end if

    % the "lines" aren't points, so find slopes and y-intercepts

    var m1, m2, b1, b2 : real
    if x2 not= x1 then     %if line 1 is not vertical, keep going
        m1 := (y2 - y1) / (x2 - x1)
        if h2 not= h1 then     %is line 2 vertical?
            m2 := (v2 - v1) / (h2 - h1)
            %everything is normal
            %w00t
        else     %line 2 is vertical! but line 1 is not!
            b1 := y1 - m1 * x1
            point_x := h1
            point_y := b1 + m1 * point_x

            if Pt_In_Rec (point_x, point_y, x1, y1, x2, y2) and
                    ((point_y < v1 and point_y > 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


Hopefully it isn't too complicated.... I made it so that it uses y = mx + b format, with extra stuff to correct it when m = infinity and so on.
Author:  BenLi [ Thu Aug 31, 2006 1:24 pm ]
Post subject: 
well without reading your code, you said

Quote:

It is supposed to return true if two lines are intersecting

Any two lines will intersect if it's not parallel. Why don't you check that instead?
Author:  Bored [ Thu Aug 31, 2006 2:29 pm ]
Post subject: 
When he says lines he is talking about line segments. Therfore even though the extended line will touch it does not mean that the line segments are touching. So instead he needs to find the point of intersection and see if its within both line segments or atleast thats what I think he's doing.
Author:  Bored [ Thu Aug 31, 2006 2:53 pm ]
Post subject: 
I added this code to the bottom to generate random lines and test your program:

code:
View.Set ("nocursor")
var x, y : array 1 .. 5 of real
loop
    for i : 1 .. 4
        x (i) := Rand.Int (0, maxx - 1) + Rand.Real
        y (i) := Rand.Int (0, maxy - 1) + Rand.Real
    end for
    drawline (round (x (1)), round (y (1)), round (x (2)), round (y (2)), red)
    drawline (round (x (3)), round (y (3)), round (x (4)), round (y (4)), blue)
    put Intersect_Seg (x (1), y (1), x (2), y (2), x (3), y (3), x (4), y (4), x (5), y (5))
    drawfilloval (round (x (5)), round (y (5)), 2, 2, green)
    exit when getchar = KEY_ESC
    cls
end loop

And after extensive trials I have not seen one wrong case. Try it for yourself. If you find one that is wrong take a picture and post it as it seems to work fine for me. Maybe your just implimenting it into another program wrong or something like that.
Author:  Windsurfer [ Thu Aug 31, 2006 3:43 pm ]
Post subject: 
Well, if you've ever played my game Forces you may have noticed what i call "offscreen bubbles". What i'm actually doing is finding the intersection of a line drawn from the center of the screen to where the enemy is. Where it intersects the border, i put a bubble. You may have noticed it flickering... But that's just one example.

But here is that same problem written as a program. Try moving your mouse around the outside, and watch the line flicker.
code:

%this algorythm was made by Adam Bilinski
%very usefol for many games

var mouse_x, mouse_y, button : int := 0
const X_SCREEN := 650
const Y_SCREEN := 600
setscreen ("graphics:" + intstr (X_SCREEN) + ";" + intstr (Y_SCREEN))
const C_X := X_SCREEN div 2
const C_Y := Y_SCREEN div 2

View.Set ("offscreenonly")

function Pt_Near (h1, v1, h2, v2, dist : real) : boolean
    %which method is faster?
    %result sqrt ((h2 - h1) *(h2 - h1) + (v2 - v1) *(v2 - v1)) < dist
    result sqrt ((h2 - h1) ** 2 + (v2 - v1) ** 2) < dist
end Pt_Near

function Pt_Dist (h1, v1, h2, v2 : real) : real
    %which method is faster?
    %result sqrt ((h2 - h1) *(h2 - h1) + (v2 - v1) *(v2 - v1) )
    result sqrt ((h2 - h1) ** 2 + (v2 - v1) ** 2)
end Pt_Dist

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_x2)) or ((h <= rec_x1) and (h >= rec_x2))) and
        (((v >= rec_y1) and (v <= rec_y2)) or ((v <= rec_y1) and (v >= rec_y2)))
end Pt_In_Rec

function Intersect_Seg (x1, y1, x2, y2, h1, v1, h2, v2 : real, var point_x : real, var point_y : real) : boolean
    %This function returns true if the segments intersect
    %if they don't, this **should** be able to find the point that the "lines" intersect
    %if they don't intersect at all (eg. parallel lines not overlapping), then the point will be 0,0
    %uses form y = m*x + b
    if x1 = x2 and y1 = y2 then % if the "line" is a point
        if ((x1 = h1) or (x1 = h2)) and ((y1 = v1) or (y1 = v2)) then
            point_x := x1
            point_y := y1
            result true
        end if
    end if
    if h1 = h2 and v1 = v2 then     % if the "line" is a point
        if ((h1 = x1) or (h1 = x2)) and ((v1 = y1) or (v1 = y2)) then
            point_x := h1
            point_y := v1
            result true
        end if
    end if

    % the "lines" aren't points, so find slopes and y-intercepts

    var m1, m2, b1, b2 : real
    if x2 not= x1 then     %if line 1 is not vertical, keep going
        m1 := (y2 - y1) / (x2 - x1)
        if h2 not= h1 then     %is line 2 vertical?
            m2 := (v2 - v1) / (h2 - h1)
            %everything is normal
            %w00t
        else     %line 2 is vertical! but line 1 is not!
            b1 := y1 - m1 * x1
            point_x := h1
            point_y := b1 + m1 * point_x

            if Pt_In_Rec (point_x, point_y, x1, y1, x2, y2) and
                    ((point_y < v1 and point_y > 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
Author:  zylum [ Fri Sep 01, 2006 12:01 am ]
Post subject: 
i dont see any flicker either. here's a simple function thats a little easier to read:

code:
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 <= max (x1, x2) & px >= min (x3, x4) & px <= max (x3, x4)
end intercept
Author:  Windsurfer [ Sun Sep 03, 2006 10:53 am ]
Post subject: 
Okay, your function does work, and IS easier to read, but it doesn't work for line segments. It also doesn't work if one of the lines is vertical... which is kind of critical. It also doesn't work if a line is a point, and it ALSO doesn't always return the right boolean. Take a look.... move your mouse off the right of the screen:
code:


var mouse_x, mouse_y, button : int := 0
const X_SCREEN := 650
const Y_SCREEN := 600
setscreen ("graphics:" + intstr (X_SCREEN) + ";" + intstr (Y_SCREEN))
const C_X := X_SCREEN div 2
const C_Y := Y_SCREEN div 2

View.Set ("offscreenonly")

function Pt_Near (h1, v1, h2, v2, dist : real) : boolean
    %which method is faster?
    %result sqrt ((h2 - h1) *(h2 - h1) + (v2 - v1) *(v2 - v1)) < dist
    result sqrt ((h2 - h1) ** 2 + (v2 - v1) ** 2) < dist
end Pt_Near

function Pt_Dist (h1, v1, h2, v2 : real) : real
    %which method is faster?
    %result sqrt ((h2 - h1) *(h2 - h1) + (v2 - v1) *(v2 - v1) )
    result sqrt ((h2 - h1) ** 2 + (v2 - v1) ** 2)
end Pt_Dist

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_x2)) or ((h <= rec_x1) and (h >= rec_x2))) and
        (((v >= rec_y1) and (v <= rec_y2)) or ((v <= rec_y1) and (v >= rec_y2)))
end Pt_In_Rec

function Intersect_Seg (x1, y1, x2, y2, h1, v1, h2, v2 : real, var point_x : real, var point_y : real) : boolean
    %This function returns true if the segments intersect
    %if they don't, this **should** be able to find the point that the "lines" intersect
    %if they don't intersect at all (eg. parallel lines not overlapping), then the point will be 0,0
    %uses form y = m*x + b
    if x1 = x2 and y1 = y2 then % if the "line" is a point
        if ((x1 = h1) or (x1 = h2)) and ((y1 = v1) or (y1 = v2)) then
            point_x := x1
            point_y := y1
            result true
        end if
    end if
    if h1 = h2 and v1 = v2 then     % if the "line" is a point
        if ((h1 = x1) or (h1 = x2)) and ((v1 = y1) or (v1 = y2)) then
            point_x := h1
            point_y := v1
            result true
        end if
    end if

    % the "lines" aren't points, so find slopes and y-intercepts

    var m1, m2, b1, b2 : real
    if x2 not= x1 then     %if line 1 is not vertical, keep going
        m1 := (y2 - y1) / (x2 - x1)
        if h2 not= h1 then     %is line 2 vertical?
            m2 := (v2 - v1) / (h2 - h1)
            %everything is normal
            %w00t
        else     %line 2 is vertical! but line 1 is not!
            b1 := y1 - m1 * x1
            point_x := h1
            point_y := b1 + m1 * point_x

            if Pt_In_Rec (point_x, point_y, x1, y1, x2, y2) and
                    ((point_y < v1 and point_y > 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

fcn intercept (x1, y1, x2, y2, x3, y3, x4, y4 : real, var px, py : real) : 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 := x
    py := m1 * x + b1

    result px >= min (x1, x2) & px <= max (x1, x2) & px >= min (x3, x4) & px <= max (x3, x4)
end intercept

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 intercept (C_X, C_Y, h1, v1, x1, y1, x1, y2, point_x, point_y) then
        elsif intercept (C_X, C_Y, h1, v1, x1, y2, x2, y2, point_x, point_y) then
        elsif intercept (C_X, C_Y, h1, v1, x2, y2, x2, y1, point_x, point_y) then
        elsif intercept (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
        put "Mouse is outside of window"
        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)
        else
            put "But line was not drawn."
        end if
    end if
    View.Update
    delay (10)
    cls
end loop
Author:  zylum [ Mon Sep 04, 2006 12:54 am ]
Post subject: 
k, this one should work a little better:

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

    var x := (b1 - b2) / (m2 - m1 + 1e-4)

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

    result px >= min (x1, x2) & px <= max (x1, x2) & px >= min (x3, x4) & px <= max (x3, x4) &
        py >= min (y1, y2) & py <= max (y1, y2) & py >= min (y3, y4) & py <= max (y3, y4)
end intercept
Author:  Windsurfer [ Mon Sep 04, 2006 7:21 am ]
Post subject: 
Wow. This works perfectly. Thanks... all I know is that your function works, and does resemble mine... sort of.
Anyhoo, this is awsome. Maybe now i can start putting walls in Forces.
+ bits Smile

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy