Class IsValidOp

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.Iterator;
17	import java.util.Set;
18	import java.util.TreeSet;
19
20	import org.locationtech.jts.algorithm.LineIntersector;
21	import org.locationtech.jts.algorithm.PointLocation;
22	import org.locationtech.jts.algorithm.RobustLineIntersector;
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.Geometry;
27	import org.locationtech.jts.geom.GeometryCollection;
28	import org.locationtech.jts.geom.LineString;
29	import org.locationtech.jts.geom.LinearRing;
30	import org.locationtech.jts.geom.Location;
31	import org.locationtech.jts.geom.MultiPoint;
32	import org.locationtech.jts.geom.MultiPolygon;
33	import org.locationtech.jts.geom.Point;
34	import org.locationtech.jts.geom.Polygon;
35	import org.locationtech.jts.geomgraph.Edge;
36	import org.locationtech.jts.geomgraph.EdgeIntersection;
37	import org.locationtech.jts.geomgraph.EdgeIntersectionList;
38	import org.locationtech.jts.geomgraph.GeometryGraph;
39	import org.locationtech.jts.util.Assert;
40
41	/**
42	* Implements the algorithms required to compute the <code>isValid()</code> method
43	* for {@link Geometry}s.
44	* See the documentation for the various geometry types for a specification of validity.
45	*
46	* @version 1.7
47	*/
48	public class IsValidOp
49	{
50	/**
51	* Tests whether a {@link Geometry} is valid.
52	* @param geom the Geometry to test
53	* @return true if the geometry is valid
54	*/
55	public static boolean isValid(Geometry geom)
56	{
57	IsValidOp isValidOp = new IsValidOp(geom);
58	return isValidOp.isValid();
59	}
60
61	/**
62	* Checks whether a coordinate is valid for processing.
63	* Coordinates are valid iff their x and y ordinates are in the
64	* range of the floating point representation.
65	*
66	* @param coord the coordinate to validate
67	* @return <code>true</code> if the coordinate is valid
68	*/
69	public static boolean isValid(Coordinate coord)
70	{
71	if (Double.isNaN(coord.x)) return false;
72	if (Double.isInfinite(coord.x)) return false;
73	if (Double.isNaN(coord.y)) return false;
74	if (Double.isInfinite(coord.y)) return false;
75	return true;
76	}
77	/**
78	* Find a point from the list of testCoords
79	* that is NOT a node in the edge for the list of searchCoords
80	*
81	* @return the point found, or <code>null</code> if none found
82	*/
83	public static Coordinate findPtNotNode(
84	Coordinate[] testCoords,
85	LinearRing searchRing,
86	GeometryGraph graph)
87	{
88	// find edge corresponding to searchRing.
89	Edge searchEdge = graph.findEdge(searchRing);
90	// find a point in the testCoords which is not a node of the searchRing
91	EdgeIntersectionList eiList = searchEdge.getEdgeIntersectionList();
92	// somewhat inefficient - is there a better way? (Use a node map, for instance?)
93	for (int i = 0 ; i < testCoords.length; i++) {
94	Coordinate pt = testCoords[i];
95	if (! eiList.isIntersection(pt))
96	return pt;
97	}
98	return null;
99	}
100
101	private Geometry parentGeometry; // the base Geometry to be validated
102	/**
103	* If the following condition is TRUE JTS will validate inverted shells and exverted holes
104	* (the ESRI SDE model)
105	*/
106	private boolean isSelfTouchingRingFormingHoleValid = false;
107	private TopologyValidationError validErr;
108
109	public IsValidOp(Geometry parentGeometry)
110	{
111	this.parentGeometry = parentGeometry;
112	}
113
114	/**
115	* Sets whether polygons using <b>Self-Touching Rings</b> to form
116	* holes are reported as valid.
117	* If this flag is set, the following Self-Touching conditions
118	* are treated as being valid:
119	* <ul>
120	* <li>the shell ring self-touches to create a hole touching the shell
121	* <li>a hole ring self-touches to create two holes touching at a point
122	* </ul>
123	* <p>
124	* The default (following the OGC SFS standard)
125	* is that this condition is <b>not</b> valid (<code>false</code>).
126	* <p>
127	* This does not affect whether Self-Touching Rings
128	* disconnecting the polygon interior are considered valid
129	* (these are considered to be <b>invalid</b> under the SFS, and many other
130	* spatial models as well).
131	* This includes "bow-tie" shells,
132	* which self-touch at a single point causing the interior to
133	* be disconnected,
134	* and "C-shaped" holes which self-touch at a single point causing an island to be formed.
135	*
136	* @param isValid states whether geometry with this condition is valid
137	*/
138	public void setSelfTouchingRingFormingHoleValid(boolean isValid)
139	{
140	isSelfTouchingRingFormingHoleValid = isValid;
141	}
142
143	/**
144	* Computes the validity of the geometry,
145	* and returns <tt>true</tt> if it is valid.
146	*
147	* @return true if the geometry is valid
148	*/
149	public boolean isValid()
150	{
151	checkValid(parentGeometry);
152	return validErr == null;
153	}
154
155	/**
156	* Computes the validity of the geometry,
157	* and if not valid returns the validation error for the geometry,
158	* or null if the geometry is valid.
159	*
160	* @return the validation error, if the geometry is invalid
161	* or null if the geometry is valid
162	*/
163	public TopologyValidationError getValidationError()
164	{
165	checkValid(parentGeometry);
166	return validErr;
167	}
168
169	private void checkValid(Geometry g)
170	{
171	validErr = null;
172
173	// empty geometries are always valid!
174	if (g.isEmpty()) return;
175
176	if (g instanceof Point) checkValid((Point) g);
177	else if (g instanceof MultiPoint) checkValid((MultiPoint) g);
178	// LineString also handles LinearRings
179	else if (g instanceof LinearRing) checkValid( (LinearRing) g);
180	else if (g instanceof LineString) checkValid( (LineString) g);
181	else if (g instanceof Polygon) checkValid( (Polygon) g);
182	else if (g instanceof MultiPolygon) checkValid( (MultiPolygon) g);
183	else if (g instanceof GeometryCollection) checkValid( (GeometryCollection) g);
184	else throw new UnsupportedOperationException(g.getClass().getName());
185	}
186
187	/**
188	* Checks validity of a Point.
189	*/
190	private void checkValid(Point g)
191	{
192	checkInvalidCoordinates(g.getCoordinates());
193	}
194	/**
195	* Checks validity of a MultiPoint.
196	*/
197	private void checkValid(MultiPoint g)
198	{
199	checkInvalidCoordinates(g.getCoordinates());
200	}
201
202	/**
203	* Checks validity of a LineString. Almost anything goes for linestrings!
204	*/
205	private void checkValid(LineString g)
206	{
207	checkInvalidCoordinates(g.getCoordinates());
208	if (validErr != null) return;
209	GeometryGraph graph = new GeometryGraph(0, g);
210	checkTooFewPoints(graph);
211	}
212	/**
213	* Checks validity of a LinearRing.
214	*/
215	private void checkValid(LinearRing g)
216	{
217	checkInvalidCoordinates(g.getCoordinates());
218	if (validErr != null) return;
219	checkClosedRing(g);
220	if (validErr != null) return;
221
222	GeometryGraph graph = new GeometryGraph(0, g);
223	checkTooFewPoints(graph);
224	if (validErr != null) return;
225
226	LineIntersector li = new RobustLineIntersector();
227	graph.computeSelfNodes(li, true, true);
228	checkNoSelfIntersectingRings(graph);
229	}
230
231	/**
232	* Checks the validity of a polygon.
233	* Sets the validErr flag.
234	*/
235	private void checkValid(Polygon g)
236	{
237	checkInvalidCoordinates(g);
238	if (validErr != null) return;
239	checkClosedRings(g);
240	if (validErr != null) return;
241
242	GeometryGraph graph = new GeometryGraph(0, g);
243
244	checkTooFewPoints(graph);
245	if (validErr != null) return;
246	checkConsistentArea(graph);
247	if (validErr != null) return;
248
249	if (! isSelfTouchingRingFormingHoleValid) {
250	checkNoSelfIntersectingRings(graph);
251	if (validErr != null) return;
252	}
253	checkHolesInShell(g, graph);
254	if (validErr != null) return;
255	//SLOWcheckHolesNotNested(g);
256	checkHolesNotNested(g, graph);
257	if (validErr != null) return;
258	checkConnectedInteriors(graph);
259	}
260
261	private void checkValid(MultiPolygon g)
262	{
263	for (int i = 0; i < g.getNumGeometries(); i++) {
264	Polygon p = (Polygon) g.getGeometryN(i);
265	checkInvalidCoordinates(p);
266	if (validErr != null) return;
267	checkClosedRings(p);
268	if (validErr != null) return;
269	}
270
271	GeometryGraph graph = new GeometryGraph(0, g);
272
273	checkTooFewPoints(graph);
274	if (validErr != null) return;
275	checkConsistentArea(graph);
276	if (validErr != null) return;
277	if (! isSelfTouchingRingFormingHoleValid) {
278	checkNoSelfIntersectingRings(graph);
279	if (validErr != null) return;
280	}
281	for (int i = 0; i < g.getNumGeometries(); i++) {
282	Polygon p = (Polygon) g.getGeometryN(i);
283	checkHolesInShell(p, graph);
284	if (validErr != null) return;
285	}
286	for (int i = 0; i < g.getNumGeometries(); i++) {
287	Polygon p = (Polygon) g.getGeometryN(i);
288	checkHolesNotNested(p, graph);
289	if (validErr != null) return;
290	}
291	checkShellsNotNested(g, graph);
292	if (validErr != null) return;
293	checkConnectedInteriors(graph);
294	}
295
296	private void checkValid(GeometryCollection gc)
297	{
298	for (int i = 0; i < gc.getNumGeometries(); i++) {
299	Geometry g = gc.getGeometryN(i);
300	checkValid(g);
301	if (validErr != null) return;
302	}
303	}
304
305	private void checkInvalidCoordinates(Coordinate[] coords)
306	{
307	for (int i = 0; i < coords.length; i++) {
308	if (! isValid(coords[i])) {
309	validErr = new TopologyValidationError(
310	TopologyValidationError.INVALID_COORDINATE,
311	coords[i]);
312	return;
313	}
314	}
315	}
316
317	private void checkInvalidCoordinates(Polygon poly)
318	{
319	checkInvalidCoordinates(poly.getExteriorRing().getCoordinates());
320	if (validErr != null) return;
321	for (int i = 0; i < poly.getNumInteriorRing(); i++) {
322	checkInvalidCoordinates(poly.getInteriorRingN(i).getCoordinates());
323	if (validErr != null) return;
324	}
325	}
326
327	private void checkClosedRings(Polygon poly)
328	{
329	checkClosedRing(poly.getExteriorRing());
330	if (validErr != null) return;
331	for (int i = 0; i < poly.getNumInteriorRing(); i++) {
332	checkClosedRing(poly.getInteriorRingN(i));
333	if (validErr != null) return;
334	}
335	}
336
337	private void checkClosedRing(LinearRing ring)
338	{
339	if (ring.isEmpty()) return;
340	if (! ring.isClosed() ) {
341	Coordinate pt = null;
342	if (ring.getNumPoints() >= 1)
343	pt = ring.getCoordinateN(0);
344	validErr = new TopologyValidationError(
345	TopologyValidationError.RING_NOT_CLOSED,
346	pt);
347	}
348	}
349
350	private void checkTooFewPoints(GeometryGraph graph)
351	{
352	if (graph.hasTooFewPoints()) {
353	validErr = new TopologyValidationError(
354	TopologyValidationError.TOO_FEW_POINTS,
355	graph.getInvalidPoint());
356	return;
357	}
358	}
359
360	/**
361	* Checks that the arrangement of edges in a polygonal geometry graph
362	* forms a consistent area.
363	*
364	* @param graph
365	*
366	* @see ConsistentAreaTester
367	*/
368	private void checkConsistentArea(GeometryGraph graph)
369	{
370	ConsistentAreaTester cat = new ConsistentAreaTester(graph);
371	boolean isValidArea = cat.isNodeConsistentArea();
372	if (! isValidArea) {
373	validErr = new TopologyValidationError(
374	TopologyValidationError.SELF_INTERSECTION,
375	cat.getInvalidPoint());
376	return;
377	}
378	if (cat.hasDuplicateRings()) {
379	validErr = new TopologyValidationError(
380	TopologyValidationError.DUPLICATE_RINGS,
381	cat.getInvalidPoint());
382	}
383	}
384
385	/**
386	* Check that there is no ring which self-intersects (except of course at its endpoints).
387	* This is required by OGC topology rules (but not by other models
388	* such as ESRI SDE, which allow inverted shells and exverted holes).
389	*
390	* @param graph the topology graph of the geometry
391	*/
392	private void checkNoSelfIntersectingRings(GeometryGraph graph)
393	{
394	for (Iterator i = graph.getEdgeIterator(); i.hasNext(); ) {
395	Edge e = (Edge) i.next();
396	checkNoSelfIntersectingRing(e.getEdgeIntersectionList());
397	if (validErr != null)
398	return;
399	}
400	}
401
402	/**
403	* Check that a ring does not self-intersect, except at its endpoints.
404	* Algorithm is to count the number of times each node along edge occurs.
405	* If any occur more than once, that must be a self-intersection.
406	*/
407	private void checkNoSelfIntersectingRing(EdgeIntersectionList eiList)
408	{
409	Set nodeSet = new TreeSet();
410	boolean isFirst = true;
411	for (Iterator i = eiList.iterator(); i.hasNext(); ) {
412	EdgeIntersection ei = (EdgeIntersection) i.next();
413	if (isFirst) {
414	isFirst = false;
415	continue;
416	}
417	if (nodeSet.contains(ei.coord)) {
418	validErr = new TopologyValidationError(
419	TopologyValidationError.RING_SELF_INTERSECTION,
420	ei.coord);
421	return;
422	}
423	else {
424	nodeSet.add(ei.coord);
425	}
426	}
427	}
428
429	/**
430	* Tests that each hole is inside the polygon shell.
431	* This routine assumes that the holes have previously been tested
432	* to ensure that all vertices lie on the shell or on the same side of it
433	* (i.e. that the hole rings do not cross the shell ring).
434	* In other words, this test is only correct if the ConsistentArea test is passed first.
435	* Given this, a simple point-in-polygon test of a single point in the hole can be used,
436	* provided the point is chosen such that it does not lie on the shell.
437	*
438	* @param p the polygon to be tested for hole inclusion
439	* @param graph a GeometryGraph incorporating the polygon
440	*/
441	private void checkHolesInShell(Polygon p, GeometryGraph graph)
442	{
443	// skip test if no holes are present
444	if (p.getNumInteriorRing() <= 0) return;
445
446	LinearRing shell = p.getExteriorRing();
447	boolean isShellEmpty = shell.isEmpty();
448	//PointInRing pir = new SimplePointInRing(shell); // testing only
449	PointOnGeometryLocator pir = new IndexedPointInAreaLocator(shell);
450
451	for (int i = 0; i < p.getNumInteriorRing(); i++) {
452
453	LinearRing hole = p.getInteriorRingN(i);
454	Coordinate holePt = null;
455	if (hole.isEmpty()) continue;
456	holePt = findPtNotNode(hole.getCoordinates(), shell, graph);
457	/**
458	* If no non-node hole vertex can be found, the hole must
459	* split the polygon into disconnected interiors.
460	* This will be caught by a subsequent check.
461	*/
462	if (holePt == null) return;
463
464	boolean outside = isShellEmpty \|\| (Location.EXTERIOR == pir.locate(holePt));
465	if ( outside ) {
466	validErr = new TopologyValidationError(
467	TopologyValidationError.HOLE_OUTSIDE_SHELL,
468	holePt);
469	return;
470	}
471	}
472	}
473
474	/**
475	* Tests that no hole is nested inside another hole.
476	* This routine assumes that the holes are disjoint.
477	* To ensure this, holes have previously been tested
478	* to ensure that:
479	* <ul>
480	* <li>they do not partially overlap
481	* (checked by <code>checkRelateConsistency</code>)
482	* <li>they are not identical
483	* (checked by <code>checkRelateConsistency</code>)
484	* </ul>
485	*/
486	private void checkHolesNotNested(Polygon p, GeometryGraph graph)
487	{
488	// skip test if no holes are present
489	if (p.getNumInteriorRing() <= 0) return;
490
491	IndexedNestedRingTester nestedTester = new IndexedNestedRingTester(graph);
492	//SimpleNestedRingTester nestedTester = new SimpleNestedRingTester(arg[0]);
493	//SweeplineNestedRingTester nestedTester = new SweeplineNestedRingTester(arg[0]);
494
495	for (int i = 0; i < p.getNumInteriorRing(); i++) {
496	LinearRing innerHole = p.getInteriorRingN(i);
497	if (innerHole.isEmpty()) continue;
498	nestedTester.add(innerHole);
499	}
500	boolean isNonNested = nestedTester.isNonNested();
501	if ( ! isNonNested ) {
502	validErr = new TopologyValidationError(
503	TopologyValidationError.NESTED_HOLES,
504	nestedTester.getNestedPoint());
505	}
506	}
507
508	/**
509	* Tests that no element polygon is wholly in the interior of another element polygon.
510	* <p>
511	* Preconditions:
512	* <ul>
513	* <li>shells do not partially overlap
514	* <li>shells do not touch along an edge
515	* <li>no duplicate rings exist
516	* </ul>
517	* This routine relies on the fact that while polygon shells may touch at one or
518	* more vertices, they cannot touch at ALL vertices.
519	*/
520	private void checkShellsNotNested(MultiPolygon mp, GeometryGraph graph)
521	{
522	for (int i = 0; i < mp.getNumGeometries(); i++) {
523	Polygon p = (Polygon) mp.getGeometryN(i);
524	LinearRing shell = p.getExteriorRing();
525	for (int j = 0; j < mp.getNumGeometries(); j++) {
526	if (i == j) continue;
527	Polygon p2 = (Polygon) mp.getGeometryN(j);
528	checkShellNotNested(shell, p2, graph);
529	if (validErr != null) return;
530	}
531	}
532	}
533
534	/**
535	* Check if a shell is incorrectly nested within a polygon. This is the case
536	* if the shell is inside the polygon shell, but not inside a polygon hole.
537	* (If the shell is inside a polygon hole, the nesting is valid.)
538	* <p>
539	* The algorithm used relies on the fact that the rings must be properly contained.
540	* E.g. they cannot partially overlap (this has been previously checked by
541	* <code>checkRelateConsistency</code> )
542	*/
543	private void checkShellNotNested(LinearRing shell, Polygon p, GeometryGraph graph)
544	{
545	Coordinate[] shellPts = shell.getCoordinates();
546	// test if shell is inside polygon shell
547	LinearRing polyShell = p.getExteriorRing();
548	if (polyShell.isEmpty()) return;
549	Coordinate[] polyPts = polyShell.getCoordinates();
550	Coordinate shellPt = findPtNotNode(shellPts, polyShell, graph);
551	// if no point could be found, we can assume that the shell is outside the polygon
552	if (shellPt == null)
553	return;
554	boolean insidePolyShell = PointLocation.isInRing(shellPt, polyPts);
555	if (! insidePolyShell) return;
556
557	// if no holes, this is an error!
558	if (p.getNumInteriorRing() <= 0) {
559	validErr = new TopologyValidationError(
560	TopologyValidationError.NESTED_SHELLS,
561	shellPt);
562	return;
563	}
564
565	/**
566	* Check if the shell is inside one of the holes.
567	* This is the case if one of the calls to checkShellInsideHole
568	* returns a null coordinate.
569	* Otherwise, the shell is not properly contained in a hole, which is an error.
570	*/
571	Coordinate badNestedPt = null;
572	for (int i = 0; i < p.getNumInteriorRing(); i++) {
573	LinearRing hole = p.getInteriorRingN(i);
574	badNestedPt = checkShellInsideHole(shell, hole, graph);
575	if (badNestedPt == null)
576	return;
577	}
578	validErr = new TopologyValidationError(
579	TopologyValidationError.NESTED_SHELLS,
580	badNestedPt);
581	}
582
583	/**
584	* This routine checks to see if a shell is properly contained in a hole.
585	* It assumes that the edges of the shell and hole do not
586	* properly intersect.
587	*
588	* @return <code>null</code> if the shell is properly contained, or
589	* a Coordinate which is not inside the hole if it is not
590	*
591	*/
592	private Coordinate checkShellInsideHole(LinearRing shell, LinearRing hole, GeometryGraph graph)
593	{
594	Coordinate[] shellPts = shell.getCoordinates();
595	Coordinate[] holePts = hole.getCoordinates();
596	// TODO: improve performance of this - by sorting pointlists for instance?
597	Coordinate shellPt = findPtNotNode(shellPts, hole, graph);
598	// if point is on shell but not hole, check that the shell is inside the hole
599	if (shellPt != null) {
600	boolean insideHole = PointLocation.isInRing(shellPt, holePts);
601	if (! insideHole) {
602	return shellPt;
603	}
604	}
605	Coordinate holePt = findPtNotNode(holePts, shell, graph);
606	// if point is on hole but not shell, check that the hole is outside the shell
607	if (holePt != null) {
608	boolean insideShell = PointLocation.isInRing(holePt, shellPts);
609	if (insideShell) {
610	return holePt;
611	}
612	return null;
613	}
614	Assert.shouldNeverReachHere("points in shell and hole appear to be equal");
615	return null;
616	}
617
618	private void checkConnectedInteriors(GeometryGraph graph)
619	{
620	ConnectedInteriorTester cit = new ConnectedInteriorTester(graph);
621	if (! cit.isInteriorsConnected())
622	validErr = new TopologyValidationError(
623	TopologyValidationError.DISCONNECTED_INTERIOR,
624	cit.getCoordinate());
625	}
626
627	}
628