A* Pathfinding Project
4.1.19
The A* Pathfinding Project for Unity 3D

Utility functions for working with polygons, lines, and other vector math. More...
Utility functions for working with polygons, lines, and other vector math.
All functions which accepts Vector3s but work in 2D space uses the XZ space if nothing else is said.
Static Public Member Functions  
static Vector3  ClosestPointOnTriangle (Vector3[] triangle, Vector3 point) 
Returns the closest point on the triangle. More...  
static Vector2  ClosestPointOnTriangle (Vector2 a, Vector2 b, Vector2 c, Vector2 p) 
Closest point on the triangle abc to the point p. More...  
static Vector3  ClosestPointOnTriangle (Vector3 a, Vector3 b, Vector3 c, Vector3 p) 
Closest point on the triangle abc to the point p. More...  
static Vector3  ClosestPointOnTriangleXZ (Vector3 a, Vector3 b, Vector3 c, Vector3 p) 
Closest point on the triangle abc to the point p when seen from above. More...  
static void  CompressMesh (List< Int3 > vertices, List< int > triangles, out Int3[] outVertices, out int[] outTriangles) 
Compress the mesh by removing duplicate vertices. More...  
static bool  ContainsPoint (Vector3 a, Vector3 b, Vector3 c, Vector3 p) 
Returns if the triangle ABC contains the point p in XZ space. More...  
static bool  ContainsPoint (Int3 a, Int3 b, Int3 c, Int3 p) 
Returns if the triangle ABC contains the point p. More...  
static bool  ContainsPoint (Int2 a, Int2 b, Int2 c, Int2 p) 
Returns if the triangle ABC contains the point p. More...  
static bool  ContainsPoint (Vector3[] polyPoints, Vector3 p) 
Checks if p is inside the polygon (XZ space) More...  
static bool  ContainsPoint (Vector2[] polyPoints, Vector2 p) 
Checks if p is inside the polygon. More...  
static bool  ContainsPointXZ (Vector3 a, Vector3 b, Vector3 c, Vector3 p) 
Returns if the triangle ABC contains the point p in XZ space. More...  
static bool  ContainsPointXZ (Int3 a, Int3 b, Int3 c, Int3 p) 
Returns if the triangle ABC contains the point p. More...  
static bool  ContainsPointXZ (Vector3[] polyPoints, Vector3 p) 
Checks if p is inside the polygon (XZ space). More...  
static Vector3 []  ConvexHull (Vector3[] points) 
Calculates convex hull in XZ space for the points. More...  
static Vector3 []  ConvexHullXZ (Vector3[] points) 
Calculates convex hull in XZ space for the points. More...  
static float  DistanceSegmentSegment3D (Vector3 s1, Vector3 e1, Vector3 s2, Vector3 e2) 
Get the 3D minimum distance between 2 segments Input: two 3D line segments S1 and S2. More...  
static bool  IntersectionFactor (Int3 start1, Int3 end1, Int3 start2, Int3 end2, out float factor1, out float factor2) 
Returns the intersection factors for line 1 and line 2. More...  
static bool  IntersectionFactor (Vector3 start1, Vector3 end1, Vector3 start2, Vector3 end2, out float factor1, out float factor2) 
Returns the intersection factors for line 1 and line 2. More...  
static float  IntersectionFactor (Vector3 start1, Vector3 end1, Vector3 start2, Vector3 end2) 
Returns the intersection factor for line 1 with line 2. More...  
static float  IntersectionFactorRay (Int3 start1, Int3 end1, Int3 start2, Int3 end2) 
Returns the intersection factor for line 1 with ray 2. More...  
static bool  IntersectionFactorRaySegment (Int3 start1, Int3 end1, Int3 start2, Int3 end2) 
Returns if the ray (start1, end1) intersects the segment (start2, end2). More...  
static Vector3  IntersectionPoint (Vector3 start1, Vector3 end1, Vector3 start2, Vector3 end2) 
Returns the intersection point between the two lines. More...  
static Vector3  IntersectionPoint (Vector3 start1, Vector3 end1, Vector3 start2, Vector3 end2, out bool intersects) 
Returns the intersection point between the two lines. More...  
static Vector2  IntersectionPoint (Vector2 start1, Vector2 end1, Vector2 start2, Vector2 end2) 
Returns the intersection point between the two lines. More...  
static Vector2  IntersectionPoint (Vector2 start1, Vector2 end1, Vector2 start2, Vector2 end2, out bool intersects) 
Returns the intersection point between the two lines. More...  
static Vector3  IntersectionPointOptimized (Vector3 start1, Vector3 dir1, Vector3 start2, Vector3 dir2) 
Intersection point between two infinite lines. More...  
static Vector3  IntersectionPointOptimized (Vector3 start1, Vector3 dir1, Vector3 start2, Vector3 dir2, out bool intersects) 
Intersection point between two infinite lines. More...  
static bool  Intersects (Int2 start1, Int2 end1, Int2 start2, Int2 end2) 
Returns if the line segment a2  b2 intersects the line segment a  b. More...  
static bool  Intersects (Int3 start1, Int3 end1, Int3 start2, Int3 end2) 
Returns if the line segment a2  b2 intersects the line segment a  b. More...  
static bool  Intersects (Vector3 start1, Vector3 end1, Vector3 start2, Vector3 end2) 
Returns if the two line segments intersects. More...  
static bool  IntersectsUnclamped (Vector3 a, Vector3 b, Vector3 a2, Vector3 b2) 
Returns if the line segment a2  b2 intersects the infinite line a  b. More...  
static bool  IsClockwise (Vector3 a, Vector3 b, Vector3 c) 
Returns if the points a in a clockwise order. More...  
static bool  IsClockwise (Int3 a, Int3 b, Int3 c) 
Returns if the points a in a clockwise order. More...  
static bool  IsClockwiseMargin (Vector3 a, Vector3 b, Vector3 c) 
Returns if the points a in a clockwise order. More...  
static bool  IsClockwiseMargin (Int3 a, Int3 b, Int3 c) 
Returns true if the points a in a clockwise order or if they are colinear. More...  
static bool  IsClockwiseMargin (Int2 a, Int2 b, Int2 c) 
Returns true if the points a in a clockwise order or if they are colinear. More...  
static bool  IsColinear (Int3 a, Int3 b, Int3 c) 
Returns if the points are colinear (lie on a straight line) More...  
static bool  IsColinear (Vector3 a, Vector3 b, Vector3 c) 
Returns if the points are colinear (lie on a straight line) More...  
static bool  IsColinearAlmost (Int3 a, Int3 b, Int3 c) 
Returns if the points are colinear (lie on a straight line) More...  
static bool  Left (Vector3 a, Vector3 b, Vector3 p) 
Returns if p lies on the left side of the line a  b. More...  
static bool  Left (Vector2 a, Vector2 b, Vector2 p) 
Returns if p lies on the left side of the line a  b. More...  
static bool  Left (Int3 a, Int3 b, Int3 p) 
Returns if p lies on the left side of the line a  b. More...  
static bool  Left (Int2 a, Int2 b, Int2 p) 
Returns if p lies on the left side of the line a  b. More...  
static bool  LeftNotColinear (Vector3 a, Vector3 b, Vector3 p) 
Returns if p lies on the left side of the line a  b. More...  
static bool  LeftNotColinear (Int3 a, Int3 b, Int3 p) 
Returns if p lies on the left side of the line a  b. More...  
static bool  LineIntersectsBounds (Bounds bounds, Vector3 a, Vector3 b) 
Does the line segment intersect the bounding box. More...  
static int  SampleYCoordinateInTriangle (Int3 p1, Int3 p2, Int3 p3, Int3 p) 
Sample Y coordinate of the triangle (p1, p2, p3) at the point p in XZ space. More...  
static Vector3  SegmentIntersectionPoint (Vector3 start1, Vector3 end1, Vector3 start2, Vector3 end2, out bool intersects) 
Returns the intersection point between the two line segments in XZ space. More...  
static void  Subdivide (List< Vector3 > points, List< Vector3 > result, int subSegments) 
Divides each segment in the list into subSegments segments and fills the result list with the new points. More...  
static void  TraceContours (Dictionary< int, int > outline, HashSet< int > hasInEdge, System.Action< List< int >, bool > results) 
Given a set of edges between vertices, follows those edges and returns them as chains and cycles. More...  
static long  TriangleArea (Int3 a, Int3 b, Int3 c) 
Signed area of a triangle in the XZ plane multiplied by 2. More...  
static float  TriangleArea (Vector3 a, Vector3 b, Vector3 c) 
Signed area of a triangle in the XZ plane multiplied by 2. More...  
static long  TriangleArea2 (Int3 a, Int3 b, Int3 c) 
Signed area of a triangle in the XZ plane multiplied by 2. More...  
static float  TriangleArea2 (Vector3 a, Vector3 b, Vector3 c) 
Signed area of a triangle in the XZ plane multiplied by 2. More...  
Static Private Attributes  
static readonly Dictionary< Int3, int >  cached_Int3_int_dict = new Dictionary<Int3, int>() 
Cached dictionary to avoid excessive allocations. More...  

