public final class Voronoi
extends java.lang.Object
findAll(org.kynosarges.tektosyne.geometry.PointD[])
to find both the Voronoi diagram and the Delaunay triangulation for a
given PointD
set, or findDelaunay(org.kynosarges.tektosyne.geometry.PointD[])
to find only the Delaunay triangulation.
Since the outgoing edges of a Voronoi diagram continue indefinitely, Voronoi
employs
a clipping rectangle slightly larger than the bounding box of the specified point set. Voronoi
edges that cross the clipping rectangle are terminated with a pseudo-vertex at the point of
intersection. True Voronoi vertices beyond the clipping rectangle are not found. You may specify
a larger clipping rectangle if desired.
Voronoi
performs Fortune’s sweep line algorithm with an asymptotic runtime of O(n log n).
This algorithm was first published in Steven J. Fortune, A Sweepline Algorithm for Voronoi
Diagrams, Algorithmica 2 (1987), p.153-174. This Java implementation was adapted from
Fortune’s own C implementation, which used to be available as sweep2.gz
at the
archive page netlib/voronoi
of Sandia National Laboratories. Unfortunately the original URL has since become invalid.
The following copyright statement is reproduced from the original C program, as required by
the copyright conditions.
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.
Modifier and Type | Method and Description |
---|---|
static VoronoiResults |
findAll(PointD[] points)
Finds the Voronoi diagram and the Delaunay triangulation for the specified set
of
PointD coordinates, using a default clipping rectangle. |
static VoronoiResults |
findAll(PointD[] points,
RectD clip)
Finds the Voronoi diagram and the Delaunay triangulation for the specified set
of
PointD coordinates, using the specified clipping rectangle. |
static PointI[] |
findDelaunay(PointD[] points)
Finds the Delaunay triangulation for the specified set of
PointD coordinates. |
static Subdivision |
findDelaunaySubdivision(PointD[] points)
Finds the Delaunay triangulation for the specified set of
PointD coordinates
and creates the corresponding Subdivision . |
public static VoronoiResults findAll(PointD[] points)
PointD
coordinates, using a default clipping rectangle.points
- an array containing the PointD
coordinates whose
Voronoi diagram and Delaunay triangulation to findVoronoiResults
instance containing the Voronoi diagram
and Delaunay triangulation for the specified points
java.lang.IllegalArgumentException
- if points
contains less than three elementsjava.lang.NullPointerException
- if points
or any of its elements is null
public static VoronoiResults findAll(PointD[] points, RectD clip)
PointD
coordinates, using the specified clipping rectangle.
The actual clipping rectangle always extends somewhat beyond the bounding rectangle
of the specified points
. The specified clip
rectangle can only further
extend this area, not restrict it.points
- an array containing the PointD
coordinates whose
Voronoi diagram and Delaunay triangulation to findclip
- a RectD
indicating the clipping bounds for pseudo-verticesVoronoiResults
instance containing the Voronoi diagram
and Delaunay triangulation for the specified points
java.lang.IllegalArgumentException
- if points
contains less than three elementsjava.lang.NullPointerException
- if points
or clip
is null
,
or any points
element is null
public static PointI[] findDelaunay(PointD[] points)
PointD
coordinates.
The PointI.x
and PointI.y
components of each PointI
element
in the returned array hold the indices of any two points
elements that are
connected by an edge in the Delaunay triangulation.
Use LineD.fromIndexPoints(org.kynosarges.tektosyne.geometry.PointD[], org.kynosarges.tektosyne.geometry.PointI[])
to combine points
and the returned index array
into a LineD
array representing the edges of the Delaunay triangulation.
points
- an array containing the PointD
coordinates whose Delaunay triangulation to findpoints
java.lang.IllegalArgumentException
- if points
contains less than three elementsjava.lang.NullPointerException
- if points
or any of its elements is null
public static Subdivision findDelaunaySubdivision(PointD[] points)
PointD
coordinates
and creates the corresponding Subdivision
.
Convenience method that first calls findDelaunay(org.kynosarges.tektosyne.geometry.PointD[])
on the specified
points
, then LineD.fromIndexPoints(org.kynosarges.tektosyne.geometry.PointD[], org.kynosarges.tektosyne.geometry.PointI[])
on the resulting indices, and
finally Subdivision.fromLines(org.kynosarges.tektosyne.geometry.LineD[], double)
with an epsilon of zero on the resulting lines.
The Subdivision
does not include a mapping of vertices to Voronoi regions.
Call findAll(org.kynosarges.tektosyne.geometry.PointD[])
and then VoronoiResults.toDelaunaySubdivision(boolean)
to
obtain this mapping, and also to apply an optional clipping rectangle.
points
- an array containing the PointD
coordinates whose Delaunay triangulation to findSubdivision
whose Subdivision.edges()
correspond
to the edges of the Delaunay triangulation for points
java.lang.IllegalArgumentException
- if points
contains less than three elementsjava.lang.NullPointerException
- if points
or any of its elements is null