Intersection between two lines

There are many useful functions in FMath to determine intersections e.g. between a line and a box, a line and a plane … but not to calculate the intersection of two lines. Or is there one?

For all those who are interested I found a working solution here Find the point of intersection of two 3D line segments, works in 2D if z=0 · GitHub and implemented a simple function for UE (I only did 2 tests for the method):

bool PCGUtils::lineToLineIntersection(const FVector& fromA, const FVector& fromB, const FVector& toA, const FVector& toB, FVector& _outIntersection)
{
	FVector da = fromB - fromA;
	FVector db = toB - toA;
	FVector dc = toA - fromA;

	if (FVector::DotProduct(dc, FVector::CrossProduct(da, db)) != 0.0) {
		return false;
	}

	FVector crossDaDb = FVector::CrossProduct(da, db);
	float prod = crossDaDb.X * crossDaDb.X + crossDaDb.Y * crossDaDb.Y + crossDaDb.Z * crossDaDb.Z;

	float res = FVector::DotProduct(FVector::CrossProduct(dc, db), FVector::CrossProduct(da, db) / prod);
	if (res >= 0.0f && res <= 1.0f) {
		_outIntersection = fromA + da * FVector(res, res, res);
		return true;
	}

	return false;
}

This method is right basically…But there are some point that may haven’t be considered…

if (res >= 0.0f && res <= 1.0f)

This condition can not include all the situation…

For example…

Line a and line b will not intersect…Just like the picture i give below…But it will return true.Because the cross point is on line a.
In order to make it right,it must consider if the intersect point is on line b too…

What’s more ,I found some different from your answer and the answer on github…
On github,the answer is

float res = FVector::DotProduct(FVector::CrossProduct(dc, db), FVector::CrossProduct(da, db)) / prod;

Your answer is

float res = FVector::DotProduct(FVector::CrossProduct(dc, db), FVector::CrossProduct(da, db) / prod);

There are some different about “)”…

I havn’t test which one is right .But I’m using the github answer and it looks right…

Thanks for the solution you provides. It helps me a lot.

104390-1.png

I make some change for this function.
Check if the intersect point is on line a and line b at the same time.
Here is the code

_outIntersection = fromA + da * FVector(res, res, res);

FVector fromAToIntersectPoint = _outIntersection - fromA;
FVector fromBToIntersectPoint = _outIntersection - fromB;
FVector toAToIntersectPoint = _outIntersection - toA;
FVector toBToIntersectPoint = _outIntersection - toB;
if (FVector::DotProduct(fromAToIntersectPoint, fromBToIntersectPoint) <= 0 && FVector::DotProduct(toAToIntersectPoint, toBToIntersectPoint) <= 0)
{
	return true;
}
return false;

}

Well.Unfortunately,this is still not the correct answer…I forget the paralla situation…

if (FVector::DotProduct(dc, FVector::CrossProduct(da, db)) != 0.0) {
return false;
}

This function can not check the paralla situation…So I made some change…
Here is the final code…

    FVector da = fromB - fromA;
FVector db = toB - toA;
FVector dc = toA - fromA;

FVector crossDaDb = FVector::CrossProduct(da, db);
float prod = crossDaDb.X * crossDaDb.X + crossDaDb.Y * crossDaDb.Y + crossDaDb.Z * crossDaDb.Z;
if(prod == 0 || FVector::DotProduct(dc,crossDaDb) != 0)
{
	return false;
}
float res = FVector::DotProduct(FVector::CrossProduct(dc, db), FVector::CrossProduct(da, db)) / prod;

_outIntersection = fromA + da * FVector(res, res, res);

FVector fromAToIntersectPoint = _outIntersection - fromA;
FVector fromBToIntersectPoint = _outIntersection - fromB;
FVector toAToIntersectPoint = _outIntersection - toA;
FVector toBToIntersectPoint = _outIntersection - toB;
if (FVector::DotProduct(fromAToIntersectPoint, fromBToIntersectPoint) <= 0 && FVector::DotProduct(toAToIntersectPoint, toBToIntersectPoint) <= 0)
{
	return true;
}
return false;
1 Like

