Trouble with Line Intersection Code in Wiki

[Gravy]

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

[mathacka]

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]

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

[verilog]

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]

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