static 
Returns the closest point on the triangle.
The triangle array must have a length of at least 3.

static 
Closest point on the triangle abc to the point p.

static 
Closest point on the triangle abc to the point p.

static 
Closest point on the triangle abc to the point p when seen from above.

static 
Compress the mesh by removing duplicate vertices.
vertices  Vertices of the input mesh 
triangles  Triangles of the input mesh 
outVertices  Vertices of the output mesh. 
outTriangles  Triangles of the output mesh. 
Vertices that differ by only 1 along the y coordinate will also be merged together.

static 
Returns if the triangle ABC contains the point p in XZ space.
Returns if the triangle ABC contains the point p.
Returns if the triangle ABC contains the point p.
The triangle vertices are assumed to be laid out in clockwise order.

static 
Checks if p is inside the polygon (XZ space)

static 
Checks if p is inside the polygon.

static 
Returns if the triangle ABC contains the point p in XZ space.
The triangle vertices are assumed to be laid out in clockwise order.
Returns if the triangle ABC contains the point p.
The triangle vertices are assumed to be laid out in clockwise order.

static 
Checks if p is inside the polygon (XZ space).

static 
Calculates convex hull in XZ space for the points.
Implemented using the very simple Gift Wrapping Algorithm which has a complexity of O(nh) where n is the number of points and h is the number of points on the hull, so it is in the worst case quadratic.

