Line - Line Intersection

Games
#1

Hi everyone,

I am trying to make a sample following this instruction

http://www.emanueleferonato.com/2012/01/25/the-concept-behind-stringy-flash-game-determine-if-a-sprite-is-inside-a-lasso/

But I can’t understand why his performance is so smooth but mine is badly delayed :frowning:

local HEIGHT = display.contentHeight  
local WIDTH = display.contentWidth  
   
local lines = {}  
local point = {}  
local line\_number = 1  
local line\_remove = 1  
local line\_width = 5  
local tailNodes = 90  
local prev\_x, prev\_y, ball  
  
   
for i=1,tailNodes do  
 point[i] = display.newCircle( WIDTH/2, HEIGHT/2, 5 )  
end  
  
local function lineIntersection(Point1,Point2,Point3,Point4)  
 --Line 1: 1 + 2  
 --Line 2: 3 + 4  
 local x1 = Point1.x;  
 local x2 = Point2.x;  
 local x3 = Point3.x;  
 local x4 = Point4.x;  
 local y1 = Point1.y;  
 local y2 = Point2.y;  
 local y3 = Point3.y;  
 local y4 = Point4.y;  
  
 --Check if two line are parallel or coincident  
 if (((x1-x2)\*(y3-y4))-((y1-y2)\*(x3-x4)) == 0) then  
 return nil;  
 end  
 --Calculate intersection point  
 local px = (((((x1\*y2)-y1\*x2)\*(x3-x4))-(x1-x2)\*((x3\*y4)-y3\*x4))/(((x1-x2)\*(y3-y4))-(y1-y2)\*(x3-x4)));  
 local py = (((((x1\*y2)-y1\*x2)\*(y3-y4))-(y1-y2)\*((x3\*y4)-y3\*x4))/(((x1-x2)\*(y3-y4))-(y1-y2)\*(x3-x4)));  
 --Line 1 lenght  
 local segment1Len = math.pow(Point1.x-Point2.x,2) + math.pow(Point1.y-Point2.y,2);  
 --Line 2 lenght  
 local segment2Len = math.pow(Point3.x-Point4.x,2) + math.pow(Point3.y-Point4.y,2);  
  
 --Check if intersection point is inside 4 point  
 if (math.pow(Point1.x-px,2)+math.pow(Point1.y-py,2)\>segment1Len) then  
 return nil;  
 end  
 if (math.pow(Point2.x-px,2)+math.pow(Point2.y-py,2)\>segment1Len) then  
 return nil;  
 end  
 if (math.pow(Point3.x-px,2)+math.pow(Point3.y-py,2)\>segment2Len) then  
 return nil;  
 end  
 if (math.pow(Point4.x-px,2)+math.pow(Point4.y-py,2)\>segment2Len) then  
 return nil;  
 end  
  
 --Store Intersection Point  
 local interSectionPoint = {x = px, y = py}   
  
 return interSectionPoint;  
end   
   
