geom2d.voronoi¶
Voronoi diagram / Delaunay triangulation.
Compute a Voronoi diagram and optional Delaunay triangulation for a set of 2D input points.
- Based on Steve Fortune’s original code:
- Derek Bradley’s fixes for memory leaks:
- Shane O’Sullivan’s translation to C++:
- Translated to Python by Bill Simons September, 2005:
(not sure where this original translation can be found anymore)
- Nicely refactored version by Manfred Moitzi at:
This version was based on the Bill Simons version, refactored with some of Moitzi’s cleanups, and comments incorporated from Shane O’Sullivan’s update.
Derived from code bearing the following notice:
The author of this software is Steven Fortune. Copyright (c) 1994 by AT&T
Bell Laboratories.
Permission to use, copy, modify, and distribute this software for any
purpose without fee is hereby granted, provided that this entire notice
is included in all copies of any software which is or includes a copy
or modification of this software and in all copies of the supporting
documentation for such software.
THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
This module has no dependencies besides standard Python libraries.
- class geom2d.voronoi.DelaunayEdge(p1: TPoint, p2: TPoint)¶
A Delaunay edge.
The dual of a corresponding Voronoi segment that bisects this Delaunay segment. This is a line segment between nearest neighbor sites.
- p1: Sequence[float]¶
Alias for field number 0
- p2: Sequence[float]¶
Alias for field number 1
- class geom2d.voronoi.DelaunayTriangle(p1: TPoint, p2: TPoint, p3: TPoint)¶
A Delaunay triangle. This a 3-tuple of 2-tuple (x, y) points.
- p1: Sequence[float]¶
Alias for field number 0
- p2: Sequence[float]¶
Alias for field number 1
- p3: Sequence[float]¶
Alias for field number 2
- geom2d.voronoi.EPSILON = 1e-09¶
Tolerance for floating point comparisons
- class geom2d.voronoi.VoronoiDiagram(input_points: Sequence[Sequence[float]], delaunay: bool = False, jiggle_points: bool = False)¶
Voronoi diagram and Delaunay triangulation.
- property delaunay_edges: list[DelaunayEdge]¶
List of DelaunayEdges.
- property edges: list[VoronoiEdge]¶
List of VoronoiEdges.
- property lines: list[tuple[float, float, float]]¶
List of Voronoi edges as line equations.
A line is a 3-tuple (a, b, c) for the line equation of the form a*x + b*y = c.
- property triangles: list[DelaunayTriangle]¶
List of DelaunayTriangles.
- property vertices: list[Sequence[float]]¶
List of Voronoi diagram vertices.
- class geom2d.voronoi.VoronoiEdge(p1: TPoint | None, p2: TPoint | None, equation: TLineEq, delaunay_edge: DelaunayEdge)¶
A Voronoi edge.
The dual of a corresponding Delauney edge. This is a line segment that bisects a line between nearest neighbor sites.
If one end point of the edge is None it means the line extends to infinity. If the first end point is None the edge extends to the left. If the second end point is None the edge extends to the right.
- delaunay_edge: DelaunayEdge¶
Alias for field number 3
- equation: tuple[float, float, float]¶
Alias for field number 2
- p1: Sequence[float] | None¶
Alias for field number 0
- p2: Sequence[float] | None¶
Alias for field number 1
- geom2d.voronoi.jiggle(point: Sequence[float]) Sequence[float]¶
Move a point in a random direction by a very small random distance.
Useful for when input is degenerate (i.e. when points are collinear.) avoiding divide by zero exceptions.
- Parameters:
point – The point as a 2-tuple of the form (x, y)
- Returns:
A new jiggled point as a 2-tuple