static 
Calculates convex hull in XZ space for the points.
Implemented using the very simple Gift Wrapping Algorithm which has a complexity of O(nh) where n is the number of points and h is the number of points on the hull, so it is in the worst case quadratic.

static 
Get the 3D minimum distance between 2 segments Input: two 3D line segments S1 and S2.

static 
Returns the intersection factors for line 1 and line 2.
The intersection factors is a distance along the line start  end where the other line intersects it.
Lines are treated as infinite.
false is returned if the lines are parallel and true if they are not. Only the XZ coordinates are used.

static 
Returns the intersection factors for line 1 and line 2.
The intersection factors is a distance along the line start  end where the other line intersects it.
Lines are treated as infinite.
false is returned if the lines are parallel and true if they are not. Only the XZ coordinates are used.

static 
Returns the intersection factor for line 1 with line 2.
The intersection factor is a distance along the line start1  end1 where the line start2  end2 intersects it.
. Lines are treated as infinite.
1 is returned if the lines are parallel (note that this is a valid return value if they are not parallel too) *
Returns the intersection factor for line 1 with ray 2.
The intersection factors is a factor distance along the line start  end where the other line intersects it.
Lines are treated as infinite.
The second "line" is treated as a ray, meaning only matches on start2 or forwards towards end2 (and beyond) will be returned If the point lies on the wrong side of the ray start, Nan will be returned.
NaN is returned if the lines are parallel. *
Returns if the ray (start1, end1) intersects the segment (start2, end2).
false is returned if the lines are parallel. Only the XZ coordinates are used.

