Class ConformingDelaunayTriangulationBuilder

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.Iterator;
17	import java.util.List;
18	import java.util.Map;
19	import java.util.TreeMap;
20
21	import org.locationtech.jts.geom.Coordinate;
22	import org.locationtech.jts.geom.Envelope;
23	import org.locationtech.jts.geom.Geometry;
24	import org.locationtech.jts.geom.GeometryCollection;
25	import org.locationtech.jts.geom.GeometryFactory;
26	import org.locationtech.jts.geom.LineString;
27	import org.locationtech.jts.geom.MultiLineString;
28	import org.locationtech.jts.geom.Polygon;
29	import org.locationtech.jts.geom.util.LinearComponentExtracter;
30	import org.locationtech.jts.triangulate.quadedge.QuadEdgeSubdivision;
31	import org.locationtech.jts.triangulate.quadedge.Vertex;
32
33
34	/**
35	* A utility class which creates Conforming Delaunay Triangulations
36	* from collections of points and linear constraints, and extract the resulting
37	* triangulation edges or triangles as geometries.
38	*
39	* @author Martin Davis
40	*
41	*/
42	public class ConformingDelaunayTriangulationBuilder
43	{
44	private Collection siteCoords;
45	private Geometry constraintLines;
46	private double tolerance = 0.0;
47	private QuadEdgeSubdivision subdiv = null;
48
49	private Map constraintVertexMap = new TreeMap();
50
51	public ConformingDelaunayTriangulationBuilder()
52	{
53	}
54
55	/**
56	* Sets the sites (point or vertices) which will be triangulated.
57	* All vertices of the given geometry will be used as sites.
58	* The site vertices do not have to contain the constraint
59	* vertices as well; any site vertices which are
60	* identical to a constraint vertex will be removed
61	* from the site vertex set.
62	*
63	* @param geom the geometry from which the sites will be extracted.
64	*/
65	public void setSites(Geometry geom)
66	{
67	siteCoords = DelaunayTriangulationBuilder.extractUniqueCoordinates(geom);
68	}
69
70	/**
71	* Sets the linear constraints to be conformed to.
72	* All linear components in the input will be used as constraints.
73	* The constraint vertices do not have to be disjoint from
74	* the site vertices.
75	* The constraints must not contain duplicate segments (up to orientation).
76	*
77	* @param constraintLines the lines to constraint to
78	*/
79	public void setConstraints(Geometry constraintLines)
80	{
81	this.constraintLines = constraintLines;
82	}
83
84	/**
85	* Sets the snapping tolerance which will be used
86	* to improved the robustness of the triangulation computation.
87	* A tolerance of 0.0 specifies that no snapping will take place.
88	*
89	* @param tolerance the tolerance distance to use
90	*/
91	public void setTolerance(double tolerance)
92	{
93	this.tolerance = tolerance;
94	}
95
96
97	private void create()
98	{
99	if (subdiv != null) return;
100
101	Envelope siteEnv = DelaunayTriangulationBuilder.envelope(siteCoords);
102
103	List segments = new ArrayList();
104	if (constraintLines != null) {
105	siteEnv.expandToInclude(constraintLines.getEnvelopeInternal());
106	createVertices(constraintLines);
107	segments = createConstraintSegments(constraintLines);
108	}
109	List sites = createSiteVertices(siteCoords);
110
111	ConformingDelaunayTriangulator cdt = new ConformingDelaunayTriangulator(sites, tolerance);
112
113	cdt.setConstraints(segments, new ArrayList(constraintVertexMap.values()));
114
115	cdt.formInitialDelaunay();
116	cdt.enforceConstraints();
117	subdiv = cdt.getSubdivision();
118	}
119
120	private List createSiteVertices(Collection coords)
121	{
122	List verts = new ArrayList();
123	for (Iterator i = coords.iterator(); i.hasNext(); ) {
124	Coordinate coord = (Coordinate) i.next();
125	if (constraintVertexMap.containsKey(coord))
126	continue;
127	verts.add(new ConstraintVertex(coord));
128	}
129	return verts;
130	}
131
132	private void createVertices(Geometry geom)
133	{
134	Coordinate[] coords = geom.getCoordinates();
135	for (int i = 0; i < coords.length; i++) {
136	Vertex v = new ConstraintVertex(coords[i]);
137	constraintVertexMap.put(coords[i], v);
138	}
139	}
140
141	private static List createConstraintSegments(Geometry geom)
142	{
143	List lines = LinearComponentExtracter.getLines(geom);
144	List constraintSegs = new ArrayList();
145	for (Iterator i = lines.iterator(); i.hasNext(); ) {
146	LineString line = (LineString) i.next();
147	createConstraintSegments(line, constraintSegs);
148	}
149	return constraintSegs;
150	}
151
152	private static void createConstraintSegments(LineString line, List constraintSegs)
153	{
154	Coordinate[] coords = line.getCoordinates();
155	for (int i = 1; i < coords.length; i++) {
156	constraintSegs.add(new Segment(coords[i-1], coords[i]));
157	}
158	}
159
160	/**
161	* Gets the QuadEdgeSubdivision which models the computed triangulation.
162	*
163	* @return the subdivision containing the triangulation
164	*/
165	public QuadEdgeSubdivision getSubdivision()
166	{
167	create();
168	return subdiv;
169	}
170
171	/**
172	* Gets the edges of the computed triangulation as a {@link MultiLineString}.
173	*
174	* @param geomFact the geometry factory to use to create the output
175	* @return the edges of the triangulation
176	*/
177	public Geometry getEdges(GeometryFactory geomFact)
178	{
179	create();
180	return subdiv.getEdges(geomFact);
181	}
182
183	/**
184	* Gets the faces of the computed triangulation as a {@link GeometryCollection}
185	* of {@link Polygon}.
186	*
187	* @param geomFact the geometry factory to use to create the output
188	* @return the faces of the triangulation
189	*/
190	public Geometry getTriangles(GeometryFactory geomFact)
191	{
192	create();
193	return subdiv.getTriangles(geomFact);
194	}
195
196	}
197
198
199