If you want a really functional solution which takes into account all possible configurations (including segments being points) here it is.

If segments overlap it returns the first point of intersection from the first segment’s point of view.

bool FindPointSegmentIntersection(const FVector Point, const FVector SegmentStart,
                                                const FVector SegmentEnd)
{
	const FVector Da = Point - SegmentStart;
	const FVector Db = SegmentEnd - SegmentStart;
	if (FVector::CrossProduct(Da, Db).IsNearlyZero())
	{
		const float Res = Da.SizeSquared() / Db.SizeSquared();
		const float DotProd = FVector::DotProduct(Da, Db);
		if (DotProd >= 0 && 0 <= Res && Res <= 1)
		{
			return true;
		}
	}
	return false;
}


bool FindSegmentSegmentIntersection(const FVector Segment1Start, const FVector Segment1End,
                                                  const FVector Segment2Start, const FVector Segment2End,
                                                  FVector& IntersectionPoint)
{
	// both points
	if (Segment1Start == Segment1End && Segment2Start == Segment2End)
	{
		if (Segment1Start == Segment2Start)
		{
			IntersectionPoint = Segment1Start;
			return true;
		}
		return false;
	}

	//segment 1 is point
	if (Segment1Start == Segment1End)
	{
		if (FindPointSegmentIntersection(Segment1Start, Segment2Start, Segment2End))
		{
			IntersectionPoint = Segment1Start;
			return true;
		}
		return false;
	}

	//segment 2 is point
	if (Segment2Start == Segment2End)
	{
		if (FindPointSegmentIntersection(Segment2Start, Segment1Start, Segment1End))
		{
			IntersectionPoint = Segment2Start;
			return true;
		}
		return false;
	}

	//both segments
	const FVector S1Delta = Segment1End - Segment1Start;
	const FVector S2Delta = Segment2End - Segment2Start;
	const FVector Delta = Segment2Start - Segment1Start;
	const FVector Cross = FVector::CrossProduct(S1Delta, S2Delta);

	if (Cross.IsNearlyZero())
	{
		if (!FVector::CrossProduct(Delta, S2Delta).IsNearlyZero())
		{
			//parallel
			return false;
		}
		//overlap
		const float T0 = FVector::DotProduct(Delta, S1Delta) / S1Delta.SizeSquared();
		const float T1 = T0 + FVector::DotProduct(S2Delta, S1Delta) / S1Delta.SizeSquared();
		if (T0 <= 0 && T0 <= 1)
		{
			IntersectionPoint = Segment1Start + (S1Delta * T0);
			return true;
		}
		if (T0 <= 0 && 0 <= T1)
		{
			IntersectionPoint = Segment1Start;
			return true;
		}
		if (0 <= T1 && T1 <= 1)
		{
			IntersectionPoint = Segment1Start + (S1Delta * T0);
			return true;
		}
		if (T0 <= 1 && 1 <= T1)
		{
			IntersectionPoint = Segment1Start;
			return true;
		}
		return false;
	}

	if (!FMath::IsNearlyZero(FVector::DotProduct(Delta, Cross)))
	{
		//skew
		return false;
	}

	FVector Cross1 = FVector::CrossProduct(Delta, S1Delta);
	const FVector Cross2 = FVector::CrossProduct(Delta, S2Delta);
	FVector Start = Segment2Start;
	FVector SDelta = S2Delta;
	if (Cross1.IsNearlyZero())
	{
		Cross1 = Cross2;
		Start = Segment1Start;
		SDelta = S1Delta;
	}

	const float Dot1 = FVector::DotProduct(Cross1, Cross);
	const float Dot2 = FVector::DotProduct(Cross2, Cross);
	const float Denom = Cross.SizeSquared();

	if (0 <= Dot1 && Dot1 <= Denom && 0 <= Dot2 && Dot2 <= Denom)
	{
		IntersectionPoint = Start + (SDelta * (Dot1 / Denom));
		return true;
	}
	return false;