Class IsSimpleOp

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;
15
16	import java.util.Iterator;
17	import java.util.List;
18	import java.util.Map;
19	import java.util.Set;
20	import java.util.TreeMap;
21	import java.util.TreeSet;
22
23	import org.locationtech.jts.algorithm.BoundaryNodeRule;
24	import org.locationtech.jts.algorithm.LineIntersector;
25	import org.locationtech.jts.algorithm.RobustLineIntersector;
26	import org.locationtech.jts.geom.Coordinate;
27	import org.locationtech.jts.geom.Geometry;
28	import org.locationtech.jts.geom.GeometryCollection;
29	import org.locationtech.jts.geom.LineString;
30	import org.locationtech.jts.geom.Lineal;
31	import org.locationtech.jts.geom.LinearRing;
32	import org.locationtech.jts.geom.MultiLineString;
33	import org.locationtech.jts.geom.MultiPoint;
34	import org.locationtech.jts.geom.Point;
35	import org.locationtech.jts.geom.Polygonal;
36	import org.locationtech.jts.geom.util.LinearComponentExtracter;
37	import org.locationtech.jts.geomgraph.Edge;
38	import org.locationtech.jts.geomgraph.EdgeIntersection;
39	import org.locationtech.jts.geomgraph.GeometryGraph;
40	import org.locationtech.jts.geomgraph.index.SegmentIntersector;
41
42	/**
43	* Tests whether a <code>Geometry</code> is simple.
44	* In general, the SFS specification of simplicity
45	* follows the rule:
46	* <ul>
47	* <li> A Geometry is simple if and only if the only self-intersections are at
48	* boundary points.
49	* </ul>
50	* <p>
51	* Simplicity is defined for each {@link Geometry} type as follows:
52	* <ul>
53	* <li><b>Polygonal</b> geometries are simple by definition, so
54	* <code>isSimple</code> trivially returns true.
55	* (Note: this means that <tt>isSimple</tt> cannot be used to test
56	* for (invalid) self-intersections in <tt>Polygon</tt>s.
57	* In order to check if a <tt>Polygonal</tt> geometry has self-intersections,
58	* use {@link Geometry#isValid()}).
59	* <li><b>Linear</b> geometries are simple iff they do <i>not</i> self-intersect at interior points
60	* (i.e. points other than boundary points).
61	* This is equivalent to saying that no two linear components satisfy the SFS {@link Geometry#touches(Geometry)}
62	* predicate.
63	* <li><b>Zero-dimensional (point)</b> geometries are simple if and only if they have no
64	* repeated points.
65	* <li><b>Empty</b> geometries are <i>always</i> simple, by definition
66	* </ul>
67	* For {@link Lineal} geometries the evaluation of simplicity
68	* can be customized by supplying a {@link BoundaryNodeRule}
69	* to define how boundary points are determined.
70	* The default is the SFS-standard {@link BoundaryNodeRule#MOD2_BOUNDARY_RULE}.
71	* Note that under the <tt>Mod-2</tt> rule, closed <tt>LineString</tt>s (rings)
72	* will never satisfy the <tt>touches</tt> predicate at their endpoints, since these are
73	* interior points, not boundary points.
74	* If it is required to test whether a set of <code>LineString</code>s touch
75	* only at their endpoints, use <code>IsSimpleOp</code> with {@link BoundaryNodeRule#ENDPOINT_BOUNDARY_RULE}.
76	* For example, this can be used to validate that a set of lines form a topologically valid
77	* linear network.
78	*
79	* @see BoundaryNodeRule
80	*
81	* @version 1.7
82	*/
83	public class IsSimpleOp
84	{
85	private Geometry inputGeom;
86	private boolean isClosedEndpointsInInterior = true;
87	private Coordinate nonSimpleLocation = null;
88
89	/**
90	* Creates a simplicity checker using the default SFS Mod-2 Boundary Node Rule
91	*
92	* @deprecated use IsSimpleOp(Geometry)
93	*/
94	public IsSimpleOp() {
95	}
96
97	/**
98	* Creates a simplicity checker using the default SFS Mod-2 Boundary Node Rule
99	*
100	* @param geom the geometry to test
101	*/
102	public IsSimpleOp(Geometry geom) {
103	this.inputGeom = geom;
104	}
105
106	/**
107	* Creates a simplicity checker using a given {@link BoundaryNodeRule}
108	*
109	* @param geom the geometry to test
110	* @param boundaryNodeRule the rule to use.
111	*/
112	public IsSimpleOp(Geometry geom, BoundaryNodeRule boundaryNodeRule)
113	{
114	this.inputGeom = geom;
115	isClosedEndpointsInInterior = ! boundaryNodeRule.isInBoundary(2);
116	}
117
118	/**
119	* Tests whether the geometry is simple.
120	*
121	* @return true if the geometry is simple
122	*/
123	public boolean isSimple()
124	{
125	nonSimpleLocation = null;
126	return computeSimple(inputGeom);
127	}
128
129	private boolean computeSimple(Geometry geom)
130	{
131	nonSimpleLocation = null;
132	if (geom.isEmpty()) return true;
133	if (geom instanceof LineString) return isSimpleLinearGeometry(geom);
134	if (geom instanceof MultiLineString) return isSimpleLinearGeometry(geom);
135	if (geom instanceof MultiPoint) return isSimpleMultiPoint((MultiPoint) geom);
136	if (geom instanceof Polygonal) return isSimplePolygonal(geom);
137	if (geom instanceof GeometryCollection) return isSimpleGeometryCollection(geom);
138	// all other geometry types are simple by definition
139	return true;
140	}
141
142	/**
143	* Gets a coordinate for the location where the geometry
144	* fails to be simple.
145	* (i.e. where it has a non-boundary self-intersection).
146	* {@link #isSimple} must be called before this method is called.
147	*
148	* @return a coordinate for the location of the non-boundary self-intersection
149	* or null if the geometry is simple
150	*/
151	public Coordinate getNonSimpleLocation()
152	{
153	return nonSimpleLocation;
154	}
155
156	/**
157	* Reports whether a {@link LineString} is simple.
158	*
159	* @param geom the lineal geometry to test
160	* @return true if the geometry is simple
161	* @deprecated use isSimple()
162	*/
163	public boolean isSimple(LineString geom)
164	{
165	return isSimpleLinearGeometry(geom);
166	}
167
168	/**
169	* Reports whether a {@link MultiLineString} geometry is simple.
170	*
171	* @param geom the lineal geometry to test
172	* @return true if the geometry is simple
173	* @deprecated use isSimple()
174	*/
175	public boolean isSimple(MultiLineString geom)
176	{
177	return isSimpleLinearGeometry(geom);
178	}
179
180	/**
181	* A MultiPoint is simple iff it has no repeated points
182	* @deprecated use isSimple()
183	*/
184	public boolean isSimple(MultiPoint mp)
185	{
186	return isSimpleMultiPoint(mp);
187	}
188
189	private boolean isSimpleMultiPoint(MultiPoint mp)
190	{
191	if (mp.isEmpty()) return true;
192	Set points = new TreeSet();
193	for (int i = 0; i < mp.getNumGeometries(); i++) {
194	Point pt = (Point) mp.getGeometryN(i);
195	Coordinate p = pt.getCoordinate();
196	if (points.contains(p)) {
197	nonSimpleLocation = p;
198	return false;
199	}
200	points.add(p);
201	}
202	return true;
203	}
204
205	/**
206	* Computes simplicity for polygonal geometries.
207	* Polygonal geometries are simple if and only if
208	* all of their component rings are simple.
209	*
210	* @param geom a Polygonal geometry
211	* @return true if the geometry is simple
212	*/
213	private boolean isSimplePolygonal(Geometry geom)
214	{
215	List rings = LinearComponentExtracter.getLines(geom);
216	for (Iterator i = rings.iterator(); i.hasNext(); ) {
217	LinearRing ring = (LinearRing) i.next();
218	if (! isSimpleLinearGeometry(ring))
219	return false;
220	}
221	return true;
222	}
223
224	/**
225	* Semantics for GeometryCollection is
226	* simple iff all components are simple.
227	*
228	* @param geom
229	* @return true if the geometry is simple
230	*/
231	private boolean isSimpleGeometryCollection(Geometry geom)
232	{
233	for (int i = 0; i < geom.getNumGeometries(); i++ ) {
234	Geometry comp = geom.getGeometryN(i);
235	if (! computeSimple(comp))
236	return false;
237	}
238	return true;
239	}
240
241	private boolean isSimpleLinearGeometry(Geometry geom)
242	{
243	if (geom.isEmpty()) return true;
244	GeometryGraph graph = new GeometryGraph(0, geom);
245	LineIntersector li = new RobustLineIntersector();
246	SegmentIntersector si = graph.computeSelfNodes(li, true);
247	// if no self-intersection, must be simple
248	if (! si.hasIntersection()) return true;
249	if (si.hasProperIntersection()) {
250	nonSimpleLocation = si.getProperIntersectionPoint();
251	return false;
252	}
253	if (hasNonEndpointIntersection(graph)) return false;
254	if (isClosedEndpointsInInterior) {
255	if (hasClosedEndpointIntersection(graph)) return false;
256	}
257	return true;
258	}
259
260	/**
261	* For all edges, check if there are any intersections which are NOT at an endpoint.
262	* The Geometry is not simple if there are intersections not at endpoints.
263	*/
264	private boolean hasNonEndpointIntersection(GeometryGraph graph)
265	{
266	for (Iterator i = graph.getEdgeIterator(); i.hasNext(); ) {
267	Edge e = (Edge) i.next();
268	int maxSegmentIndex = e.getMaximumSegmentIndex();
269	for (Iterator eiIt = e.getEdgeIntersectionList().iterator(); eiIt.hasNext(); ) {
270	EdgeIntersection ei = (EdgeIntersection) eiIt.next();
271	if (! ei.isEndPoint(maxSegmentIndex)) {
272	nonSimpleLocation = ei.getCoordinate();
273	return true;
274	}
275	}
276	}
277	return false;
278	}
279
280	private static class EndpointInfo {
281	Coordinate pt;
282	boolean isClosed;
283	int degree;
284
285	public EndpointInfo(Coordinate pt)
286	{
287	this.pt = pt;
288	isClosed = false;
289	degree = 0;
290	}
291
292	public Coordinate getCoordinate() { return pt; }
293
294	public void addEndpoint(boolean isClosed)
295	{
296	degree++;
297	this.isClosed \|= isClosed;
298	}
299	}
300
301	/**
302	* Tests that no edge intersection is the endpoint of a closed line.
303	* This ensures that closed lines are not touched at their endpoint,
304	* which is an interior point according to the Mod-2 rule
305	* To check this we compute the degree of each endpoint.
306	* The degree of endpoints of closed lines
307	* must be exactly 2.
308	*/
309	private boolean hasClosedEndpointIntersection(GeometryGraph graph)
310	{
311	Map endPoints = new TreeMap();
312	for (Iterator i = graph.getEdgeIterator(); i.hasNext(); ) {
313	Edge e = (Edge) i.next();
314	boolean isClosed = e.isClosed();
315	Coordinate p0 = e.getCoordinate(0);
316	addEndpoint(endPoints, p0, isClosed);
317	Coordinate p1 = e.getCoordinate(e.getNumPoints() - 1);
318	addEndpoint(endPoints, p1, isClosed);
319	}
320
321	for (Iterator i = endPoints.values().iterator(); i.hasNext(); ) {
322	EndpointInfo eiInfo = (EndpointInfo) i.next();
323	if (eiInfo.isClosed && eiInfo.degree != 2) {
324	nonSimpleLocation = eiInfo.getCoordinate();
325	return true;
326	}
327	}
328	return false;
329	}
330
331	/**
332	* Add an endpoint to the map, creating an entry for it if none exists
333	*/
334	private void addEndpoint(Map endPoints, Coordinate p, boolean isClosed)
335	{
336	EndpointInfo eiInfo = (EndpointInfo) endPoints.get(p);
337	if (eiInfo == null) {
338	eiInfo = new EndpointInfo(p);
339	endPoints.put(p, eiInfo);
340	}
341	eiInfo.addEndpoint(isClosed);
342	}
343
344	}
345