4
* The JTS Topology Suite is a collection of Java classes that
5
* implement the fundamental operations required to validate a given
6
* geo-spatial data set to a known topological specification.
8
* Copyright (C) 2001 Vivid Solutions
10
* This library is free software; you can redistribute it and/or
11
* modify it under the terms of the GNU Lesser General Public
12
* License as published by the Free Software Foundation; either
13
* version 2.1 of the License, or (at your option) any later version.
15
* This library is distributed in the hope that it will be useful,
16
* but WITHOUT ANY WARRANTY; without even the implied warranty of
17
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18
* Lesser General Public License for more details.
20
* You should have received a copy of the GNU Lesser General Public
21
* License along with this library; if not, write to the Free Software
22
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24
* For more information, contact:
28
* 2328 Government Street
33
* www.vividsolutions.com
35
package com.vividsolutions.jts.operation.valid;
38
import com.vividsolutions.jts.algorithm.*;
39
import com.vividsolutions.jts.geomgraph.*;
40
import com.vividsolutions.jts.operation.overlay.*;
41
import com.vividsolutions.jts.geom.*;
42
import com.vividsolutions.jts.util.*;
45
* This class tests that the interior of an area {@link Geometry}
46
* ({@link Polygon} or {@link MultiPolygon} )
47
* is connected. An area Geometry is invalid if the interior is disconnected.
50
* <li>one or more holes either form a chain touching the shell at two places
51
* <li>one or more holes form a ring around a portion of the interior
53
* If an inconsistency if found the location of the problem
58
public class ConnectedInteriorTester {
60
public static Coordinate findDifferentPoint(Coordinate[] coord, Coordinate pt)
62
for (int i = 0; i < coord.length; i++) {
63
if (! coord[i].equals(pt))
69
private GeometryFactory geometryFactory = new GeometryFactory();
70
private CGAlgorithms cga = new CGAlgorithms();
72
private GeometryGraph geomGraph;
73
// save a coordinate for any disconnected interior found
74
// the coordinate will be somewhere on the ring surrounding the disconnected interior
75
private Coordinate disconnectedRingcoord;
77
public ConnectedInteriorTester(GeometryGraph geomGraph)
79
this.geomGraph = geomGraph;
82
public Coordinate getCoordinate() { return disconnectedRingcoord; }
84
public boolean isInteriorsConnected()
86
// node the edges, in case holes touch the shell
87
List splitEdges = new ArrayList();
88
geomGraph.computeSplitEdges(splitEdges);
90
// polygonize the edges
91
PlanarGraph graph = new PlanarGraph(new OverlayNodeFactory());
92
graph.addEdges(splitEdges);
93
setAllEdgesInResult(graph);
94
graph.linkAllDirectedEdges();
95
List edgeRings = buildEdgeRings(graph.getEdgeEnds());
98
* Mark all the edges for the edgeRings corresponding to the shells
99
* of the input polygons. Note only ONE ring gets marked for each shell.
101
visitShellInteriors(geomGraph.getGeometry(), graph);
104
* If there are any unvisited shell edges
105
* (i.e. a ring which is not a hole and which has the interior
106
* of the parent area on the RHS)
107
* this means that one or more holes must have split the interior of the
108
* polygon into at least two pieces. The polygon is thus invalid.
110
return ! hasUnvisitedShellEdge(edgeRings);
113
private void setAllEdgesInResult(PlanarGraph graph)
115
for (Iterator it = graph.getEdgeEnds().iterator(); it.hasNext(); ) {
116
DirectedEdge de = (DirectedEdge) it.next();
117
de.setInResult(true);
122
* for all DirectedEdges in result, form them into EdgeRings
124
private List buildEdgeRings(Collection dirEdges)
126
List edgeRings = new ArrayList();
127
for (Iterator it = dirEdges.iterator(); it.hasNext(); ) {
128
DirectedEdge de = (DirectedEdge) it.next();
129
// if this edge has not yet been processed
130
if (de.getEdgeRing() == null) {
131
EdgeRing er = new MaximalEdgeRing(de, geometryFactory, cga);
139
* Mark all the edges for the edgeRings corresponding to the shells
140
* of the input polygons. Note only ONE ring gets marked for each shell.
142
private void visitShellInteriors(Geometry g, PlanarGraph graph)
144
if (g instanceof Polygon) {
145
Polygon p = (Polygon) g;
146
visitInteriorRing(p.getExteriorRing(), graph);
148
if (g instanceof MultiPolygon) {
149
MultiPolygon mp = (MultiPolygon) g;
150
for (int i = 0; i < mp.getNumGeometries(); i++) {
151
Polygon p = (Polygon) mp.getGeometryN(i);
152
visitInteriorRing(p.getExteriorRing(), graph);
157
private void visitInteriorRing(LineString ring, PlanarGraph graph)
159
Coordinate[] pts = ring.getCoordinates();
160
Coordinate pt0 = pts[0];
162
* Find first point in coord list different to initial point.
163
* Need special check since the first point may be repeated.
165
Coordinate pt1 = findDifferentPoint(pts, pt0);
166
Edge e = graph.findEdgeInSameDirection(pt0, pt1);
167
DirectedEdge de = (DirectedEdge) graph.findEdgeEnd(e);
168
DirectedEdge intDe = null;
169
if (de.getLabel().getLocation(0, Position.RIGHT) == Location.INTERIOR) {
172
else if (de.getSym().getLabel().getLocation(0, Position.RIGHT) == Location.INTERIOR) {
175
Assert.isTrue(intDe != null, "unable to find dirEdge with Interior on RHS");
177
visitLinkedDirectedEdges(intDe);
179
protected void visitLinkedDirectedEdges(DirectedEdge start)
181
DirectedEdge startDe = start;
182
DirectedEdge de = start;
185
Assert.isTrue(de != null, "found null Directed Edge");
189
} while (de != startDe);
193
* Check if any shell ring has an unvisited edge.
194
* A shell ring is a ring which is not a hole and which has the interior
195
* of the parent area on the RHS.
196
* (Note that there may be non-hole rings with the interior on the LHS,
197
* since the interior of holes will also be polygonized into CW rings
198
* by the linkAllDirectedEdges() step)
200
* @return true if there is an unvisited edge in a non-hole ring
202
private boolean hasUnvisitedShellEdge(List edgeRings)
204
for (int i = 0; i < edgeRings.size(); i++) {
205
EdgeRing er = (EdgeRing) edgeRings.get(i);
206
if (er.isHole()) continue;
207
List edges = er.getEdges();
208
DirectedEdge de = (DirectedEdge) edges.get(0);
209
// don't check CW rings which are holes
210
if (de.getLabel().getLocation(0, Position.RIGHT) != Location.INTERIOR) continue;
212
// must have a CW ring which surrounds the INT of the area, so check all
213
// edges have been visited
214
for (int j = 0; j < edges.size(); j++) {
215
de = (DirectedEdge) edges.get(j);
216
//Debug.print("visted? "); Debug.println(de);
217
if (! de.isVisited()) {
218
//Debug.print("not visited "); Debug.println(de);
219
disconnectedRingcoord = de.getCoordinate();