Class TriangleLocator

Locate triangles in a mesh.

Inheritance

System.Object

TriangleLocator

Inherited Members

System.Object.ToString()

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

Namespace: UnityEngine.Experimental.U2D.TriangleNet

Syntax

public class TriangleLocator

Remarks

WARNING: This routine is designed for convex triangulations, and will not generally work after the holes and concavities have been carved.

Based on a paper by Ernst P. Mucke, Isaac Saias, and Binhai Zhu, "Fast Randomized Point Location Without Preprocessing in Two- and Three-Dimensional Delaunay Triangulations," Proceedings of the Twelfth Annual Symposium on Computational Geometry, ACM, May 1996.

Constructors

TriangleLocator(Mesh)

Declaration

public TriangleLocator(Mesh mesh)

Parameters

Type	Name	Description
Mesh	mesh

TriangleLocator(Mesh, IPredicates)

Declaration

public TriangleLocator(Mesh mesh, IPredicates predicates)

Parameters

Type	Name	Description
Mesh	mesh
IPredicates	predicates

Methods

Locate(Point, ref Otri)

Find a triangle or edge containing a given point.

Declaration

public LocateResult Locate(Point searchpoint, ref Otri searchtri)

Parameters

Type	Name	Description
Point	searchpoint	The point to locate.
Otri	searchtri	The triangle to start the search at.

Returns

Type	Description
LocateResult	Location information.

Remarks

Searching begins from one of: the input 'searchtri', a recently encountered triangle 'recenttri', or from a triangle chosen from a random sample. The choice is made by determining which triangle's origin is closest to the point we are searching for. Normally, 'searchtri' should be a handle on the convex hull of the triangulation.

Details on the random sampling method can be found in the Mucke, Saias, and Zhu paper cited in the header of this code.

On completion, 'searchtri' is a triangle that contains 'searchpoint'.

Returns ONVERTEX if the point lies on an existing vertex. 'searchtri' is a handle whose origin is the existing vertex.

Returns ONEDGE if the point lies on a mesh edge. 'searchtri' is a handle whose primary edge is the edge on which the point lies.

Returns INTRIANGLE if the point lies strictly within a triangle. 'searchtri' is a handle on the triangle that contains the point.

Returns OUTSIDE if the point lies outside the mesh. 'searchtri' is a handle whose primary edge the point is to the right of. This might occur when the circumcenter of a triangle falls just slightly outside the mesh due to floating-point roundoff error. It also occurs when seeking a hole or region point that a foolish user has placed outside the mesh.

WARNING: This routine is designed for convex triangulations, and will not generally work after the holes and concavities have been carved.

PreciseLocate(Point, ref Otri, Boolean)

Find a triangle or edge containing a given point.

Declaration

public LocateResult PreciseLocate(Point searchpoint, ref Otri searchtri, bool stopatsubsegment)

Parameters

Type	Name	Description
Point	searchpoint	The point to locate.
Otri	searchtri	The triangle to start the search at.
System.Boolean	stopatsubsegment	If 'stopatsubsegment' is set, the search will stop if it tries to walk through a subsegment, and will return OUTSIDE.

Returns

Type	Description
LocateResult	Location information.

Remarks

Begins its search from 'searchtri'. It is important that 'searchtri' be a handle with the property that 'searchpoint' is strictly to the left of the edge denoted by 'searchtri', or is collinear with that edge and does not intersect that edge. (In particular, 'searchpoint' should not be the origin or destination of that edge.)

These conditions are imposed because preciselocate() is normally used in one of two situations:

(1) To try to find the location to insert a new point. Normally, we know an edge that the point is strictly to the left of. In the incremental Delaunay algorithm, that edge is a bounding box edge. In Ruppert's Delaunay refinement algorithm for quality meshing, that edge is the shortest edge of the triangle whose circumcenter is being inserted.

(2) To try to find an existing point. In this case, any edge on the convex hull is a good starting edge. You must screen out the possibility that the vertex sought is an endpoint of the starting edge before you call preciselocate().

On completion, 'searchtri' is a triangle that contains 'searchpoint'.

This implementation differs from that given by Guibas and Stolfi. It walks from triangle to triangle, crossing an edge only if 'searchpoint' is on the other side of the line containing that edge. After entering a triangle, there are two edges by which one can leave that triangle. If both edges are valid ('searchpoint' is on the other side of both edges), one of the two is chosen by drawing a line perpendicular to the entry edge (whose endpoints are 'forg' and 'fdest') passing through 'fapex'. Depending on which side of this perpendicular 'searchpoint' falls on, an exit edge is chosen.

This implementation is empirically faster than the Guibas and Stolfi point location routine (which I originally used), which tends to spiral in toward its target.

Returns ONVERTEX if the point lies on an existing vertex. 'searchtri' is a handle whose origin is the existing vertex.

Returns ONEDGE if the point lies on a mesh edge. 'searchtri' is a handle whose primary edge is the edge on which the point lies.

Returns INTRIANGLE if the point lies strictly within a triangle. 'searchtri' is a handle on the triangle that contains the point.

Returns OUTSIDE if the point lies outside the mesh. 'searchtri' is a handle whose primary edge the point is to the right of. This might occur when the circumcenter of a triangle falls just slightly outside the mesh due to floating-point roundoff error. It also occurs when seeking a hole or region point that a foolish user has placed outside the mesh.

WARNING: This routine is designed for convex triangulations, and will not generally work after the holes and concavities have been carved. However, it can still be used to find the circumcenter of a triangle, as long as the search is begun from the triangle in question.

Reset()

Declaration

public void Reset()

Update(ref Otri)

Suggest the given triangle as a starting triangle for point location.

Declaration

public void Update(ref Otri otri)

Parameters

Type	Name	Description
Otri	otri