Class ConnectedInteriorTester

1
2
3	/*
4	* Copyright (c) 2016 Vivid Solutions.
5	*
6	* All rights reserved. This program and the accompanying materials
7	* are made available under the terms of the Eclipse Public License 2.0
8	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
9	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
10	* and the Eclipse Distribution License is available at
11	*
12	* http://www.eclipse.org/org/documents/edl-v10.php.
13	*/
14	package org.locationtech.jts.operation.valid;
15
16	import java.util.ArrayList;
17	import java.util.Collection;
18	import java.util.Iterator;
19	import java.util.List;
20
21	import org.locationtech.jts.geom.Coordinate;
22	import org.locationtech.jts.geom.Geometry;
23	import org.locationtech.jts.geom.GeometryFactory;
24	import org.locationtech.jts.geom.LineString;
25	import org.locationtech.jts.geom.Location;
26	import org.locationtech.jts.geom.MultiPolygon;
27	import org.locationtech.jts.geom.Polygon;
28	import org.locationtech.jts.geomgraph.DirectedEdge;
29	import org.locationtech.jts.geomgraph.Edge;
30	import org.locationtech.jts.geomgraph.EdgeRing;
31	import org.locationtech.jts.geomgraph.GeometryGraph;
32	import org.locationtech.jts.geomgraph.PlanarGraph;
33	import org.locationtech.jts.geomgraph.Position;
34	import org.locationtech.jts.operation.overlay.MaximalEdgeRing;
35	import org.locationtech.jts.operation.overlay.OverlayNodeFactory;
36	import org.locationtech.jts.util.Assert;
37
38	/**
39	* This class tests that the interior of an area {@link Geometry}
40	* ( {@link Polygon} or {@link MultiPolygon} )
41	* is connected.
42	* This can happen if:
43	* <ul>
44	* <li>a shell self-intersects
45	* <li>one or more holes form a connected chain touching a shell at two different points
46	* <li>one or more holes form a ring around a subset of the interior
47	* </ul>
48	* If a disconnected situation is found the location of the problem is recorded.
49	*
50	* @version 1.7
51	*/
52	public class ConnectedInteriorTester {
53
54	public static Coordinate findDifferentPoint(Coordinate[] coord, Coordinate pt)
55	{
56	for (int i = 0; i < coord.length; i++) {
57	if (! coord[i].equals(pt))
58	return coord[i];
59	}
60	return null;
61	}
62
63	private GeometryFactory geometryFactory = new GeometryFactory();
64
65	private GeometryGraph geomGraph;
66	// save a coordinate for any disconnected interior found
67	// the coordinate will be somewhere on the ring surrounding the disconnected interior
68	private Coordinate disconnectedRingcoord;
69
70	public ConnectedInteriorTester(GeometryGraph geomGraph)
71	{
72	this.geomGraph = geomGraph;
73	}
74
75	public Coordinate getCoordinate() { return disconnectedRingcoord; }
76
77	public boolean isInteriorsConnected()
78	{
79	// node the edges, in case holes touch the shell
80	List splitEdges = new ArrayList();
81	geomGraph.computeSplitEdges(splitEdges);
82
83	// form the edges into rings
84	PlanarGraph graph = new PlanarGraph(new OverlayNodeFactory());
85	graph.addEdges(splitEdges);
86	setInteriorEdgesInResult(graph);
87	graph.linkResultDirectedEdges();
88	List edgeRings = buildEdgeRings(graph.getEdgeEnds());
89
90	/**
91	* Mark all the edges for the edgeRings corresponding to the shells
92	* of the input polygons. Note only ONE ring gets marked for each shell.
93	*/
94	visitShellInteriors(geomGraph.getGeometry(), graph);
95
96	/**
97	* If there are any unvisited shell edges
98	* (i.e. a ring which is not a hole and which has the interior
99	* of the parent area on the RHS)
100	* this means that one or more holes must have split the interior of the
101	* polygon into at least two pieces. The polygon is thus invalid.
102	*/
103	return ! hasUnvisitedShellEdge(edgeRings);
104	}
105
106	private void setInteriorEdgesInResult(PlanarGraph graph)
107	{
108	for (Iterator it = graph.getEdgeEnds().iterator(); it.hasNext(); ) {
109	DirectedEdge de = (DirectedEdge) it.next();
110	if (de.getLabel().getLocation(0, Position.RIGHT) == Location.INTERIOR) {
111	de.setInResult(true);
112	}
113	}
114	}
115
116	/**
117	* Form DirectedEdges in graph into Minimal EdgeRings.
118	* (Minimal Edgerings must be used, because only they are guaranteed to provide
119	* a correct isHole computation)
120	*/
121	private List buildEdgeRings(Collection dirEdges)
122	{
123	List edgeRings = new ArrayList();
124	for (Iterator it = dirEdges.iterator(); it.hasNext(); ) {
125	DirectedEdge de = (DirectedEdge) it.next();
126	// if this edge has not yet been processed
127	if (de.isInResult()
128	&& de.getEdgeRing() == null) {
129	MaximalEdgeRing er = new MaximalEdgeRing(de, geometryFactory);
130
131	er.linkDirectedEdgesForMinimalEdgeRings();
132	List minEdgeRings = er.buildMinimalRings();
133	edgeRings.addAll(minEdgeRings);
134	}
135	}
136	return edgeRings;
137	}
138
139	/**
140	* Mark all the edges for the edgeRings corresponding to the shells
141	* of the input polygons.
142	* Only ONE ring gets marked for each shell - if there are others which remain unmarked
143	* this indicates a disconnected interior.
144	*/
145	private void visitShellInteriors(Geometry g, PlanarGraph graph)
146	{
147	if (g instanceof Polygon) {
148	Polygon p = (Polygon) g;
149	visitInteriorRing(p.getExteriorRing(), graph);
150	}
151	if (g instanceof MultiPolygon) {
152	MultiPolygon mp = (MultiPolygon) g;
153	for (int i = 0; i < mp.getNumGeometries(); i++) {
154	Polygon p = (Polygon) mp.getGeometryN(i);
155	visitInteriorRing(p.getExteriorRing(), graph);
156	}
157	}
158	}
159
160	private void visitInteriorRing(LineString ring, PlanarGraph graph)
161	{
162	if (ring.isEmpty()) return;
163	Coordinate[] pts = ring.getCoordinates();
164	Coordinate pt0 = pts[0];
165	/**
166	* Find first point in coord list different to initial point.
167	* Need special check since the first point may be repeated.
168	*/
169	Coordinate pt1 = findDifferentPoint(pts, pt0);
170	Edge e = graph.findEdgeInSameDirection(pt0, pt1);
171	DirectedEdge de = (DirectedEdge) graph.findEdgeEnd(e);
172	DirectedEdge intDe = null;
173	if (de.getLabel().getLocation(0, Position.RIGHT) == Location.INTERIOR) {
174	intDe = de;
175	}
176	else if (de.getSym().getLabel().getLocation(0, Position.RIGHT) == Location.INTERIOR) {
177	intDe = de.getSym();
178	}
179	Assert.isTrue(intDe != null, "unable to find dirEdge with Interior on RHS");
180
181	visitLinkedDirectedEdges(intDe);
182	}
183
184	protected void visitLinkedDirectedEdges(DirectedEdge start)
185	{
186	DirectedEdge startDe = start;
187	DirectedEdge de = start;
188	do {
189	Assert.isTrue(de != null, "found null Directed Edge");
190	de.setVisited(true);
191	de = de.getNext();
192	} while (de != startDe);
193	}
194
195	/**
196	* Check if any shell ring has an unvisited edge.
197	* A shell ring is a ring which is not a hole and which has the interior
198	* of the parent area on the RHS.
199	* (Note that there may be non-hole rings with the interior on the LHS,
200	* since the interior of holes will also be polygonized into CW rings
201	* by the linkAllDirectedEdges() step)
202	*
203	* @return true if there is an unvisited edge in a non-hole ring
204	*/
205	private boolean hasUnvisitedShellEdge(List edgeRings)
206	{
207	for (int i = 0; i < edgeRings.size(); i++) {
208	EdgeRing er = (EdgeRing) edgeRings.get(i);
209	// don't check hole rings
210	if (er.isHole())
211	continue;
212	List edges = er.getEdges();
213	DirectedEdge de = (DirectedEdge) edges.get(0);
214	// don't check CW rings which are holes
215	// (MD - this check may now be irrelevant)
216	if (de.getLabel().getLocation(0, Position.RIGHT) != Location.INTERIOR) continue;
217
218	/**
219	* the edgeRing is CW ring which surrounds the INT of the area, so check all
220	* edges have been visited. If any are unvisited, this is a disconnected part of the interior
221	*/
222	for (int j = 0; j < edges.size(); j++) {
223	de = (DirectedEdge) edges.get(j);
224	//Debug.print("visted? "); Debug.println(de);
225	if (! de.isVisited()) {
226	//Debug.print("not visited "); Debug.println(de);
227	disconnectedRingcoord = de.getCoordinate();
228	return true;
229	}
230	}
231	}
232	return false;
233	}
234	}
235