Trouble with Line Intersection Code in Wiki

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
Gravy
Citizen
Posts: 80
Joined: Sun Jan 22, 2012 10:15 pm
Location: CA, USA

Trouble with Line Intersection Code in Wiki

Post by Gravy » Sat Dec 29, 2012 11:42 pm

Hi all,

I'm using the line intersection code here: https://love2d.org/wiki/Additional_math, and am having trouble with it when line segments are horizontal or vertical.

In the part where it checks the segments, the checks sometimes return false when the three values are identical. I have no idea why. I ended up adding a tolerance value of 0.1, which did the trick but should be unnecessary. Any idea why this would be happening?

Attached is a love file that turns on and off the tolerance with the space button. WASD or arrows move the rectangle. When the tolerance is off, the collision is missed at random-seeming times.

Code: Select all

-- Checks if two lines intersect (or line segments if seg is true)
-- Lines are given as four numbers (two coordinates)
function findIntersect(l1p1x,l1p1y, l1p2x,l1p2y, l2p1x,l2p1y, l2p2x,l2p2y, seg1, seg2, tol)
	-- added tolerance
	local tolerance = tol and 0.1 or 0
    local a1,b1,a2,b2 = l1p2y-l1p1y, l1p1x-l1p2x, l2p2y-l2p1y, l2p1x-l2p2x
    local c1,c2 = a1*l1p1x+b1*l1p1y, a2*l2p1x+b2*l2p1y
    local det = a1*b2 - a2*b1
    if det==0 then return false, "The lines are parallel." end
    local x,y = (b2*c1-b1*c2)/det, (a1*c2-a2*c1)/det
    if seg1 or seg2 then
        local min,max = math.min, math.max
        if seg1 and not (min(l1p1x,l1p2x) <= x + tolerance and x <= max(l1p1x,l1p2x) + tolerance and min(l1p1y,l1p2y) <= y + tolerance 
        	and y <= (max(l1p1y,l1p2y)) + tolerance) or
           seg2 and not (min(l2p1x,l2p2x) <= x + tolerance and x <= max(l2p1x,l2p2x) + tolerance and min(l2p1y,l2p2y) <= y + tolerance 
           	and y <= (max(l2p1y,l2p2y)) + tolerance) then
            return false, "The lines don't intersect."
        end
    end
    return x,y
end
Attachments
line_rect_collision.love
(1.13 KiB) Downloaded 60 times

mathacka
Prole
Posts: 8
Joined: Tue Sep 25, 2012 7:45 pm

Re: Trouble with Line Intersection Code in Wiki

Post by mathacka » Fri Jan 04, 2013 9:50 pm

I tried changing your tolerance level to 0.00000001, and it still worked, I'm thinking the math functions they're using is producing some kind of floating point error at some places. I appears you can minimize your own error by putting in a tolerance lower then .01, but I don't know how much performance/accuracy you need,

well, I don't know if that helped at all.

Gravy
Citizen
Posts: 80
Joined: Sun Jan 22, 2012 10:15 pm
Location: CA, USA

Re: Trouble with Line Intersection Code in Wiki

Post by Gravy » Sat Jan 05, 2013 6:55 pm

Thanks, this is basically what I figured, but it seems crazy that this error exists at all.

User avatar
verilog
Citizen
Posts: 97
Joined: Thu Nov 03, 2011 3:15 am
Contact:

Re: Trouble with Line Intersection Code in Wiki

Post by verilog » Sat Jan 05, 2013 10:10 pm

Hello Gravy,

A while ago I faced the same problem while trying to figure out an algorithm for line intersection. It turns out that the algorithm fails due to computations that may produce results with rounding errors. The main problem is that numbers that should be equal, are in practice, unequal.

The error is more evident when dealing with horizontal or vertical segments. The problem seems to be the “det” variable, this variable, in some cases, should be exactly “0”, but because of the rounding error, it is not, but a very small value. Adding a tolerance (sometimes labelled "epsilon") value is one effective way of dealing with these precision errors.

Here's a small blog post that discusses this algorithm and the solution for rounding errors:

http://blogs.mathworks.com/loren/2011/0 ... es-part-2/

Gravy
Citizen
Posts: 80
Joined: Sun Jan 22, 2012 10:15 pm
Location: CA, USA

Re: Trouble with Line Intersection Code in Wiki

Post by Gravy » Sun Jan 06, 2013 6:06 pm

Interesting, thanks a lot. Good to know I'm not alone in this :)

Post Reply

Who is online

Users browsing this forum: Bing [Bot] and 23 guests