Skip to content

Instantly share code, notes, and snippets.

@der-hugo
Created March 10, 2021 11:04
Show Gist options
  • Save der-hugo/ba9f3c9f6da8c886e6b813ed6be86a10 to your computer and use it in GitHub Desktop.
Save der-hugo/ba9f3c9f6da8c886e6b813ed6be86a10 to your computer and use it in GitHub Desktop.
Are two 2D triangles intersecting in Unity? Refactored version of https://www.habrador.com/tutorials/math/6-triangle-triangle-intersection
using System;
using UnityEngine;
/// <summary>
/// To store triangle data to get cleaner code
/// </summary>
[Serializable]
public struct Triangle2D
{
/// <summary>
/// To create a line segment
/// </summary>
private struct LineSegment2D
{
//Start/end coordinates
private readonly Vector2 _p1;
private readonly Vector2 _p2;
public LineSegment2D(Vector2 p1, Vector2 p2)
{
_p1 = p1;
_p2 = p2;
}
/// <summary>
/// Check if 2 line segments are intersecting in 2d space
/// <para>http://thirdpartyninjas.com/blog/2008/10/07/line-segment-intersection/</para>
/// </summary>
public bool IsIntersecting(LineSegment2D other)
{
var p3 = other._p1;
var p4 = other._p2;
var denominator = (p4.y - p3.y) * (_p2.x - _p1.x) - (p4.x - p3.x) * (_p2.y - _p1.y);
//Make sure the denominator is != 0, if 0 the lines are parallel
if (denominator == 0) return false;
var u_a = ((p4.x - p3.x) * (_p1.y - p3.y) - (p4.y - p3.y) * (_p1.x - p3.x)) / denominator;
var u_b = ((_p2.x - _p1.x) * (_p1.y - p3.y) - (_p2.y - _p1.y) * (_p1.x - p3.x)) / denominator;
//Is intersecting if u_a and u_b are between 0 and 1
return 0 <= u_a && u_a <= 1 && 0 <= u_b && u_b <= 1;
}
}
//Corners of the triangle
// Can be edited via the Inspector
[SerializeField] private Vector2 _a;
[SerializeField] private Vector2 _b;
[SerializeField] private Vector2 _c;
//The 3 line segments that make up this triangle
private LineSegment2D[] _lineSegments;
public Triangle2D(Vector2 a, Vector2 b, Vector2 c)
{
_a = a;
_b = b;
_c = c;
_lineSegments = new[]
{
new LineSegment2D(a, b),
new LineSegment2D(b, c),
new LineSegment2D(c, a)
};
}
/// <summary>
/// Is this triangle intersecting the other one?
/// </summary>
public bool IsIntersecting(Triangle2D other)
{
//Step 1. AABB intersection
if (IsIntersectingAABB(other))
{
//Step 2. Line segment - triangle intersection
if (AreAnyLineSegmentsIntersecting(other))
{
return true;
}
//Step 3. Point in triangle intersection - if one of the triangles is inside the other
if (AreCornersIntersecting(other))
{
return true;
}
}
return false;
}
/// <summary>
/// Is a point p inside this triangle
///<para>From http://totologic.blogspot.se/2014/01/accurate-point-in-triangle-test.html</para>
/// </summary>
public bool IsPointInTriangle(Vector3 p)
{
var denominator = (_b.y - _c.y) * (_a.x - _c.x) + (_c.x - _b.x) * (_a.y - _c.y);
var a = ((_b.y - _c.y) * (p.x - _c.x) + (_c.x - _b.x) * (p.y - _c.y)) / denominator;
var b = ((_c.y - _a.y) * (p.x - _c.x) + (_a.x - _c.x) * (p.y - _c.y)) / denominator;
var c = 1 - a - b;
return 0f <= a && a <= 1f && 0f <= b && b <= 1f && 0f <= c && c <= 1f;
}
/// <summary>
/// Approximate the triangles with rectangles and see if they intersect with the AABB intersection algorithm
/// </summary>
private bool IsIntersectingAABB(Triangle2D other)
{
//Find the size of the bounding boxes
// Bounding box Triangle 1
var t1_minX = Mathf.Min(_a.x, _b.x, _c.x);
var t1_maxX = Mathf.Max(_a.x, _b.x, _c.x);
var t1_minY = Mathf.Min(_a.y, _b.y, _c.y);
var t1_maxY = Mathf.Max(_a.y, _b.y, _c.y);
// Bounding box Triangle 2
var t2_minX = Mathf.Min(other._a.x, other._b.x, other._c.x);
var t2_maxX = Mathf.Max(other._a.x, other._b.x, other._c.x);
var t2_minY = Mathf.Min(other._a.y, other._b.y, other._c.y);
var t2_maxY = Mathf.Max(other._a.y, other._b.y, other._c.y);
//Are the rectangles intersecting?
//If the min of one box in one dimension is greater than the max of another box then the boxes are not intersecting
//They have to intersect in 2 dimensions. We have to test if box 1 is to the left or box 2 and vice versa
return t1_minX <= t2_maxX && t2_minX <= t1_maxX && t1_minY <= t2_maxY && t2_minY <= t1_maxY;
}
/// <summary>
/// Check if any of the edges that make up one of the triangles is intersecting with any of the edges of the other triangle
/// </summary>
private bool AreAnyLineSegmentsIntersecting(Triangle2D triangle2)
{
//Loop through all edges
foreach (var line1 in _lineSegments)
{
foreach (var line2 in triangle2._lineSegments)
{
//Are they intersecting?
if (line1.IsIntersecting(line2))
{
return true;
}
}
}
return false;
}
/// <summary>
/// There's a possibility that one of the triangles is smaller than the other
/// <para>So we have to check if any of the triangle's corners is inside the other triangle</para>
/// </summary>
private bool AreCornersIntersecting(Triangle2D other)
{
//We only have to test one corner from each triangle (otherwise the line segments would already intersect anyway)
//Triangle 1 in triangle 2 or //Triangle 2 in triangle 1
return other.IsPointInTriangle(_a) || IsPointInTriangle(other._a);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment