Class EdgeRing

1
2	/*
3	* Copyright (c) 2016 Vivid Solutions.
4	*
5	* All rights reserved. This program and the accompanying materials
6	* are made available under the terms of the Eclipse Public License 2.0
7	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
8	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
9	* and the Eclipse Distribution License is available at
10	*
11	* http://www.eclipse.org/org/documents/edl-v10.php.
12	*/
13
14
15	package org.locationtech.jts.operation.polygonize;
16
17	import java.util.ArrayList;
18	import java.util.Comparator;
19	import java.util.Iterator;
20	import java.util.List;
21
22	import org.locationtech.jts.algorithm.Orientation;
23	import org.locationtech.jts.algorithm.locate.IndexedPointInAreaLocator;
24	import org.locationtech.jts.algorithm.locate.PointOnGeometryLocator;
25	import org.locationtech.jts.geom.Coordinate;
26	import org.locationtech.jts.geom.CoordinateArrays;
27	import org.locationtech.jts.geom.CoordinateList;
28	import org.locationtech.jts.geom.Envelope;
29	import org.locationtech.jts.geom.GeometryFactory;
30	import org.locationtech.jts.geom.LineString;
31	import org.locationtech.jts.geom.LinearRing;
32	import org.locationtech.jts.geom.Location;
33	import org.locationtech.jts.geom.Polygon;
34	import org.locationtech.jts.geom.impl.CoordinateArraySequence;
35	import org.locationtech.jts.io.WKTWriter;
36	import org.locationtech.jts.planargraph.DirectedEdge;
37	import org.locationtech.jts.util.Assert;
38
39
40	/**
41	* Represents a ring of {@link PolygonizeDirectedEdge}s which form
42	* a ring of a polygon. The ring may be either an outer shell or a hole.
43	*
44	* @version 1.7
45	*/
46	class EdgeRing {
47
48	/**
49	* Find the innermost enclosing shell EdgeRing containing the argument EdgeRing, if any.
50	* The innermost enclosing ring is the <i>smallest</i> enclosing ring.
51	* The algorithm used depends on the fact that:
52	* <br>
53	* ring A contains ring B iff envelope(ring A) contains envelope(ring B)
54	* <br>
55	* This routine is only safe to use if the chosen point of the hole
56	* is known to be properly contained in a shell
57	* (which is guaranteed to be the case if the hole does not touch its shell)
58	* <p>
59	* To improve performance of this function the caller should
60	* make the passed shellList as small as possible (e.g.
61	* by using a spatial index filter beforehand).
62	*
63	* @return containing EdgeRing, if there is one
64	* or null if no containing EdgeRing is found
65	*/
66	public static EdgeRing findEdgeRingContaining(EdgeRing testEr, List erList)
67	{
68	LinearRing testRing = testEr.getRing();
69	Envelope testEnv = testRing.getEnvelopeInternal();
70	Coordinate testPt = testRing.getCoordinateN(0);
71
72	EdgeRing minRing = null;
73	Envelope minRingEnv = null;
74	for (Iterator it = erList.iterator(); it.hasNext(); ) {
75	EdgeRing tryEdgeRing = (EdgeRing) it.next();
76	LinearRing tryRing = tryEdgeRing.getRing();
77	Envelope tryShellEnv = tryRing.getEnvelopeInternal();
78	// the hole envelope cannot equal the shell envelope
79	// (also guards against testing rings against themselves)
80	if (tryShellEnv.equals(testEnv)) continue;
81
82	// hole must be contained in shell
83	if (! tryShellEnv.contains(testEnv)) continue;
84
85	testPt = CoordinateArrays.ptNotInList(testRing.getCoordinates(), tryEdgeRing.getCoordinates());
86
87	boolean isContained = tryEdgeRing.isInRing(testPt);
88
89	// check if the new containing ring is smaller than the current minimum ring
90	if (isContained) {
91	if (minRing == null
92	\|\| minRingEnv.contains(tryShellEnv)) {
93	minRing = tryEdgeRing;
94	minRingEnv = minRing.getRing().getEnvelopeInternal();
95	}
96	}
97	}
98	return minRing;
99	}
100
101	/**
102	* Traverses a ring of DirectedEdges, accumulating them into a list.
103	* This assumes that all dangling directed edges have been removed
104	* from the graph, so that there is always a next dirEdge.
105	*
106	* @param startDE the DirectedEdge to start traversing at
107	* @return a List of DirectedEdges that form a ring
108	*/
109	public static List findDirEdgesInRing(PolygonizeDirectedEdge startDE)
110	{
111	PolygonizeDirectedEdge de = startDE;
112	List edges = new ArrayList();
113	do {
114	edges.add(de);
115	de = de.getNext();
116	Assert.isTrue(de != null, "found null DE in ring");
117	Assert.isTrue(de == startDE \|\| ! de.isInRing(), "found DE already in ring");
118	} while (de != startDE);
119	return edges;
120	}
121
122	private GeometryFactory factory;
123
124	private List deList = new ArrayList();
125	private DirectedEdge lowestEdge = null;
126
127	// cache the following data for efficiency
128	private LinearRing ring = null;
129	private IndexedPointInAreaLocator locator;
130
131	private Coordinate[] ringPts = null;
132	private List holes;
133	private EdgeRing shell;
134	private boolean isHole;
135	private boolean isProcessed = false;
136	private boolean isIncludedSet = false;
137	private boolean isIncluded = false;
138
139	public EdgeRing(GeometryFactory factory)
140	{
141	this.factory = factory;
142	}
143
144	public void build(PolygonizeDirectedEdge startDE) {
145	PolygonizeDirectedEdge de = startDE;
146	do {
147	add(de);
148	de.setRing(this);
149	de = de.getNext();
150	Assert.isTrue(de != null, "found null DE in ring");
151	Assert.isTrue(de == startDE \|\| ! de.isInRing(), "found DE already in ring");
152	} while (de != startDE);
153	}
154
155	/**
156	* Adds a {@link DirectedEdge} which is known to form part of this ring.
157	* @param de the {@link DirectedEdge} to add.
158	*/
159	private void add(DirectedEdge de)
160	{
161	deList.add(de);
162	}
163
164	/**
165	* Tests whether this ring is a hole.
166	* @return <code>true</code> if this ring is a hole
167	*/
168	public boolean isHole()
169	{
170	return isHole;
171	}
172
173	/**
174	* Computes whether this ring is a hole.
175	* Due to the way the edges in the polygonization graph are linked,
176	* a ring is a hole if it is oriented counter-clockwise.
177	*/
178	public void computeHole()
179	{
180	LinearRing ring = getRing();
181	isHole = Orientation.isCCW(ring.getCoordinates());
182	}
183
184	/**
185	* Adds a hole to the polygon formed by this ring.
186	* @param hole the {@link LinearRing} forming the hole.
187	*/
188	public void addHole(LinearRing hole) {
189	if (holes == null)
190	holes = new ArrayList();
191	holes.add(hole);
192	}
193
194	/**
195	* Adds a hole to the polygon formed by this ring.
196	* @param hole the {@link LinearRing} forming the hole.
197	*/
198	public void addHole(EdgeRing holeER) {
199	holeER.setShell(this);
200	LinearRing hole = holeER.getRing();
201	if (holes == null)
202	holes = new ArrayList();
203	holes.add(hole);
204	}
205
206	/**
207	* Computes the {@link Polygon} formed by this ring and any contained holes.
208	*
209	* @return the {@link Polygon} formed by this ring and its holes.
210	*/
211	public Polygon getPolygon()
212	{
213	LinearRing[] holeLR = null;
214	if (holes != null) {
215	holeLR = new LinearRing[holes.size()];
216	for (int i = 0; i < holes.size(); i++) {
217	holeLR[i] = (LinearRing) holes.get(i);
218	}
219	}
220	Polygon poly = factory.createPolygon(ring, holeLR);
221	return poly;
222	}
223
224	/**
225	* Tests if the {@link LinearRing} ring formed by this edge ring is topologically valid.
226	*
227	* @return true if the ring is valid
228	*/
229	public boolean isValid()
230	{
231	getCoordinates();
232	if (ringPts.length <= 3) return false;
233	getRing();
234	return ring.isValid();
235	}
236
237	public boolean isIncludedSet() {
238	return isIncludedSet;
239	}
240
241	public boolean isIncluded() {
242	return isIncluded;
243	}
244
245	public void setIncluded(boolean isIncluded) {
246	this.isIncluded = isIncluded;
247	this.isIncludedSet = true;
248	}
249
250	private PointOnGeometryLocator getLocator() {
251	if (locator == null) {
252	locator = new IndexedPointInAreaLocator(getRing());
253	}
254	return locator;
255	}
256
257	public boolean isInRing(Coordinate pt) {
258	/**
259	* Use an indexed point-in-polygon for performance
260	*/
261	return Location.EXTERIOR != getLocator().locate(pt);
262	//return PointLocation.isInRing(pt, getCoordinates());
263	}
264
265	/**
266	* Computes the list of coordinates which are contained in this ring.
267	* The coordinates are computed once only and cached.
268	*
269	* @return an array of the {@link Coordinate}s in this ring
270	*/
271	private Coordinate[] getCoordinates()
272	{
273	if (ringPts == null) {
274	CoordinateList coordList = new CoordinateList();
275	for (Iterator i = deList.iterator(); i.hasNext(); ) {
276	DirectedEdge de = (DirectedEdge) i.next();
277	PolygonizeEdge edge = (PolygonizeEdge) de.getEdge();
278	addEdge(edge.getLine().getCoordinates(), de.getEdgeDirection(), coordList);
279	}
280	ringPts = coordList.toCoordinateArray();
281	}
282	return ringPts;
283	}
284
285	/**
286	* Gets the coordinates for this ring as a {@link LineString}.
287	* Used to return the coordinates in this ring
288	* as a valid geometry, when it has been detected that the ring is topologically
289	* invalid.
290	* @return a {@link LineString} containing the coordinates in this ring
291	*/
292	public LineString getLineString()
293	{
294	getCoordinates();
295	return factory.createLineString(ringPts);
296	}
297
298	/**
299	* Returns this ring as a {@link LinearRing}, or null if an Exception occurs while
300	* creating it (such as a topology problem). Details of problems are written to
301	* standard output.
302	*/
303	public LinearRing getRing()
304	{
305	if (ring != null) return ring;
306	getCoordinates();
307	if (ringPts.length < 3) System.out.println(ringPts);
308	try {
309	ring = factory.createLinearRing(ringPts);
310	}
311	catch (Exception ex) {
312	System.out.println(ringPts);
313	}
314	return ring;
315	}
316
317	private static void addEdge(Coordinate[] coords, boolean isForward, CoordinateList coordList)
318	{
319	if (isForward) {
320	for (int i = 0; i < coords.length; i++) {
321	coordList.add(coords[i], false);
322	}
323	}
324	else {
325	for (int i = coords.length - 1; i >= 0; i--) {
326	coordList.add(coords[i], false);
327	}
328	}
329	}
330
331	/**
332	* Sets the containing shell ring of a ring that has been determined to be a hole.
333	*
334	* @param shell the shell ring
335	*/
336	public void setShell(EdgeRing shell) {
337	this.shell = shell;
338	}
339
340	/**
341	* Tests whether this ring has a shell assigned to it.
342	*
343	* @return true if the ring has a shell
344	*/
345	public boolean hasShell() {
346	return shell != null;
347	}
348
349	/**
350	* Gets the shell for this ring. The shell is the ring itself if it is not a hole, otherwise its parent shell.
351	*
352	* @return the shell for this ring
353	*/
354	public EdgeRing getShell() {
355	if (isHole()) return shell;
356	return this;
357	}
358	/**
359	* Tests whether this ring is an outer hole.
360	* A hole is an outer hole if it is not contained by a shell.
361	*
362	* @return true if the ring is an outer hole.
363	*/
364	public boolean isOuterHole() {
365	if (! isHole) return false;
366	return ! hasShell();
367	}
368
369	/**
370	* Tests whether this ring is an outer shell.
371	*
372	* @return true if the ring is an outer shell.
373	*/
374	public boolean isOuterShell() {
375	return getOuterHole() != null;
376	}
377
378	/**
379	* Gets the outer hole of a shell, if it has one.
380	* An outer hole is one that is not contained
381	* in any other shell.
382	* Each disjoint connected group of shells
383	* is surrounded by an outer hole.
384	*
385	* @return the outer hole edge ring, or null
386	*/
387	public EdgeRing getOuterHole()
388	{
389	/*
390	* Only shells can have outer holes
391	*/
392	if (isHole()) return null;
393	/*
394	* A shell is an outer shell if any edge is also in an outer hole.
395	* A hole is an outer hole if it is not contained by a shell.
396	*/
397	for (int i = 0; i < deList.size(); i++) {
398	PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) deList.get(i);
399	EdgeRing adjRing = ((PolygonizeDirectedEdge) de.getSym()).getRing();
400	if (adjRing.isOuterHole()) return adjRing;
401	}
402	return null;
403	}
404
405	/**
406	* Updates the included status for currently non-included shells
407	* based on whether they are adjacent to an included shell.
408	*/
409	public void updateIncluded() {
410	if (isHole()) return;
411	for (int i = 0; i < deList.size(); i++) {
412	PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) deList.get(i);
413	EdgeRing adjShell = ((PolygonizeDirectedEdge) de.getSym()).getRing().getShell();
414
415	if (adjShell != null && adjShell.isIncludedSet()) {
416	// adjacent ring has been processed, so set included to inverse of adjacent included
417	setIncluded(! adjShell.isIncluded());
418	return;
419	}
420	}
421	}
422
423	/**
424	* Gets a string representation of this object.
425	*
426	* @return a string representing the object
427	*/
428	public String toString() {
429	return WKTWriter.toLineString(new CoordinateArraySequence(getCoordinates()));
430	}
431
432	/**
433	* @return whether the ring has been processed
434	*/
435	public boolean isProcessed() {
436	return isProcessed;
437	}
438
439	/**
440	* @param isProcessed whether the ring has been processed
441	*/
442	public void setProcessed(boolean isProcessed) {
443	this.isProcessed = isProcessed;
444	}
445
446	/**
447	* Compares EdgeRings based on their envelope,
448	* using the standard lexicographic ordering.
449	* This ordering is sufficient to make edge ring sorting deterministic.
450	*
451	* @author mbdavis
452	*
453	*/
454	static class EnvelopeComparator implements Comparator {
455	public int compare(Object obj0, Object obj1) {
456	EdgeRing r0 = (EdgeRing) obj0;
457	EdgeRing r1 = (EdgeRing) obj1;
458	return r0.getRing().getEnvelope().compareTo(r1.getRing().getEnvelope());
459	}
460
461	}
462
463	}
464