Package rope.mesh
Class R_Delaunay_Triangulation
- All Implemented Interfaces:
Iterable<R_Delaunay_Triangle>
,Collection<R_Delaunay_Triangle>
,Set<R_Delaunay_Triangle>
A 2D Delaunay DelaunayTriangulation (DT) with incremental site insertion.
This is not the fastest way to build a DT, but it's a reasonable way to build
a DT incrementally and it makes a nice interactive display. There are several
O(n log n) methods, but they require that the sites are all known initially.
A DelaunayTriangulation is a Set of Triangles. A DelaunayTriangulation is
unmodifiable as a Set; the only way to change it is to add sites (via
delaunayPlace).
- Author:
- Paul Chew Created July 2005. Derived from an earlier, messier version. Modified November 2007. Rewrote to use AbstractSet as parent class and to use the UndirectedGraph class internally. Tried to make the DT algorithm clearer by explicitly creating a cavity. Added code needed to find a Voronoi cell., Karsten Schmidt Ported to use toxiclibs classes (June 2010)., Stanislas Marçais Ported to use rope classes (August 2022).
-
Constructor Summary
ConstructorsConstructorDescriptionR_Delaunay_Triangulation
(R_Delaunay_Triangle triangle) All sites must fall within the initial triangle. -
Method Summary
Modifier and TypeMethodDescriptionboolean
True iff triangle is a member of this triangulation.int
Place a new site into the DT.iterator()
locate
(R_Delaunay_Vertex point) Locate the triangle with point inside it or on its boundary.neighborOpposite
(R_Delaunay_Vertex site, R_Delaunay_Triangle triangle) Report neighbor opposite the given vertex of triangle.neighbors
(R_Delaunay_Triangle triangle) Return the set of triangles adjacent to triangle.int
size()
surroundingTriangles
(R_Delaunay_Vertex site, R_Delaunay_Triangle triangle) Report triangles surrounding site in order (cw or ccw).toString()
Methods inherited from class java.util.AbstractSet
equals, hashCode, removeAll
Methods inherited from class java.util.AbstractCollection
add, addAll, clear, containsAll, isEmpty, remove, retainAll, toArray, toArray
Methods inherited from interface java.util.Collection
parallelStream, removeIf, stream, toArray
-
Constructor Details
-
R_Delaunay_Triangulation
All sites must fall within the initial triangle.- Parameters:
triangle
- the initial triangle
-
-
Method Details
-
contains
True iff triangle is a member of this triangulation. This method isn't required by AbstractSet, but it improves efficiency.- Specified by:
contains
in interfaceCollection<R_Delaunay_Triangle>
- Specified by:
contains
in interfaceSet<R_Delaunay_Triangle>
- Overrides:
contains
in classAbstractCollection<R_Delaunay_Triangle>
- Parameters:
triangle
- the object to check for membership
-
delaunay_area
Place a new site into the DT. Nothing happens if the site matches an existing DT vertex.- Parameters:
site
- the new R_Delaunay_Vertex- Returns:
- 0 or 1 in most of case or -1 if site does not lie in any triangle
-
iterator
- Specified by:
iterator
in interfaceCollection<R_Delaunay_Triangle>
- Specified by:
iterator
in interfaceIterable<R_Delaunay_Triangle>
- Specified by:
iterator
in interfaceSet<R_Delaunay_Triangle>
- Specified by:
iterator
in classAbstractCollection<R_Delaunay_Triangle>
-
locate
Locate the triangle with point inside it or on its boundary.- Parameters:
point
- the point to locate- Returns:
- the triangle that holds point; null if no such triangle
-
neighborOpposite
Report neighbor opposite the given vertex of triangle.- Parameters:
site
- a vertex of triangletriangle
- we want the neighbor of this triangle- Returns:
- the neighbor opposite site in triangle; null if none
- Throws:
IllegalArgumentException
- if site is not in this triangle
-
neighbors
Return the set of triangles adjacent to triangle.- Parameters:
triangle
- the triangle to check- Returns:
- the neighbors of triangle
-
size
public int size()- Specified by:
size
in interfaceCollection<R_Delaunay_Triangle>
- Specified by:
size
in interfaceSet<R_Delaunay_Triangle>
- Specified by:
size
in classAbstractCollection<R_Delaunay_Triangle>
-
surroundingTriangles
public List<R_Delaunay_Triangle> surroundingTriangles(R_Delaunay_Vertex site, R_Delaunay_Triangle triangle) Report triangles surrounding site in order (cw or ccw).- Parameters:
site
- we want the surrounding triangles for this sitetriangle
- a "starting" triangle that has site as a vertex- Returns:
- all triangles surrounding site in order (cw or ccw)
- Throws:
IllegalArgumentException
- if site is not in triangle
-
toString
- Overrides:
toString
in classAbstractCollection<R_Delaunay_Triangle>
-