Class VoronoiDiagramBuilder

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12	package org.locationtech.jts.triangulate;
13
14	import java.util.ArrayList;
15	import java.util.Collection;
16	import java.util.List;
17
18	import org.locationtech.jts.geom.Coordinate;
19	import org.locationtech.jts.geom.CoordinateArrays;
20	import org.locationtech.jts.geom.Envelope;
21	import org.locationtech.jts.geom.Geometry;
22	import org.locationtech.jts.geom.GeometryCollection;
23	import org.locationtech.jts.geom.GeometryFactory;
24	import org.locationtech.jts.geom.Polygon;
25	import org.locationtech.jts.triangulate.quadedge.QuadEdgeSubdivision;
26
27
28	/**
29	* A utility class which creates Voronoi Diagrams
30	* from collections of points.
31	* The diagram is returned as a {@link GeometryCollection} of {@link Polygon}s
32	* representing the faces of the Voronoi diagram.
33	* The faces are clipped to the larger of:
34	* <ul>
35	* <li> an envelope supplied by {@link #setClipEnvelope(Envelope)}
36	* <li> an envelope determined by the input sites
37	* </ul>
38	* The <tt>userData</tt> attribute of each face <tt>Polygon</tt> is set to
39	* the <tt>Coordinate</tt> of the corresponding input site.
40	* This allows using a <tt>Map</tt> to link faces to data associated with sites.
41	*
42	* @author Martin Davis
43	*
44	*/
45	public class VoronoiDiagramBuilder
46	{
47	private Collection siteCoords;
48	private double tolerance = 0.0;
49	private QuadEdgeSubdivision subdiv = null;
50	private Envelope clipEnv = null;
51	private Envelope diagramEnv = null;
52
53	/**
54	* Creates a new Voronoi diagram builder.
55	*
56	*/
57	public VoronoiDiagramBuilder()
58	{
59	}
60
61	/**
62	* Sets the sites (point or vertices) which will be diagrammed.
63	* All vertices of the given geometry will be used as sites.
64	*
65	* @param geom the geometry from which the sites will be extracted.
66	*/
67	public void setSites(Geometry geom)
68	{
69	// remove any duplicate points (they will cause the triangulation to fail)
70	siteCoords = DelaunayTriangulationBuilder.extractUniqueCoordinates(geom);
71	}
72
73	/**
74	* Sets the sites (point or vertices) which will be diagrammed
75	* from a collection of {@link Coordinate}s.
76	*
77	* @param coords a collection of Coordinates.
78	*/
79	public void setSites(Collection coords)
80	{
81	// remove any duplicate points (they will cause the triangulation to fail)
82	siteCoords = DelaunayTriangulationBuilder.unique(CoordinateArrays.toCoordinateArray(coords));
83	}
84
85	/**
86	* Sets the envelope to clip the diagram to.
87	* The diagram will be clipped to the larger
88	* of this envelope or an envelope surrounding the sites.
89	*
90	* @param clipEnv the clip envelope.
91	*/
92	public void setClipEnvelope(Envelope clipEnv)
93	{
94	this.clipEnv = clipEnv;
95	}
96	/**
97	* Sets the snapping tolerance which will be used
98	* to improved the robustness of the triangulation computation.
99	* A tolerance of 0.0 specifies that no snapping will take place.
100	*
101	* @param tolerance the tolerance distance to use
102	*/
103	public void setTolerance(double tolerance)
104	{
105	this.tolerance = tolerance;
106	}
107
108	private void create()
109	{
110	if (subdiv != null) return;
111
112	Envelope siteEnv = DelaunayTriangulationBuilder.envelope(siteCoords);
113	diagramEnv = clipEnv;
114	if (diagramEnv == null) {
115	/**
116	* If no user-provided clip env,
117	* create one which encloses all the sites,
118	* with a buffer around the edges.
119	*/
120	diagramEnv = siteEnv;
121	// add a buffer around the sites envelope
122	double expandBy = diagramEnv.getDiameter();
123	diagramEnv.expandBy(expandBy);
124	}
125
126	List vertices = DelaunayTriangulationBuilder.toVertices(siteCoords);
127	subdiv = new QuadEdgeSubdivision(siteEnv, tolerance);
128	IncrementalDelaunayTriangulator triangulator = new IncrementalDelaunayTriangulator(subdiv);
129	triangulator.insertSites(vertices);
130	}
131
132	/**
133	* Gets the {@link QuadEdgeSubdivision} which models the computed diagram.
134	*
135	* @return the subdivision containing the triangulation
136	*/
137	public QuadEdgeSubdivision getSubdivision()
138	{
139	create();
140	return subdiv;
141	}
142
143	/**
144	* Gets the faces of the computed diagram as a {@link GeometryCollection}
145	* of {@link Polygon}s, clipped as specified.
146	* <p>
147	* The <tt>userData</tt> attribute of each face <tt>Polygon</tt> is set to
148	* the <tt>Coordinate</tt> of the corresponding input site.
149	* This allows using a <tt>Map</tt> to link faces to data associated with sites.
150	*
151	* @param geomFact the geometry factory to use to create the output
152	* @return a <tt>GeometryCollection</tt> containing the face <tt>Polygon</tt>s of the diagram
153	*/
154	public Geometry getDiagram(GeometryFactory geomFact)
155	{
156	create();
157	Geometry polys = subdiv.getVoronoiDiagram(geomFact);
158
159	// clip polys to diagramEnv
160	return clipGeometryCollection(polys, diagramEnv);
161	}
162
163	private static Geometry clipGeometryCollection(Geometry geom, Envelope clipEnv)
164	{
165	Geometry clipPoly = geom.getFactory().toGeometry(clipEnv);
166	List clipped = new ArrayList();
167	for (int i = 0; i < geom.getNumGeometries(); i++) {
168	Geometry g = geom.getGeometryN(i);
169	Geometry result = null;
170	// don't clip unless necessary
171	if (clipEnv.contains(g.getEnvelopeInternal()))
172	result = g;
173	else if (clipEnv.intersects(g.getEnvelopeInternal())) {
174	result = clipPoly.intersection(g);
175	// keep vertex key info
176	result.setUserData(g.getUserData());
177	}
178
179	if (result != null && ! result.isEmpty()) {
180	clipped.add(result);
181	}
182	}
183	return geom.getFactory().createGeometryCollection(GeometryFactory.toGeometryArray(clipped));
184	}
185	}
186