Doc Classic

Class NodingValidator

  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 package org.locationtech.jts.noding;
 14  
 15 import java.util.Collection;
 16 import java.util.Iterator;
 17  
 18 import org.locationtech.jts.algorithm.LineIntersector;
 19 import org.locationtech.jts.algorithm.RobustLineIntersector;
 20 import org.locationtech.jts.geom.Coordinate;
 21 import org.locationtech.jts.geom.GeometryFactory;
 22 import org.locationtech.jts.util.Debug;
 23  
 24 /**
 25  * Validates that a collection of {@link SegmentString}s is correctly noded.
 26  * Throws an appropriate exception if an noding error is found.
 27  *
 28  * @version 1.7
 29  */
 30 public class NodingValidator {
 31  
 32   private LineIntersector li = new RobustLineIntersector();
 33  
 34   private Collection segStrings;
 35   
 36   private static final GeometryFactory fact = new GeometryFactory();
 37  
 38   public NodingValidator(Collection segStrings)
 39   {
 40     this.segStrings = segStrings;
 41   }
 42  
 43   public void checkValid()
 44   {
 45       // MD - is this call required?  Or could it be done in the Interior Intersection code?
 46     checkEndPtVertexIntersections();
 47     checkInteriorIntersections();
 48     checkCollapses();
 49   }
 50  
 51   /**
 52    * Checks if a segment string contains a segment pattern a-b-a (which implies a self-intersection)
 53    */
 54   private void checkCollapses()
 55   {
 56     for (Iterator i = segStrings.iterator(); i.hasNext(); ) {
 57       SegmentString ss = (SegmentString) i.next();
 58       checkCollapses(ss);
 59     }
 60   }
 61  
 62   private void checkCollapses(SegmentString ss)
 63   {
 64     Coordinate[] pts = ss.getCoordinates();
 65     for (int i = 0; i < pts.length - 2; i++) {
 66       checkCollapse(pts[i], pts[i + 1], pts[i + 2]);
 67     }
 68   }
 69  
 70   private void checkCollapse(Coordinate p0, Coordinate p1, Coordinate p2)
 71   {
 72     if (p0.equals(p2))
 73       throw new RuntimeException("found non-noded collapse at "
 74         + fact.createLineString(new Coordinate[] { p0, p1, p2}));
 75   }
 76  
 77   /**
 78    * Checks all pairs of segments for intersections at an interior point of a segment
 79    */
 80   private void checkInteriorIntersections()
 81   {
 82     for (Iterator i = segStrings.iterator(); i.hasNext(); ) {
 83       SegmentString ss0 = (SegmentString) i.next();
 84       for (Iterator j = segStrings.iterator(); j.hasNext(); ) {
 85         SegmentString ss1 = (SegmentString) j.next();
 86  
 87           checkInteriorIntersections(ss0, ss1);
 88       }
 89     }
 90   }
 91  
 92   private void checkInteriorIntersections(SegmentString ss0, SegmentString ss1)
 93   {
 94     Coordinate[] pts0 = ss0.getCoordinates();
 95     Coordinate[] pts1 = ss1.getCoordinates();
 96     for (int i0 = 0; i0 < pts0.length - 1; i0++) {
 97       for (int i1 = 0; i1 < pts1.length - 1; i1++) {
 98         checkInteriorIntersections(ss0, i0, ss1, i1);
 99       }
100     }
101   }
102  
103   private void checkInteriorIntersections(SegmentString e0, int segIndex0, SegmentString e1, int segIndex1)
104   {
105     if (e0 == e1 && segIndex0 == segIndex1) return;
106 //numTests++;
107     Coordinate p00 = e0.getCoordinates()[segIndex0];
108     Coordinate p01 = e0.getCoordinates()[segIndex0 + 1];
109     Coordinate p10 = e1.getCoordinates()[segIndex1];
110     Coordinate p11 = e1.getCoordinates()[segIndex1 + 1];
111  
112     li.computeIntersection(p00, p01, p10, p11);
113     if (li.hasIntersection()) {
114  
115       if (li.isProper()
116           || hasInteriorIntersection(li, p00, p01)
117           || hasInteriorIntersection(li, p10, p11)) {
118         throw new RuntimeException("found non-noded intersection at "
119                                    + p00 + "-" + p01
120                                    + " and "
121                                    + p10 + "-" + p11);
122       }
123     }
124   }
125   /**
126    *@return true if there is an intersection point which is not an endpoint of the segment p0-p1
127    */
128   private boolean hasInteriorIntersection(LineIntersector li, Coordinate p0, Coordinate p1)
129   {
130     for (int i = 0; i < li.getIntersectionNum(); i++) {
131       Coordinate intPt = li.getIntersection(i);
132       if (! (intPt.equals(p0) || intPt.equals(p1)))
133           return true;
134     }
135     return false;
136   }
137  
138   /**
139    * Checks for intersections between an endpoint of a segment string
140    * and an interior vertex of another segment string
141    */
142   private void checkEndPtVertexIntersections()
143   {
144     for (Iterator i = segStrings.iterator(); i.hasNext(); ) {
145       SegmentString ss = (SegmentString) i.next();
146       Coordinate[] pts = ss.getCoordinates();
147       checkEndPtVertexIntersections(pts[0], segStrings);
148       checkEndPtVertexIntersections(pts[pts.length - 1], segStrings);
149     }
150   }
151  
152   private void checkEndPtVertexIntersections(Coordinate testPt, Collection segStrings)
153   {
154     for (Iterator i = segStrings.iterator(); i.hasNext(); ) {
155       SegmentString ss = (SegmentString) i.next();
156       Coordinate[] pts = ss.getCoordinates();
157       for (int j = 1; j < pts.length - 1; j++) {
158         if (pts[j].equals(testPt))
159           throw new RuntimeException("found endpt/interior pt intersection at index " + j + " :pt " + testPt);
160       }
161     }
162   }
163  
164  
165 }
166