## 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
Gravy
Citizen
Posts: 80
Joined: Sun Jan 22, 2012 10:15 pm
Location: CA, USA

### Trouble with Line Intersection Code in Wiki

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)
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

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

### Re: Trouble with Line Intersection Code in Wiki

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

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

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

### Re: Trouble with Line Intersection Code in Wiki

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

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

### Who is online

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