static 
Returns the intersection point between the two lines.
Lines are treated as infinite. start1 is returned if the lines are parallel

static 
Returns the intersection point between the two lines.
Lines are treated as infinite. start1 is returned if the lines are parallel

static 
Returns the intersection point between the two lines.
Lines are treated as infinite. start1 is returned if the lines are parallel

static 
Returns the intersection point between the two lines.
Lines are treated as infinite. start1 is returned if the lines are parallel

static 
Intersection point between two infinite lines.
Lines are treated as infinite. If the lines are parallel 'start1' will be returned. Intersections are calculated on the XZ plane.

static 
Intersection point between two infinite lines.
Lines are treated as infinite. If the lines are parallel 'start1' will be returned. Intersections are calculated on the XZ plane.
Returns if the line segment a2  b2 intersects the line segment a  b.
If only the endpoints coincide, the result is undefined (may be true or false).
Returns if the line segment a2  b2 intersects the line segment a  b.
If only the endpoints coincide, the result is undefined (may be true or false).

static 
Returns if the two line segments intersects.
The lines are NOT treated as infinite (just for clarification)

static 
Returns if the line segment a2  b2 intersects the infinite line a  b.
ab is infinite, a2b2 is not infinite

static 
Returns if the points a in a clockwise order.
Returns if the points a in a clockwise order.

static 
Returns if the points a in a clockwise order.
Will return true even if the points are colinear or very slightly counterclockwise (if the signed area of the triangle formed by the points has an area less than or equals to float.Epsilon)
Returns true if the points a in a clockwise order or if they are colinear.
Returns true if the points a in a clockwise order or if they are colinear.
Returns if the points are colinear (lie on a straight line)

static 
Returns if the points are colinear (lie on a straight line)
Returns if the points are colinear (lie on a straight line)

static 
Returns if p lies on the left side of the line a  b.
Uses XZ space. Also returns true if the points are colinear

static 
Returns if p lies on the left side of the line a  b.
Also returns true if the points are colinear
Returns if p lies on the left side of the line a  b.
Uses XZ space. Also returns true if the points are colinear
Returns if p lies on the left side of the line a  b.
Also returns true if the points are colinear

static 
Returns if p lies on the left side of the line a  b.
Uses XZ space. Does not return true if the points are colinear.
Returns if p lies on the left side of the line a  b.
Uses XZ space.

static 
Does the line segment intersect the bounding box.
The line is NOT treated as infinite.
Sample Y coordinate of the triangle (p1, p2, p3) at the point p in XZ space.
The y coordinate of p is ignored.

static 
Returns the intersection point between the two line segments in XZ space.
Lines are NOT treated as infinite. start1 is returned if the line segments do not intersect The point will be returned along the line [start1, end1] (this matters only for the y coordinate).

static 
Divides each segment in the list into subSegments segments and fills the result list with the new points.

static 
Given a set of edges between vertices, follows those edges and returns them as chains and cycles.
outline  outline[a] = b if there is an edge from a to b. 
hasInEdge  hasInEdge should contain b if outline[a] = b for any key a. 
results  Will be called once for each contour with the contour as a parameter as well as a boolean indicating if the contour is a cycle or a chain (see image). 
Signed area of a triangle in the XZ plane multiplied by 2.
This will be negative for clockwise triangles and positive for counterclockwise ones. This method can handle larger numbers than TriangleArea2(Int3)

static 
Signed area of a triangle in the XZ plane multiplied by 2.
This will be negative for clockwise triangles and positive for counterclockwise ones. Idential to TriangleArea2(Vector3), kept for compability.
Signed area of a triangle in the XZ plane multiplied by 2.
This will be negative for clockwise triangles and positive for counterclockwise ones

static 
Signed area of a triangle in the XZ plane multiplied by 2.
This will be negative for clockwise triangles and positive for counterclockwise ones.
Cached dictionary to avoid excessive allocations.