orx-triangulation/org.openrndr.extra.triangulation/ConstrainedDelaunayTriangulation

ConstrainedDelaunayTriangulation

class ConstrainedDelaunayTriangulation(val shape: Shape, interiorPoints: List<Vector2> = emptyList()) : AbstractDelaunayTriangulation(source)

Computes a constrained Delaunay triangulation (CDT) of a Shape.

Every edge of every (closed) contour of shape is guaranteed to appear as an edge in the resulting triangulation, and triangles that fall outside the shape -- including triangles inside holes -- are discarded. Contours are combined using Shape's own containment rule (org.openrndr.shape.contains), so holes, islands inside holes, and compound shapes are all handled.

Internally this is built on Tripack, a direct port of the core algorithms of Robert Renka's TRIPACK (every contour edge is forced into an unconstrained Delaunay triangulation via repeated diagonal swapping), followed by discarding triangles whose centroid falls outside shape.

Parameters

shape

a Shape whose contours are closed and consist solely of linear segments (see Shape.linear).

interiorPoints

additional, unconstrained points to include in the triangulation, for example to refine/densify the mesh. Every point must lie inside shape.

Constructors

ConstrainedDelaunayTriangulation

constructor(shape: Shape, interiorPoints: List<Vector2> = emptyList())

Properties

points

open override val points: List<Vector2>

The combined vertex positions used for triangulation: interiorPoints followed by the vertices of all contours of shape, in that order.

shape

val shape: Shape

Functions

nearest

open fun nearest(query: Vector2): Int

Index into points of the point nearest to query.

nearestPoint

open fun nearestPoint(query: Vector2): Vector2

The point nearest to query.

neighborPoints

open fun neighborPoints(pointIndex: Int): List<Vector2>

The positions of the nodes adjacent to pointIndex in the triangulation.

neighbors

open override fun neighbors(pointIndex: Int): Sequence<Int>

Indices into points of the nodes adjacent to pointIndex in the triangulation.

triangleIndices

open override fun triangleIndices(): List<IntArray>

The resulting triangles as index triples into points, in counter-clockwise order.

triangles

open override fun triangles(filterPredicate: (Int, Int, Int) -> Boolean = { _, _, _ -> true }): List<Triangle>

The resulting triangles, optionally restricted by filterPredicate.

voronoiDiagram

open override fun voronoiDiagram(bounds: Rectangle = points.bounds): ConstrainedVoronoiDiagram

The Voronoi diagram dual to this triangulation, with cells clipped to bounds.