Thanks guys. So far the fuzzy/epsilon/delta method is working.
@ivan, yeah the problem is with using == operators with floats.
I spent over a week doing my incredibly comprehensive line intersection algo, so i'd stick with it a bit longer.
Here is it in all its glory.
Read and be awed. Or laugh at me.
Code: Select all
function get_line_intersection (lineA, lineB)
local Ax, Ay, d
-- m1= Am, m2 = Bm
local Am, Ab = lineA.m, lineA.b
local Bm, Bb = lineB.m, lineB.b
-- For this function to work, both lines need at least one defined point in them. This is the testing point Tx, Ty
-- for segments, we can take either of the points as Testing Points
--Lets define testing points for line A
if lineA.seg == true then
Ax = lineA.P1x
Ay = lineA.P1y
else
Ax = lineA.Tx
Ay = lineA.Ty
end
-- And line B
if lineB.seg == true then
Bx = lineB.P1x
By = lineB.P1y
else
Bx = lineB.Tx
By = lineB.Ty
end
-- Finding the min and max of the two points. This is used for checking if a point falls in a line.
local minAx, minAy, maxAx, maxAy, minBx, minBy, maxBx, maxBy
if lineA.seg == true and lineB.seg == true then
minAx = math.min(lineA.P1x, lineA.P2x)
maxAx = math.max(lineA.P1x, lineA.P2x)
minAy = math.min(lineA.P1y, lineA.P2y)
maxAy = math.max(lineA.P1y, lineA.P2y)
minBx = math.min(lineB.P1x, lineB.P2x)
maxBx = math.max(lineB.P1x, lineB.P2x)
minBy = math.min(lineB.P1y, lineB.P2y)
maxBy = math.max(lineB.P1y, lineB.P2y)
elseif lineA.seg == false and lineB.seg == true then
minAx = 0
maxAx = math.huge
minAy = 0
maxAy = math.huge
minBx = math.min(lineB.P1x, lineB.P2x)
maxBx = math.max(lineB.P1x, lineB.P2x)
minBy = math.min(lineB.P1y, lineB.P2y)
maxBy = math.max(lineB.P1y, lineB.P2y)
elseif lineA.seg == true and lineB.seg == false then
minAx = math.min(lineA.P1x, lineA.P2x)
maxAx = math.max(lineA.P1x, lineA.P2x)
minAy = math.min(lineA.P1y, lineA.P2y)
maxAy = math.max(lineA.P1y, lineA.P2y)
minBx = 0
maxBx = math.huge
minBy = 0
maxBy = math.huge
elseif lineA.seg == false and lineB.seg == false then
minAx = 0
maxAx = math.huge
minAy = 0
maxAy = math.huge
minBx = 0
maxBx = math.huge
minBy = 0
maxBy = math.huge
else
print("Some error with the line.seg attribute")
return {intersection = false}
end
-- First lets test for colinear and parallel lines
if Am == Bm or Am == -Bm then
print("Parallel Lines")
-- test for colinear lines
if Am == 0 and Bm == 0 then
print("Scenario : Am = Bm = 0")
-- here both have same y intercept
if Ay == By then
if lineA.seg == true and lineB.seg == true then
-- if both lines are segments, there is a chance they lie side by side
-- check if the points for any line lie between the bounding points of the other line
if (
(minAx <= minBx and minBx <= maxAx)
or (minAx <= maxBx and maxBx <= maxAx)
or (minBx <= minAx and minAx <= maxBx)
or (minBx <= maxAx and maxAx <= maxBx)
) then
print("Colinear Lines")
return {intersection = true, colinear = true}
else
print("Non Colinear Lines")
print("Lines lie Side by Side")
return {intersection = false}
end
else
-- if either of the lines is not a segment, then they will definitely be collinear
print("Colinear Lines")
return {intersection = true, colinear = true}
end
else
print("Non Colinear Lines")
return {intersection = false}
end
elseif (Am == math.huge or Am == -math.huge) and (Bm == math.huge or Bm == -math.huge) then
print("Scenario : Am = Bm = inf")
-- here both have same x intercept
if Ax == Bx then
if lineA.seg == true and lineB.seg == true then
-- if both lines are segments, there is a chance they lie side by side
-- check if the points for any line lie between the bounding points of the other line
if (
(minAy <= minBy and minBy <= maxAy)
or (minAy <= maxBy and maxBy <= maxAy)
or (minBy <= minAy and minAy <= maxBy)
or (minBy <= maxAy and maxAy <= maxBy)
) then
print("Colinear Lines")
return {intersection = true, colinear = true}
else
print("Non Colinear Lines")
print("Lines lie Side by Side")
return {intersection = false}
end
else
-- if either of the lines is not a segment, then they will definitely be collinear
print("Colinear Lines")
return {intersection = true, colinear = true}
end
else
print("Non Colinear Lines")
return {intersection = false}
end
else
print("Scenario : Am = Bm = valid")
print("Am = ", Am)
print("Bm = ", Bm)
print("Ab = ", Ab)
print("Bb = ", Bb)
-- local d = round((math.abs(Bb - Ab)) / (math.sqrt((Bm * Bm) + 1)))
-- print("d = ", d)
if Ab == Bb then
if lineA.seg == true and lineB.seg == true then
-- if both lines are segments, there is a chance they lie side by side
-- check if the points for any line lie between the bounding points of the other line
if (
(minAx <= minBx and minBx <= maxAx)
or (minAx <= maxBx and maxBx <= maxAx)
or (minBx <= minAx and minAx <= maxBx)
or (minBx <= maxAx and maxAx <= maxBx)
)
and
(
(minAy <= minBy and minBy <= maxAy)
or (minAy <= maxBy and maxBy <= maxAy)
or (minBy <= minAy and minAy <= maxBy)
or (minBy <= maxAy and maxAy <= maxBy)
) then
print("Colinear Lines")
return {intersection = true, colinear = true}
else
print("Non Colinear Lines")
print("Lines lie Side by Side")
return {intersection = false}
end
else
-- if either of the lines is not a segment, then they will definitely be collinear
print("Colinear Lines")
return {intersection = true, colinear = true}
end
else
print("Non Colinear Lines")
return {intersection = false}
end
end
else
-- print("Non parallel lines")
-- Am = 0 and Bm = inf
if Am == 0 and (Bm == math.huge or Bm == -math.huge) then
print("Scenario : Am = 0 and Bm = inf")
iy = Ay
ix = Bx
-- print(ix, iy)
-- Am = inf and Bm = 0
elseif (Am == math.huge or Am == -math.huge) and Bm == 0 then
print("Scenario : Am = inf and Bm = 0")
iy = By
ix = Ax
-- print(ix, iy)
-- Am = 0 and Bm = valid
elseif Am == 0 and (Bm ~= math.huge or Bm ~= -math.huge) then
print("Scenario : Am = 0 and Bm = valid")
iy = Ay
ix = (iy - Bb) / Bm
-- print(ix, iy)
-- Am = valid and Bm = 0
elseif (Am ~= math.huge or Am ~= -math.huge) and Bm == 0 then
print("Scenario : Am = valid and Bm = 0")
iy = By
ix = (iy - Ab) / Am
-- print(ix, iy)
-- Am = inf and Bm = valid
elseif (Am == math.huge or Am == -math.huge) and (Bm ~= math.huge or Bm ~= -math.huge) then
print("Scenario : Am = inf and Bm = valid")
ix = Ax
iy = (Bm * ix) + Bb
-- print(ix, iy)
-- Am = valid and Bm = inf
elseif (Am ~= math.huge or Am ~= -math.huge) and (Bm == math.huge or Bm == -math.huge) then
print("Scenario : Am = valid and Bm = inf")
ix = Bx
iy = (Am * ix) + Ab
-- print(ix, iy)
-- Am = valid and Bm = valid
elseif (Am ~= math.huge or Am ~= -math.huge) and (Bm ~= math.huge or Bm ~= -math.huge) then
print("Scenario : Am = valid and Bm = valid")
print("Am = ", Am)
print("Bm = ", Bm)
ix = -( (Bb - Ab)/(Bm - Am))
iy = (Bm * ix) + Bb
-- print(ix, iy)
else
print("WHAT IS THIS I CANT EVEN!")
print("UNHANDLED SCENARIO ALERT!!!")
end
-- Now that we have the Intersection points ix and iy, we need to check if they fall on the lines
-- for lines, the intersection points just being +ve is sufficient
-- for the intersection point to be valid, it should fall on both the lines
-- for the intersection point to be valid, it should fall on both the lines
if (
(minAx <= ix and ix <= maxAx)
and (minBx <= ix and ix <= maxBx)
and (minAy <= iy and iy <= maxAy)
and (minBy <= iy and iy <= maxBy)
) then
print("Found Intersection!")
return {intersection = true, colinear = false, ix = round(ix), iy = round(iy)}
else
-- print("Found NO Intersection!")
return {intersection = false}
end
end
end
