Created
March 10, 2021 11:04
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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