Delaunay triangulations

detroit.Delaunay(points: list[float])

Delaunay triangulation for the given flat array \([x_0, y_0, x_1, y_1, \ldots]\) of points.

Parameters:

points (list[float]) – The coordinates of the points as an array \([x_0, y_0, x_1, y_1, \ldots]\).

detroit.inedges

The incoming halfedge indexes \([e_0, e_1, e_2, \ldots]\). For each point i, inedges[i] is the halfedge index e of an incoming halfedge. For coincident points, the halfedge index is -1; for points on the convex hull, the incoming halfedge is on the convex hull; for other points, the choice of incoming halfedge is arbitrary. The inedges table can be used to traverse the Delaunay triangulation.

Type:

list[int]

detroit.points

The coordinates of the points as an array \([x_0, y_0, x_1, y_1, \ldots]\).

Type:

list[float]

detroit.halfedges

The halfedge indexes as an Int32Array \([j_0, j_1, \ldots]\). For each index \(0 \le i \lt \text{halfedges.length}\), there is a halfedge from triangle vertex j = halfedges[i] to triangle vertex i. Equivalently, this means that triangle \(\lfloor i / 3 \rfloor\) is adjacent to triangle \(\lfloor j / 3 \rfloor\). If j is negative, then triangle \(\lfloor i / 3 \rfloor\) is an exterior triangle on the convex hull.

Type:

list[int]

detroit.hull

A list of point indexes that form the convex hull in counterclockwise order. If the points are collinear, returns them ordered.

Type:

list[int]

detroit.triangles

The triangle vertex indexes \([i_0, j_0, k_0, i_1, j_1, k_1, \ldots]\). Each contiguous triplet of indexes i, j, k forms a counterclockwise triangle. The coordinates of the triangle’s points can be found by going through delaunay.points.

Type:

list[int]

class detroit.delaunay.delaunay.Delaunay(points: list[float])

Delaunay triangulation for the given flat array \([x_0, y_0, x_1, y_1, \ldots]\) of points.

Parameters:

points (list[float]) – The coordinates of the points as an array \([x_0, y_0, x_1, y_1, \ldots]\).

inedges

The incoming halfedge indexes \([e_0, e_1, e_2, \ldots]\). For each point i, inedges[i] is the halfedge index e of an incoming halfedge. For coincident points, the halfedge index is -1; for points on the convex hull, the incoming halfedge is on the convex hull; for other points, the choice of incoming halfedge is arbitrary. The inedges table can be used to traverse the Delaunay triangulation.

Type:

list[int]

points

The coordinates of the points as an array \([x_0, y_0, x_1, y_1, \ldots]\).

Type:

list[float]

halfedges

The halfedge indexes as an Int32Array \([j_0, j_1, \ldots]\). For each index \(0 \le i \lt \text{halfedges.length}\), there is a halfedge from triangle vertex j = halfedges[i] to triangle vertex i. Equivalently, this means that triangle \(\lfloor i / 3 \rfloor\) is adjacent to triangle \(\lfloor j / 3 \rfloor\). If j is negative, then triangle \(\lfloor i / 3 \rfloor\) is an exterior triangle on the convex hull.

Type:

list[int]

hull

A list of point indexes that form the convex hull in counterclockwise order. If the points are collinear, returns them ordered.

Type:

list[int]

triangles

The triangle vertex indexes \([i_0, j_0, k_0, i_1, j_1, k_1, \ldots]\). Each contiguous triplet of indexes i, j, k forms a counterclockwise triangle. The coordinates of the triangle’s points can be found by going through delaunay.points.

Type:

list[int]

find(x: float, y: float, i: int = 0) → int

Returns the index of the input point that is closest to the specified point \((x, y)\). The search is started at the specified point i. If i is not specified, it defaults to zero.

Parameters:

  • x (float) – X-coordinate point

  • y (float) – Y-coordinate point

  • i (int) – Starting point index

Returns:

Index of the input point

Return type:

int

classmethod from_points(points: list[~detroit.types.T], fx: ~collections.abc.Callable[[~detroit.types.T, int, list[~detroit.types.T]], float] = <function point_x>, fy: ~collections.abc.Callable[[~detroit.types.T, int, list[~detroit.types.T]], float] = <function point_y>) → Delaunay

Returns the Delaunay triangulation for the given array or iterable of points. If fx and fy are not specified, then points is assumed to be an array of two-element arrays of numbers: \([[x_0, y_0], [x_1, y_1], \ldots]\).

Parameters:

  • points (list[T]) – List of points

  • fx (Callable[[T, int, list[T]], float]) – X-coordinate accessor

  • fy (Callable[[T, int, list[T]], float]) – Y-coordinate accessor

Returns:

Delaunay object

Return type:

Delaunay

hull_polygon() → list[tuple[float, float]] | None

Returns the closed polygon \([[x_0, y_0], [x_1, y_1], \ldots, [x_0, y_0]]\) representing the convex hull.

Returns:

Closed polygon

Return type:

list[tuple[float, float]] | None

neighbors(i: int) → Iterator[int]

Returns an iterable over the indexes of the neighboring points to the specified point i. The iterable is empty if i is a coincident point.

Parameters:

i (int) – Point index

Returns:

Indexes of the neighboring points

Return type:

Iterator[int]

render(context: Context | None = None) → str | None

Renders the edges of the Delaunay triangulation to the specified context. If a context is not specified, an SVG path string is returned instead.

Parameters:

context (Context | None) – Context object

Returns:

SVG path string

Return type:

str | None

render_hull(context: Context | None = None) → str | None

Renders the convex hull of the Delaunay triangulation to the specified context. If a context is not specified, an SVG path string is returned instead.

Parameters:

context (Context | None) – Context object

Returns:

SVG path string

Return type:

str | None

render_points(context: Context | None = None, r: float | None = None) → str | None

Renders the input points of the Delaunay triangulation to the specified context as circles with the specified radius. If radius is not specified, it defaults to 2. If a context is not specified, an SVG path string is returned instead.

Parameters:

  • context (Context | None) – Context object

  • r (float | None) – Radius value

Returns:

SVG path string

Return type:

str | None

render_triangle(i: int, context: Context | None = None) → str | None

Renders triangle i of the Delaunay triangulation to the specified context. If a context is not specified, an SVG path string is returned instead.

Parameters:

  • i (int) – Triangle index

  • context (Context | None) – Context object

Returns:

SVG path string

Return type:

str | None

triangle_polygon(i: int) → list[tuple[float, float]] | None

Returns the closed polygon \([[x_0, y_0], [x_1, y_1], [x_2, y_2], [x_0, y_0]]\) representing the triangle i.

Parameters:

i (int) – Triangle index

Returns:

Closed polygon

Return type:

list[tuple[float, float]] | None

triangle_polygons() → Iterator[list[tuple[float, float]] | None]

Returns an iterable over the polygons for each triangle, in order.

Returns:

Iterator over the polygons for each triangle

Return type:

Iterator[list[tuple[float, float]] | None]

update() → Delaunay

Recomputes the triangulation after the points have been modified in-place.

Returns:

Itself

Return type:

Delaunay

voronoi(bounds: tuple[float, float, float, float] | None = None) → Voronoi

Returns the Voronoi diagram for the given Delaunay triangulation. When rendering, the diagram will be clipped to the specified bounds = [xmin, ymin, xmax, ymax].

Parameters:

bounds (tuple[float, float, float, float] | None) – [xmin, ymin, xmax, ymax] values

Returns:

Voronoi object

Return type:

Voronoi