Code is tl;dr at the bottom
It’s a relatively simple thing (for most of us anyway) but here I’ve solved it somewhat unorthodoxly. And I’m thinking wow this should come bundled with Unity, with how complete it turned out, at least in 2D.
Let’s try something different: 2D line intersection via homogeneous coordinates.
Hey I’m not an expert actually, but I know about homogeneous coordinates from working with barycentric coordinates, which are also homogeneous (you get them in HitInfo from Raycast for example). This is a pretty opaque topic in (common) geometry, one I won’t bother you too much with (and psh I don’t know what I’m talking about anyway), but what I know is that homogeneous coordinates live in a different space compared to Cartesian, where they nearly always satisfy some internally binding rule (i.e. you can usually scale them uniformly and this won’t change their meaning, which is kind of a weird “zooming” property for a coordinate system). This gives them some unique properties which is why they were invented in the first place.
Anyway, turns out you can intersect lines in 2D by using them and it’s as easy as peanuts. It’s not so easy to find an example though, so I had to scour through numpy freaks and AI research (sarcasm: yummy, my favorite activities). But after about a day, I got it working without too much hassle, and I wish you all to never have to go through that.
So what it’s all about? Well, you start by defining two lines with 2D points (a1, a2) and (b1, b2). So four points in total. Then you augment the coordinates by appending 1 as the third coordinate, as if they were in 3D, and whoa, we just got our homogeneous coordinates. Sounds so stupid and useless.
Then you cross the point pairs to define two lines in space. That’s how you do it, don’t ask me why. And then you cross the lines again. Again, don’t ask m… because that’s obviously a method for intersecting lines, alright, we ok now?
And what you got in the end is the point of intersection in homogeneous space.
static Vector2 intersectLines(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2) {
return (Vector2)(hp(a1).Cross(hp(a2))).Cross(hp(b1).Cross(hp(b2)));
}
// hp = homogeneous point, erm or whatever it is
static Vector3 hp(Vector2 pt) => new Vector3(pt.x, pt.y, 1f);
Wait, WHAT?
“You’re kidding right? That can’t possibly work”
You’re right, it can’t. This is all a bad joke, I’m sorry. UNTIL
you realize you need to scale this heavenly result down to proper legit down-to-earth glorious space we all know and love, by using that magical third component.
static Vector2 intersectLines(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2) {
Vector3 cc = (hp(a1).Cross(hp(a2))).Cross(hp(b1).Cross(hp(b2)));
return ((Vector2)cc) / cc.z;
}
Man, this is so crazy! I love it.
Btw I’m using my own libraries to type this down, and this Cross is the same as using Vector3.Cross, I just like a.Cross(b) better than Vector3.Cross(a, b). But a cross is a cross.
If I did my math correctly (edit: I did not, but I fixed it), this is what actually happens (after simplifying multiplications with 1)
X: (ha2.x - ha1.x) * (hb1.x * hb2.y - hb1.y * hb2.x) - (hb2.x - hb1.x) * (ha1.x * ha2.y - ha1.y * ha2.x),
Y: (hb1.y - hb2.y) * (ha1.x * ha2.y - ha1.y * ha2.x) - (ha1.y - ha2.y) * (hb1.x * hb2.y - hb1.y * hb2.x),
Z: (ha1.y - ha2.y) * (hb2.x - hb1.x) - (ha2.x - ha1.x) * (hb1.y - hb2.y)
which actually looks sensible. (You can also use this if you want the heart of it not to include any function calls, for performance.)
It turns out that if Z ends up being 0, there is no intersection either due to lines being parallel or coincident (in 2D there are no skewed lines).
You can find thorough explanations why this works (geometrically; numerically it looks the same as the algebraic solving-the-line-equations solution, only more robust). Here’s one of the explanations with a picture if any of it makes any sense to you (it doesn’t to me, I’m like “awkay” and it’s all very awkward, don’t be like me).
Anyway, that was part I of this adventure. Let’s now build a proper thing to round this off. Intersect methods typically return a short answer to a question “is there intersection at all?” and then shamelessly and unceremoniously plop the actual point sideways. Like so
static bool intersectLines(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersect) {
intersect = something;
return success;
}
Let’s now try to make a segment intersection with the weird homogeneous stuff, because that’s usually much more useful than having infinite lines intersect wherever.
You can optimize segment intersection slightly by checking the bounding boxes first, and cancel the whole thing if the boxes do not overlap. But let’s ignore the Bounds struct, that’s for 3D, we can use Rect instead. The Rect is produced from the minimum corner (the one toward origin) and size. How can we easily determine what corner is the minimum for an arbitrary segment, especially if we consider all kinds of wild orientations for its two points?
Well, we can find the component-wise minmax. This is one way to do it
static Rect rectFromSeg(Vector2 a, Vector2 b) {
var min = Vectx.LeastOf(a, b);
return new Rect(min, Vectx.MostOf(a, b) - min);
}
Pretty clean. LeastOf, just to illustrate the point, is functionally equivalent to
static Vector2 LeastOf(Vector2 a, Vector2 b) => new Vector2(Math.Min(a.x, b.x), Math.Min(a.y, b.y));
Now we can attack the segment intersect method with more tools.
static bool intersectLines(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersect) {
intersect = new Vector2(float.NaN, float.NaN);
var ar = rectFromSeg(a1, a2);
var br = rectFromSeg(b1, b2);
if(!ar.Overlaps(br)) return false; // quick and easy
var cc = (hp(a1).Cross(hp(a2))).Cross(hp(b1).Cross(hp(b2)));
if(cc.z.Abs() < 1E-6f) return false; // skip the last piece (and avoid division by zero)
intersect = ((Vector2)cc) * (1f / cc.z); // this replaces two divisions with one division and two multiplications
return true;
// local functions
static Vector3 hp(Vector2 pt) => new Vector3(pt.x, pt.y, 1f);
}
But this doesn’t work yet. Sure it finds the intersection like it did before, but doesn’t treat our segments as of finite length. It can happen that the boxes overlap even though the segments don’t.
We have to check whether the resulting point actually lies within the interval of both segments. To do this, we again >shift< inside the “segment space” and there we claim that the starting point is as good as 0, and that the end point is as good as 1. The point has to lie inside this interval. If it’s less than 0 or greater than 1, it’s outside of the interval, and not included in the segment. This suddenly smells like a good ol’ linear interpolation.
Indeed, that’s the lerp (or more precisely LerpUnclamped). We can always pretend that we have two points on a line and lerp between them with some interpolant t and this will yield us some point on this imaginary line, where 0 lands on the start, and 1 lands on the end. However, in this case, we got it backwards, we already have the point… and we’d like to get our t back! Yet there is no Vector2.InverseLerp, only Mathf.InverseLerp, so we’ll have to think out of the box a little to figure it all out.
The test boils down to this surprisingly non-pseudo code
static bool test(Vector2 p, Vector2 a, Vector2 b)
=> p.LerpedBetween(a, b).InRange(0f, 1f);
‘Is this point within the interval of 0 and 1 as interpolated between some points a and b?’ yes/no
static bool intersectLines(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersect) {
intersect = new Vector2(float.NaN, float.NaN);
var ar = rectFromSeg(a1, a2);
var br = rectFromSeg(b1, b2);
if(!ar.Overlaps(br)) return false;
var cc = (hp(a1).Cross(hp(a2))).Cross(hp(b1).Cross(hp(b2)));
if(cc.z.Abs() < 1E-6f) return false;
var x = ((Vector2)cc) * (1f / cc.z);
// both segments must contain the point
if(!test(x, a1, a2) || !test(x, b1, b2)) return false;
intersect = x;
return true;
// local functions
static Vector3 hp(Vector2 pt) => new Vector3(pt.x, pt.y, 1f);
static bool test(Vector2 p, Vector2 a, Vector2 b) => p.LerpedBetween(a, b).InRange(0f, 1f);
}
But we ought to figure out how to lower down the test function before we can try this out.
Lerp and Inverse Lerp
Here’s how to think about inverse lerps when there are more dimensions than 1. You can pick any one dimension and apply the inverse lerp there and it’ll work. For example just X. But here’s a caveat: imagine a line going straight horizontally, for example, its start is at (-1, 1) and its end at (5, 1), if you pick its X dimension, you’re fine, because there is so much meat to extrapolate from, because it goes from -1 to 5 so there is a proper change in its attitude; but if you pick its Y dimension, nothing happens, there is nothing to lerp in between, no change at all. So that’s the thing, you can pick any dimension, as long as there is some change recorded in it, so why not pick the one that records the greatest change (aka the delta)? That’s one way to ensure the best possible precision.
Lerp in general can be thought of as a mix of two interpolated values, where one grows at the expense of another. Thus x = a(1-t) + bt, whereas an inverse of that would look like this
x = a(1-t) + bt // we want t out
x = a(1-t) + bt // apply a
x = a - at + bt // rearrange
x = a + bt - at // put t in front
x = a + t(b - a) // move a to the left, then swap
t(b - a) = x - a // divide everything by (b - a)
t = (x - a) / (b - a)
Here it becomes obvious that when there is no delta between a and b, the solution is undefined, because we end up dividing by zero. Another reason to stay clear from it. However in this context, if zero division happens, t is supposed to be 0 (because we know a == b). In other words, it’s pretty well defined, it’s just unsure whether it’s 0 or 1, because it’s kind of both at the same time.
In the end, we’re supposed to do three things: 1) find the maximum delta, 2) apply (x - a) / (b - a) to find t, 3) check the interval. Here are the first two (I choose not to do needless if blocks if I can help it, but you do you)
int i = (b.x - a.x).Abs() < (b.y - a.y).Abs()? 1 : 0; // pick the best dimension
var num = p[i] - a[i]; // inverselerp numerator: (x - a)
var denom = b[i] - a[i]; // inverselerp denominator: (b - a)
To check the interval, we’re supposed to first divide num and denom, but let’s do something else instead. If we know 0 <= t <= 1 must return true, then a) any negative result must be false [because that would go below 0), and b) a num quantity larger then denom quantity must be false (quantity here denotes that we don’t care about the sign) [because that would go over 1]. Finally, we avoid having to divide (and having to check against 0 denom).
The (b) part is easy, we can do
if(num.Abs() > denom.Abs()) return false;
but the (a) part with the negative result is “tricky” because we have 4 possible configurations (+/+, +/-, -/- and -/+), 2 of which will give us a negative result while two of the same will cancel out and give a positive. Now writing them all down is horrible practice imho, so let’s just check if the signs are different. We can compare the two so-called SignSteps.
static bool signStep(float v) => (v >= 0f? 1 : -1);
static bool sameSigns(float a, float b) => signStep(a) == signStep(b);
SignStep is similar to the ordinary Sign function, but lacks zero. This is very useful when you need a sign stepping increment (who wants an increment of 0?), but also in this case, where we don’t actually care about zero, we just want to see if num and denom are bearing the same signs.
But then, who needs SignSteps, they’re only useful as a concept. Why not simplify to
a >= 0f == b >= 0f
Now that’s an interesting-looking expression.
We can finish this off
static bool test(Vector2 p, Vector2 a, Vector2 b) {
int i = (b.x - a.x).Abs() < (b.y - a.y).Abs()? 1 : 0;
float n = p[i] - a[i], d = b[i] - a[i];
return n >= 0f == d >= 0f && n.Abs() <= d.Abs();
}
And that’s it.
.
.
.
But what about rays? cue VSauce music
Wouldn’t it be nice if we had all three categories elegantly supported by this one method: lines, rays, and segments? In fact, I didn’t even change the name of the method to properly reflect that it’s now computing segments. Let’s add this, for funzies and, I guess, completeness.
enum Mode {
Lines,
Rays,
RayLine,
RaySegment,
Segments
}
With rays, we want to test only if that inverse lerp leads to a negative result (< 0). This means we should split and selectively exclude the other (> 1) test.
// when bidi(rection) is true, we test in two directions
static bool test(Vector2 p, Vector2 a, Vector2 b, bool bidi = false) {
int i = (b.x - a.x).Abs() < (b.y - a.y).Abs()? 1 : 0;
float n = p[i] - a[i], d = b[i] - a[i];
if(bidi && n.Abs() > d.Abs()) return false;
return n >= 0f == d >= 0f;
}
tl;dr
I’m sorry about the code not being directly copy/pasteable, I will switch this to Unity API asap, I just don’t have time to do it right now.
// compute intersects like a boss you most certainly are™
static bool intersectLines(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersect, Mode mode = Mode.Segments) {
intersect = new Vector2(float.NaN, float.NaN);
if(mode == Mode.Segments) {
var ar = rectFromSeg(a1, a2);
var br = rectFromSeg(b1, b2);
if(!ar.Overlaps(br)) return false;
}
var cc = (hp(a1).Cross(hp(a2))).Cross(hp(b1).Cross(hp(b2)));
if(cc.z.Abs() < 1E-6f) return false;
var x = ((Vector2)cc) * (1f / cc.z);
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;
intersect = x;
return true;
// local functions
static Vector3 hp(Vector2 p) => new Vector3(p.x, p.y, 1f);
static bool test(Vector2 p, Vector2 a, Vector2 b, bool bidi = false) {
int i = (b.x - a.x).Abs() < (b.y - a.y).Abs()? 1 : 0;
float n = p[i] - a[i], d = b[i] - a[i];
if(bidi && n.Abs() > d.Abs()) return false;
return n >= 0f == d >= 0f;
}
}
static Rect rectFromSeg(Vector2 a, Vector2 b) {
var min = Vectx.LeastOf(a, b); // build your own, example is in the post
return new Rect(min, Vectx.MostOf(a, b) - min);
}
enum Mode {
Lines,
Rays,
RayLine,
RaySegment,
Segments
}
Usage example
if(IntersectLines(a1, a2, b1, b2, out var point, IntersectMode.RaySegment)) {
drawGizmo(point);
}
“Can I like the post?”
Only if you insist lol
