Class PolygonBuilder

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.operation.overlay;
13
14	import java.util.ArrayList;
15	import java.util.Collection;
16	import java.util.Iterator;
17	import java.util.List;
18
19	import org.locationtech.jts.algorithm.PointLocation;
20	import org.locationtech.jts.geom.Coordinate;
21	import org.locationtech.jts.geom.CoordinateArrays;
22	import org.locationtech.jts.geom.Envelope;
23	import org.locationtech.jts.geom.GeometryFactory;
24	import org.locationtech.jts.geom.LinearRing;
25	import org.locationtech.jts.geom.Polygon;
26	import org.locationtech.jts.geom.TopologyException;
27	import org.locationtech.jts.geomgraph.DirectedEdge;
28	import org.locationtech.jts.geomgraph.EdgeRing;
29	import org.locationtech.jts.geomgraph.PlanarGraph;
30	import org.locationtech.jts.util.Assert;
31
32	/**
33	* Forms {@link Polygon}s out of a graph of {@link DirectedEdge}s.
34	* The edges to use are marked as being in the result Area.
35	* <p>
36	*
37	* @version 1.7
38	*/
39	public class PolygonBuilder {
40
41	private GeometryFactory geometryFactory;
42	private List shellList = new ArrayList();
43
44	public PolygonBuilder(GeometryFactory geometryFactory)
45	{
46	this.geometryFactory = geometryFactory;
47	}
48
49	/**
50	* Add a complete graph.
51	* The graph is assumed to contain one or more polygons,
52	* possibly with holes.
53	*/
54	public void add(PlanarGraph graph)
55	{
56	add(graph.getEdgeEnds(), graph.getNodes());
57	}
58
59	/**
60	* Add a set of edges and nodes, which form a graph.
61	* The graph is assumed to contain one or more polygons,
62	* possibly with holes.
63	*/
64	public void add(Collection dirEdges, Collection nodes)
65	{
66	PlanarGraph.linkResultDirectedEdges(nodes);
67	List maxEdgeRings = buildMaximalEdgeRings(dirEdges);
68	List freeHoleList = new ArrayList();
69	List edgeRings = buildMinimalEdgeRings(maxEdgeRings, shellList, freeHoleList);
70	sortShellsAndHoles(edgeRings, shellList, freeHoleList);
71	placeFreeHoles(shellList, freeHoleList);
72	//Assert: every hole on freeHoleList has a shell assigned to it
73	}
74
75	public List getPolygons()
76	{
77	List resultPolyList = computePolygons(shellList);
78	return resultPolyList;
79	}
80
81
82	/**
83	* for all DirectedEdges in result, form them into MaximalEdgeRings
84	*/
85	private List buildMaximalEdgeRings(Collection dirEdges)
86	{
87	List maxEdgeRings = new ArrayList();
88	for (Iterator it = dirEdges.iterator(); it.hasNext(); ) {
89	DirectedEdge de = (DirectedEdge) it.next();
90	if (de.isInResult() && de.getLabel().isArea() ) {
91	// if this edge has not yet been processed
92	if (de.getEdgeRing() == null) {
93	MaximalEdgeRing er = new MaximalEdgeRing(de, geometryFactory);
94	maxEdgeRings.add(er);
95	er.setInResult();
96	//System.out.println("max node degree = " + er.getMaxDegree());
97	}
98	}
99	}
100	return maxEdgeRings;
101	}
102
103	private List buildMinimalEdgeRings(List maxEdgeRings, List shellList, List freeHoleList)
104	{
105	List edgeRings = new ArrayList();
106	for (Iterator it = maxEdgeRings.iterator(); it.hasNext(); ) {
107	MaximalEdgeRing er = (MaximalEdgeRing) it.next();
108	if (er.getMaxNodeDegree() > 2) {
109	er.linkDirectedEdgesForMinimalEdgeRings();
110	List minEdgeRings = er.buildMinimalRings();
111	// at this point we can go ahead and attempt to place holes, if this EdgeRing is a polygon
112	EdgeRing shell = findShell(minEdgeRings);
113	if (shell != null) {
114	placePolygonHoles(shell, minEdgeRings);
115	shellList.add(shell);
116	}
117	else {
118	freeHoleList.addAll(minEdgeRings);
119	}
120	}
121	else {
122	edgeRings.add(er);
123	}
124	}
125	return edgeRings;
126	}
127
128	/**
129	* This method takes a list of MinimalEdgeRings derived from a MaximalEdgeRing,
130	* and tests whether they form a Polygon. This is the case if there is a single shell
131	* in the list. In this case the shell is returned.
132	* The other possibility is that they are a series of connected holes, in which case
133	* no shell is returned.
134	*
135	* @return the shell EdgeRing, if there is one
136	* or null, if all the rings are holes
137	*/
138	private EdgeRing findShell(List minEdgeRings)
139	{
140	int shellCount = 0;
141	EdgeRing shell = null;
142	for (Iterator it = minEdgeRings.iterator(); it.hasNext(); ) {
143	EdgeRing er = (MinimalEdgeRing) it.next();
144	if (! er.isHole()) {
145	shell = er;
146	shellCount++;
147	}
148	}
149	Assert.isTrue(shellCount <= 1, "found two shells in MinimalEdgeRing list");
150	return shell;
151	}
152	/**
153	* This method assigns the holes for a Polygon (formed from a list of
154	* MinimalEdgeRings) to its shell.
155	* Determining the holes for a MinimalEdgeRing polygon serves two purposes:
156	* <ul>
157	* <li>it is faster than using a point-in-polygon check later on.
158	* <li>it ensures correctness, since if the PIP test was used the point
159	* chosen might lie on the shell, which might return an incorrect result from the
160	* PIP test
161	* </ul>
162	*/
163	private void placePolygonHoles(EdgeRing shell, List minEdgeRings)
164	{
165	for (Iterator it = minEdgeRings.iterator(); it.hasNext(); ) {
166	MinimalEdgeRing er = (MinimalEdgeRing) it.next();
167	if (er.isHole()) {
168	er.setShell(shell);
169	}
170	}
171	}
172	/**
173	* For all rings in the input list,
174	* determine whether the ring is a shell or a hole
175	* and add it to the appropriate list.
176	* Due to the way the DirectedEdges were linked,
177	* a ring is a shell if it is oriented CW, a hole otherwise.
178	*/
179	private void sortShellsAndHoles(List edgeRings, List shellList, List freeHoleList)
180	{
181	for (Iterator it = edgeRings.iterator(); it.hasNext(); ) {
182	EdgeRing er = (EdgeRing) it.next();
183	// er.setInResult();
184	if (er.isHole() ) {
185	freeHoleList.add(er);
186	}
187	else {
188	shellList.add(er);
189	}
190	}
191	}
192	/**
193	* This method determines finds a containing shell for all holes
194	* which have not yet been assigned to a shell.
195	* These "free" holes should
196	* all be <b>properly</b> contained in their parent shells, so it is safe to use the
197	* <code>findEdgeRingContaining</code> method.
198	* (This is the case because any holes which are NOT
199	* properly contained (i.e. are connected to their
200	* parent shell) would have formed part of a MaximalEdgeRing
201	* and been handled in a previous step).
202	*
203	* @throws TopologyException if a hole cannot be assigned to a shell
204	*/
205	private void placeFreeHoles(List shellList, List freeHoleList)
206	{
207	for (Iterator it = freeHoleList.iterator(); it.hasNext(); ) {
208	EdgeRing hole = (EdgeRing) it.next();
209	// only place this hole if it doesn't yet have a shell
210	if (hole.getShell() == null) {
211	EdgeRing shell = findEdgeRingContaining(hole, shellList);
212	if (shell == null)
213	throw new TopologyException("unable to assign hole to a shell", hole.getCoordinate(0));
214	// Assert.isTrue(shell != null, "unable to assign hole to a shell");
215	hole.setShell(shell);
216	}
217	}
218	}
219
220	/**
221	* Find the innermost enclosing shell EdgeRing containing the argument EdgeRing, if any.
222	* The innermost enclosing ring is the <i>smallest</i> enclosing ring.
223	* The algorithm used depends on the fact that:
224	* <br>
225	* ring A contains ring B iff envelope(ring A) contains envelope(ring B)
226	* <br>
227	* This routine is only safe to use if the chosen point of the hole
228	* is known to be properly contained in a shell
229	* (which is guaranteed to be the case if the hole does not touch its shell)
230	*
231	* @return containing EdgeRing, if there is one
232	* or null if no containing EdgeRing is found
233	*/
234	private static EdgeRing findEdgeRingContaining(EdgeRing testEr, List shellList)
235	{
236	LinearRing testRing = testEr.getLinearRing();
237	Envelope testEnv = testRing.getEnvelopeInternal();
238	Coordinate testPt = testRing.getCoordinateN(0);
239
240	EdgeRing minShell = null;
241	Envelope minShellEnv = null;
242	for (Iterator it = shellList.iterator(); it.hasNext(); ) {
243	EdgeRing tryShell = (EdgeRing) it.next();
244	LinearRing tryShellRing = tryShell.getLinearRing();
245	Envelope tryShellEnv = tryShellRing.getEnvelopeInternal();
246	// the hole envelope cannot equal the shell envelope
247	// (also guards against testing rings against themselves)
248	if (tryShellEnv.equals(testEnv)) continue;
249	// hole must be contained in shell
250	if (! tryShellEnv.contains(testEnv)) continue;
251
252	testPt = CoordinateArrays.ptNotInList(testRing.getCoordinates(), tryShellRing.getCoordinates());
253	boolean isContained = false;
254	if (PointLocation.isInRing(testPt, tryShellRing.getCoordinates()) )
255	isContained = true;
256
257	// check if this new containing ring is smaller than the current minimum ring
258	if (isContained) {
259	if (minShell == null
260	\|\| minShellEnv.contains(tryShellEnv)) {
261	minShell = tryShell;
262	minShellEnv = minShell.getLinearRing().getEnvelopeInternal();
263	}
264	}
265	}
266	return minShell;
267	}
268	private List computePolygons(List shellList)
269	{
270	List resultPolyList = new ArrayList();
271	// add Polygons for all shells
272	for (Iterator it = shellList.iterator(); it.hasNext(); ) {
273	EdgeRing er = (EdgeRing) it.next();
274	Polygon poly = er.toPolygon(geometryFactory);
275	resultPolyList.add(poly);
276	}
277	return resultPolyList;
278	}
279
280	}
281