local function draw\_line(e)  
  
  
 local sampleNodes = {}  
 for i = 1,(#point) do  
 if (i == 90) then  
 point[i].x = e.x  
 point[i].y = e.y  
 else  
 point[i].x = point[i+1].x  
 point[i].y = point[i+1].y   
 end  
  
 if (i % 3 == 0 or i == tailNodes - 2) then  
 sampleNodes[#sampleNodes + 1] = point[i]  
 end  
 end  
  
 for i=1,(#sampleNodes - 1) do  
 for j=i+2,(#sampleNodes - 1) do  
 local intersectionPoint = lineIntersection(sampleNodes[j+1],sampleNodes[j],sampleNodes[i+1],sampleNodes[i]);  
 if (intersectionPoint~=nil) then  
 print("intersect")  
 end  
  
 end  
 end  
end  
  
Runtime:addEventListener("touch", draw\_line)

Plese help me D: [import]uid: 111309 topic_id: 21898 reply_id: 321898[/import]

#2

without putting too much thought into it

you could localize math.pow instead of calling it 12 times times tailNodes in the intersect call.
try in line 12 add

local pow = math.pow

then repleace all the math.pow in intersect funciton to

local segment1Len = pow(Point1.x-Point2.x,2) + pow(Point1.y-Point2.y,2);

[import]uid: 24 topic_id: 21898 reply_id: 87141[/import]

#3

I gave it a try but it still delays so bad. Do you have any other suggestions ? :frowning: [import]uid: 111309 topic_id: 21898 reply_id: 87222[/import]

#4

Does it work with less points or lower FPS? [import]uid: 10389 topic_id: 21898 reply_id: 87223[/import]

#5

Less points make it looks short :slight_smile:

I have never try FPS before so i am not sure about it

But never mind, I have figured out how to solve this, thank you for your concerning

Here is solution if anyone interested, it is still not the best. Give me your advices if you have some :wink:

[code]
local HEIGHT = display.contentHeight
local WIDTH = display.contentWidth

local lines = {}
local point = {}
local sampleNodes = {}
local tailNodes = 90
local pow = math.pow
–local count = 0;

local background = display.newImage( “background.png” )

for i=1,tailNodes do
point[i] = display.newCircle( 0, 0, 5 )
point[i]:setFillColor( 0, 0, 0)
if (i % 3 == 0) then
sampleNodes[#sampleNodes + 1] = point[i]
end
end

local function lineIntersection(Point1,Point2,Point3,Point4)
–Line 1: 1 + 2
–Line 2: 3 + 4
local x1 = Point1.x;
local x2 = Point2.x;
local x3 = Point3.x;
local x4 = Point4.x;
local y1 = Point1.y;
local y2 = Point2.y;
local y3 = Point3.y;
local y4 = Point4.y;

–Check if two line are parallel or coincident
if (((x1-x2)*(y3-y4))-((y1-y2)*(x3-x4)) == 0) then
return nil;
end
–Calculate intersection point
local px = (((((x1*y2)-y1*x2)*(x3-x4))-(x1-x2)*((x3*y4)-y3*x4))/(((x1-x2)*(y3-y4))-(y1-y2)*(x3-x4)));
local py = (((((x1*y2)-y1*x2)*(y3-y4))-(y1-y2)*((x3*y4)-y3*x4))/(((x1-x2)*(y3-y4))-(y1-y2)*(x3-x4)));
–Line 1 lenght
local segment1Len = pow(Point1.x-Point2.x,2) + pow(Point1.y-Point2.y,2);
–Line 2 lenght
local segment2Len = pow(Point3.x-Point4.x,2) + pow(Point3.y-Point4.y,2);

–Check if intersection point is inside 4 point
if (pow(x1-px,2)+pow(y1-py,2)>segment1Len) then
return nil;
end
if (pow(x2-px,2)+pow(y2-py,2)>segment1Len) then
return nil;
end
if (pow(x3-px,2)+pow(y3-py,2)>segment2Len) then
return nil;
end
if (pow(x4-px,2)+pow(y4-py,2)>segment2Len) then
return nil;
end

–Store Intersection Point
local interSectionPoint = {x = px, y = py}

return interSectionPoint;
end

local function draw_line(e)

if e.phase == “began” then
elseif e.phase == “moved” then
–count = count + 1
for i = 1,(#point) do
if (i == 90) then
point[i].x = e.x
point[i].y = e.y
else
point[i].x = point[i+1].x
point[i].y = point[i+1].y
end
end
–[[
print(point[1].x … " … " … point[1].y)
print(point[12].x … " || " … point[12].y)
if (count % 3 == 0 ) then
for i=1,(#sampleNodes) do
print(“before” … sampleNodes[i].x)
end
–table.remove (sampleNodes,1)
for i=1,(#sampleNodes) do
print(“now” … sampleNodes[i].x)
end
–sampleNodes[#sampleNodes + 1] = point[12]
for i=1,(#sampleNodes) do
print(“after” … sampleNodes[i].x)
end
end]]–
elseif e.phase == “ended” then
–print(#sampleNodes)
–[[
for i=1,(#sampleNodes - 1) do
for j=i+2,(#sampleNodes - 1) do
print(sampleNodes[j+1])
local intersectionPoint = lineIntersection(sampleNodes[j+1],sampleNodes[j],sampleNodes[i+1],sampleNodes[i]);
if (intersectionPoint~=nil) then
print(“intersect”)
end
end
end
for i=1,(#sampleNodes) do
print(i … “:” … sampleNodes[i].x … " - " … sampleNodes[i].y)
end]]–
end
end

local function checkIntersection()
for i=1,(#sampleNodes - 1) do
for j=i+2,(#sampleNodes - 1) do
local intersectionPoint = lineIntersection(sampleNodes[j+1],sampleNodes[j],sampleNodes[i+1],sampleNodes[i]);
if (intersectionPoint~=nil) then
print(“intersect”)
else
end
end
end
end

background:addEventListener(“touch”, draw_line)
Runtime:addEventListener(“enterFrame”, checkIntersection)
[/code] [import]uid: 111309 topic_id: 21898 reply_id: 87227[/import]