Class DelaunayTriangulationBuilder

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.Arrays;
16	import java.util.Collection;
17	import java.util.Iterator;
18	import java.util.List;
19
20	import org.locationtech.jts.geom.Coordinate;
21	import org.locationtech.jts.geom.CoordinateArrays;
22	import org.locationtech.jts.geom.CoordinateList;
23	import org.locationtech.jts.geom.Envelope;
24	import org.locationtech.jts.geom.Geometry;
25	import org.locationtech.jts.geom.GeometryCollection;
26	import org.locationtech.jts.geom.GeometryFactory;
27	import org.locationtech.jts.geom.MultiLineString;
28	import org.locationtech.jts.geom.Polygon;
29	import org.locationtech.jts.triangulate.quadedge.QuadEdgeSubdivision;
30	import org.locationtech.jts.triangulate.quadedge.Vertex;
31
32
33	/**
34	* A utility class which creates Delaunay Triangulations
35	* from collections of points and extract the resulting
36	* triangulation edges or triangles as geometries.
37	*
38	* @author Martin Davis
39	*
40	*/
41	public class DelaunayTriangulationBuilder
42	{
43	/**
44	* Extracts the unique {@link Coordinate}s from the given {@link Geometry}.
45	* @param geom the geometry to extract from
46	* @return a List of the unique Coordinates
47	*/
48	public static CoordinateList extractUniqueCoordinates(Geometry geom)
49	{
50	if (geom == null)
51	return new CoordinateList();
52
53	Coordinate[] coords = geom.getCoordinates();
54	return unique(coords);
55	}
56
57	public static CoordinateList unique(Coordinate[] coords)
58	{
59	Coordinate[] coordsCopy = CoordinateArrays.copyDeep(coords);
60	Arrays.sort(coordsCopy);
61	CoordinateList coordList = new CoordinateList(coordsCopy, false);
62	return coordList;
63	}
64
65	/**
66	* Converts all {@link Coordinate}s in a collection to {@link Vertex}es.
67	* @param coords the coordinates to convert
68	* @return a List of Vertex objects
69	*/
70	public static List toVertices(Collection coords)
71	{
72	List verts = new ArrayList();
73	for (Iterator i = coords.iterator(); i.hasNext(); ) {
74	Coordinate coord = (Coordinate) i.next();
75	verts.add(new Vertex(coord));
76	}
77	return verts;
78	}
79
80	/**
81	* Computes the {@link Envelope} of a collection of {@link Coordinate}s.
82	*
83	* @param coords a List of Coordinates
84	* @return the envelope of the set of coordinates
85	*/
86	public static Envelope envelope(Collection coords)
87	{
88	Envelope env = new Envelope();
89	for (Iterator i = coords.iterator(); i.hasNext(); ) {
90	Coordinate coord = (Coordinate) i.next();
91	env.expandToInclude(coord);
92	}
93	return env;
94	}
95
96	private Collection siteCoords;
97	private double tolerance = 0.0;
98	private QuadEdgeSubdivision subdiv = null;
99
100	/**
101	* Creates a new triangulation builder.
102	*
103	*/
104	public DelaunayTriangulationBuilder()
105	{
106	}
107
108	/**
109	* Sets the sites (vertices) which will be triangulated.
110	* All vertices of the given geometry will be used as sites.
111	*
112	* @param geom the geometry from which the sites will be extracted.
113	*/
114	public void setSites(Geometry geom)
115	{
116	// remove any duplicate points (they will cause the triangulation to fail)
117	siteCoords = extractUniqueCoordinates(geom);
118	}
119
120	/**
121	* Sets the sites (vertices) which will be triangulated
122	* from a collection of {@link Coordinate}s.
123	*
124	* @param coords a collection of Coordinates.
125	*/
126	public void setSites(Collection coords)
127	{
128	// remove any duplicate points (they will cause the triangulation to fail)
129	siteCoords = unique(CoordinateArrays.toCoordinateArray(coords));
130	}
131
132	/**
133	* Sets the snapping tolerance which will be used
134	* to improved the robustness of the triangulation computation.
135	* A tolerance of 0.0 specifies that no snapping will take place.
136	*
137	* @param tolerance the tolerance distance to use
138	*/
139	public void setTolerance(double tolerance)
140	{
141	this.tolerance = tolerance;
142	}
143
144	private void create()
145	{
146	if (subdiv != null) return;
147
148	Envelope siteEnv = envelope(siteCoords);
149	List vertices = toVertices(siteCoords);
150	subdiv = new QuadEdgeSubdivision(siteEnv, tolerance);
151	IncrementalDelaunayTriangulator triangulator = new IncrementalDelaunayTriangulator(subdiv);
152	triangulator.insertSites(vertices);
153	}
154
155	/**
156	* Gets the {@link QuadEdgeSubdivision} which models the computed triangulation.
157	*
158	* @return the subdivision containing the triangulation
159	*/
160	public QuadEdgeSubdivision getSubdivision()
161	{
162	create();
163	return subdiv;
164	}
165
166	/**
167	* Gets the edges of the computed triangulation as a {@link MultiLineString}.
168	*
169	* @param geomFact the geometry factory to use to create the output
170	* @return the edges of the triangulation
171	*/
172	public Geometry getEdges(GeometryFactory geomFact)
173	{
174	create();
175	return subdiv.getEdges(geomFact);
176	}
177
178	/**
179	* Gets the faces of the computed triangulation as a {@link GeometryCollection}
180	* of {@link Polygon}.
181	*
182	* @param geomFact the geometry factory to use to create the output
183	* @return the faces of the triangulation
184	*/
185	public Geometry getTriangles(GeometryFactory geomFact)
186	{
187	create();
188	return subdiv.getTriangles(geomFact);
189	}
190	}
191