# Two Intersecting Lines

I have a Line class that I am using to save information about Lines in my project and I’ve come to a part where I am confused on how to progress. I have a vector3 StartPos and a vector3 EndPos for every line. How can I determine if two of my lines are intersecting using these vectors? I’d appreciate any guidance.

This task requires mathematical knowledge. Assuming you’re solving this in 2D, check out this thread . Ask here if you need more help.

2 Likes

Here’s a complete solution modified so that it works with vanilla API

``````using System;
using UnityEngine;

using static MathF;

public static class LinesUtils {

// returns true if the intersection exists, false otherwise
// the actual point is returned through the 'out' parameter
public static bool Intersect(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersect, Mode mode = Mode.Segments) {

// default intersection point in case none exists
intersect = new Vector2(float.NaN, float.NaN);

// check the bounding rectangles (optimization for segments only)
if(mode == Mode.Segments) {
var ar = rectFromSeg(a1, a2);
var br = rectFromSeg(b1, b2);
if(!ar.Overlaps(br)) return false;
}

// compute point of intersection using homogeneous coordinates
var aa = Vector3.Cross(hp(a1), hp(a2));
var bb = Vector3.Cross(hp(b1), hp(b2));
var cc = Vector3.Cross(aa, bb);

// if Z is close to 0, no point of intersection exists
if(Abs(cc.z) < 1E-6f) return false;

// otherwise, compute the actual point in 2D
var x = ((Vector2)cc) * (1f / cc.z);

// test the intersection interval for rays and segments
if(mode switch {
Mode.Rays => !test(x, a1, a2) || !test(x, b1, b2),
Mode.RayLine => !test(x, a1, a2),
Mode.RaySegment => !test(x, a1, a2) || !test(x, b1, b2, bidi: true),
Mode.Segments => !test(x, a1, a2, bidi: true) || !test(x, b1, b2, bidi: true),
_ => false // lines can't fail at this
}) return false;

// adopt the 2D solution and return it
intersect = x;
return true;

// -- local functions --
// conversion to homogeneous coordinates
static Vector3 hp(Vector2 p) => new Vector3(p.x, p.y, 1f);

// interval test; segments are bidi(rectional), rays are not
static bool test(Vector2 p, Vector2 a, Vector2 b, bool bidi = false) {
int i = Abs(b.x - a.x) < Abs(b.y - a.y)? 1 : 0;
float n = p[i] - a[i], d = b[i] - a[i]; // numerator and denominator of inverse lerp
if(bidi && Abs(n) > Abs(d)) return false; // interval test for segments
return n >= 0f == d >= 0f; // interval test for rays and segments
}

// produces a rectangle that encapsulates two arbitrary points
static Rect rectFromSeg(Vector2 a, Vector2 b) {
var min = leastOf(a, b);
return new Rect(min, mostOf(a, b) - min);
}

static Vector2 leastOf(Vector2 a, Vector2 b) => new Vector2(Min(a.x, b.x), Min(a.y, b.y));
static Vector2 mostOf(Vector2 a, Vector2 b) => new Vector2(Max(a.x, b.x), Max(a.y, b.y));

}

public enum Mode {
Lines,
Rays,
RayLine,
RaySegment,
Segments
}

}
``````

Providing some more information about your use case might be helpful. Lines in 3D rarely intersect. Even if you had set some lines up so you know that mathematically an intersection will occur, inaccuracies in floating point computations can incorrectly determine the lines won’t intersect. An approach you can take for deciding if lines intersect in 3D space is to get the closest points of your two lines. You can determine if the lines intersect if the distance between the two points is less than some threshold. I’d recommend a book called Real Time Collision Detection. It has all the information you need to solve this problem.

As was stated, line in 3-space seldom intersect.

Also… if they do, due to the nature of floats and float error, getting exact tests requires some epsilon.

Here’s a line struct I wrote ages ago… it has an intersect test in it using an epsilon of 0.0001. Probably should have made that value configurable… but I wrote it ages ago. So it goes.

1 Like

You’re right I should have specified. I am working in 2d. Thank you very much for your suggestion, I’ll look into it.

Thank you very much for your help, I truly do appreciate it. I am quite new still to unity so this is all great help.

1 Like