How to test if to lines intersect

[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

[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

[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.

[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

[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.

[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

[milon]

Rosetta Code is also a good resource: https://rosettacode.org/wiki/Find_the_i ... _lines#Lua

[pgimeno]

If scalar can be negative than it's not scalar anymore

Why?

[darkfrei]

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.

[pgimeno]

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)