How to test if to lines intersect

General discussion about LÖVE, Lua, game development, puns, and unicorns.
Purple Fedora
Prole
Posts: 23
Joined: Fri Oct 26, 2018 8:41 pm

How to test if to lines intersect

Post by Purple Fedora »

I have 2 points and an line in between them.
I now the X and Y coordinates of the Points.
How can i test if the lines? Is there an Formular?

TIA
User avatar
4vZEROv
Party member
Posts: 126
Joined: Wed Jan 02, 2019 8:44 pm

Re: How to test if to lines intersect

Post by 4vZEROv »

Learn how to use google mate.

Everything you need for 2d collision detection is here :
http://www.jeffreythompson.org/collisio ... ntents.php

And since i'm such a good person :

Code: Select all

function line_line(x1, y1, x2, y2, x3, y3, x4, y4)
  local uA = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  local uB = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  return uA >= 0 and uA <= 1 and uB >= 0 and uB <= 1
end
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: How to test if to lines intersect

Post by ivan »

The code above could be optimized using "early bailout" as described in my tutorial:
https://2dengine.com/?p=intersections#S ... vs_segment
Furthermore it shows how to find the point of intersection.
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: How to test if to lines intersect

Post by darkfrei »

There is a very cheap solution to check if two lines have intersection (boolean):

You have two lines, AB and CD.
If the sine of angle between AB and AC is positive and sine of angle AB and AD is positive too, then there is no intersection.
Same if both are negative.
The intersection is _possible_ if only one of them is positive and the another one is negative.
The intersection _exists_ if points C and D are on the opposite sides of line AB _AND_ if points A and B are on the opposite sides of line CD.

Main function:

Code: Select all

function pseudoScalarMutiplication (ax, ay, bx, by)
	return ax*by-ay*bx
end
As you know, the negative product is possible if only one of multipliers is negative:

Code: Select all

AB = {x=Bx-Ax, y=By-Ay} -- where Ax, Ay is a position of point A; Bx, By - position of point B
AC = {x=Cx-Ax, y=Cy-Ay}
AD = {x=Dx-Ax, y=Dy-Ay}
-- check if points C and D are on the one side of line AB:
local value = pseudoScalarMutiplication (AB.x, AB.y, AC.x, AC.y) * pseudoScalarMutiplication (AB.x, AB.y, AD.x, AD.y)
if value > 0 then
	-- no intersection: both are positive or both are negative
else
	-- the intersection is _possible_
	-- check if points A and B are on the one side of line CD:
	CD = {x=Dx-Cx, y=Dy-Cy}
	CA = {x=Ax-Cx, y=Ay-Cy}
	CB = {x=Bx-Cx, y=By-Cy}
	local value = pseudoScalarMutiplication (CD.x, CD.y, CA.x, CA.y) * pseudoScalarMutiplication (CD.x, CD.y, CB.x, CB.y)
	if value > 0 then
		-- no intersection: both are positive or both are negative
	else
		-- 100% intersection!
	end
else
end
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
pgimeno
Party member
Posts: 3541
Joined: Sun Oct 18, 2015 2:58 pm

Re: How to test if to lines intersect

Post by pgimeno »

What you call "pseudo scalar multiplication" is actually a regular scalar multiplication by the normal. The sine of the angle between vector A and vector B is the same as the cosine of the angle between the normal to vector A and vector B.

A normal of a vector (in particular the counter-clockwise rotation of 90° of the vector) can be obtained by swapping the components and then negating the first:

normal(<x, y>) = <-y, x>

So, if dot(a, b) = ax * bx + ay * by, then dot(normal(a), b) = (-ay) * bx + (ax) * by (I've put in parentheses the components that have been replaced to obtain the normal). That's the same as your formula.
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: How to test if to lines intersect

Post by darkfrei »

If scalar can be negative than it's not scalar anymore :) But the pseudoscalar can be positive or negative.

Small optimization:

Code: Select all

function isIntersection (x1, y1, x2, y2, x3, y3, x4, y4)
-- line segments AB: x1, y1, x2, y2 and CD: x3, y3, x4, y4
	local abx, aby = (x2-x1), (y2-y1) -- main vector ab
	local acx, acy = (x3-x1), (y3-y1) -- vector ac
	local adx, ady = (x4-x1), (y4-y1) -- vector ad
	local u = (abx*acy - aby*acx)*(abx*ady - aby*adx)
	if u > 0 then return false end
	local bcx, bcy = (x3-x2), (y3-y2) -- vector bc 
	local dcx, dcy = (x3-x4), (y3-y4) -- main vector dc (vector ac is above)
	local v = (dcx*acy - dcy*acx)*(dcx*bcy - dcy*bcx)
	if v > 0 then return false end
	return true
end
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
milon
Party member
Posts: 472
Joined: Thu Jan 18, 2018 9:14 pm

Re: How to test if to lines intersect

Post by milon »

Rosetta Code is also a good resource: https://rosettacode.org/wiki/Find_the_i ... _lines#Lua
Any code samples/ideas by me should be considered Public Domain (no attribution needed) license unless otherwise stated.
User avatar
pgimeno
Party member
Posts: 3541
Joined: Sun Oct 18, 2015 2:58 pm

Re: How to test if to lines intersect

Post by pgimeno »

darkfrei wrote: Thu Dec 08, 2022 11:39 am If scalar can be negative than it's not scalar anymore :)
Why?
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: How to test if to lines intersect

Post by darkfrei »

pgimeno wrote: Thu Dec 08, 2022 6:05 pm
darkfrei wrote: Thu Dec 08, 2022 11:39 am If scalar can be negative than it's not scalar anymore :)
Why?
Because it's scalar :)
https://mathworld.wolfram.com/Pseudoscalar.html

For example scalar is an amount of driven kilometers or the speed of spaceship, it's positive in all directions.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
pgimeno
Party member
Posts: 3541
Joined: Sun Oct 18, 2015 2:58 pm

Re: How to test if to lines intersect

Post by pgimeno »

darkfrei wrote: Thu Dec 08, 2022 6:16 pm Because it's scalar :)
https://mathworld.wolfram.com/Pseudoscalar.html

For example scalar is an amount of driven kilometers or the speed of spaceship, it's positive in all directions.
I don't think you're understanding the concept of a scalar and a pseudoscalar correctly. If you're talking physics, charge is a scalar and can be negative, for example.
  • Examples of scalar quantities are mass, distance, charge, volume, time, speed [...]
https://en.wikipedia.org/wiki/Scalar_(physics)

If you're talking 2D and 3D math, which is what we're talking about here, scalars are real numbers.
  • In linear algebra, real numbers or generally elements of a field are called scalars and relate to vectors in an associated vector space through the operation of scalar multiplication (defined in the vector space), in which a vector can be multiplied by a scalar in the defined way to produce another vector.
https://en.wikipedia.org/wiki/Scalar_(mathematics)
Post Reply

Who is online

Users browsing this forum: Google [Bot] and 21 guests