Class DelaunayTriangulation

java.lang.Object

org.episteme.core.mathematics.geometry.triangulation.DelaunayTriangulation

public class DelaunayTriangulation
extends Object

Voronoi diagram and Delaunay triangulation computation.

Delaunay triangulation: No point inside circumcircle of any triangle. Voronoi diagram: Dual graph - regions closest to each point.

Since:

1.0

Author:

Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	DelaunayTriangulation.Triangle	Triangle defined by three points.
static class	DelaunayTriangulation.VoronoiCell	Voronoi cell (region closest to a point).

Constructor Summary

Constructors

Constructor	Description
DelaunayTriangulation()

Method Summary

Modifier and Type	Method	Description
static List<DelaunayTriangulation.Triangle>	triangulate(List<Point2D> points)	Computes Delaunay triangulation using Bowyer-Watson algorithm.
static List<DelaunayTriangulation.VoronoiCell>	voronoiDiagram(List<Point2D> points)	Computes Voronoi diagram from Delaunay triangulation.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

DelaunayTriangulation

public DelaunayTriangulation()

Method Details

triangulate

public static List<DelaunayTriangulation.Triangle> triangulate(List<Point2D> points)

Computes Delaunay triangulation using Bowyer-Watson algorithm.

O(n log n) expected time.

Parameters:

points - input points

Returns:

list of triangles forming triangulation

voronoiDiagram

public static List<DelaunayTriangulation.VoronoiCell> voronoiDiagram(List<Point2D> points)

Computes Voronoi diagram from Delaunay triangulation.

Voronoi vertices = circumcenters of Delaunay triangles.