Doc Classic

Class SegmentIntersector

  1  
  2  
  3  
  4 /*
  5  * Copyright (c) 2016 Vivid Solutions.
  6  *
  7  * All rights reserved. This program and the accompanying materials
  8  * are made available under the terms of the Eclipse Public License 2.0
  9  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
 10  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
 11  * and the Eclipse Distribution License is available at
 12  *
 13  * http://www.eclipse.org/org/documents/edl-v10.php.
 14  */
 15 package org.locationtech.jts.geomgraph.index;
 16  
 17 import java.util.Collection;
 18 import java.util.Iterator;
 19  
 20 import org.locationtech.jts.algorithm.LineIntersector;
 21 import org.locationtech.jts.geom.Coordinate;
 22 import org.locationtech.jts.geomgraph.Edge;
 23 import org.locationtech.jts.geomgraph.Node;
 24  
 25  
 26 /**
 27  * Computes the intersection of line segments,
 28  * and adds the intersection to the edges containing the segments.
 29  * 
 30  * @version 1.7
 31  */
 32 public class SegmentIntersector 
 33 {
 34  
 35   public static boolean isAdjacentSegments(int i1, int i2)
 36   {
 37     return Math.abs(i1 - i2) == 1;
 38   }
 39  
 40   /**
 41    * These variables keep track of what types of intersections were
 42    * found during ALL edges that have been intersected.
 43    */
 44   private boolean hasIntersection = false;
 45   private boolean hasProper = false;
 46   private boolean hasProperInterior = false;
 47   // the proper intersection point found
 48   private Coordinate properIntersectionPoint = null;
 49  
 50   private LineIntersector li;
 51   private boolean includeProper;
 52   private boolean recordIsolated;
 53   private boolean isSelfIntersection;
 54   //private boolean intersectionFound;
 55   private int numIntersections = 0;
 56  
 57   // testing only
 58   public int numTests = 0;
 59  
 60   private Collection[] bdyNodes;
 61   private boolean isDone = false;
 62   private boolean isDoneWhenProperInt = false;
 63  
 64  
 65   public SegmentIntersector(LineIntersector li,  boolean includeProper, boolean recordIsolated)
 66   {
 67     this.li = li;
 68     this.includeProper = includeProper;
 69     this.recordIsolated = recordIsolated;
 70   }
 71  
 72   public void setBoundaryNodes( Collection bdyNodes0,
 73                               Collection bdyNodes1)
 74   {
 75       bdyNodes = new Collection[2];
 76       bdyNodes[0] = bdyNodes0;
 77       bdyNodes[1] = bdyNodes1;
 78   }
 79  
 80   public void setIsDoneIfProperInt(boolean isDoneWhenProperInt) {
 81       this.isDoneWhenProperInt = isDoneWhenProperInt;
 82   }
 83   
 84   public boolean isDone() {
 85       return isDone;
 86   }
 87   /**
 88    * @return the proper intersection point, or <code>null</code> if none was found
 89    */
 90   public Coordinate getProperIntersectionPoint()  {    return properIntersectionPoint;  }
 91  
 92   public boolean hasIntersection() { return hasIntersection; }
 93   /**
 94    * A proper intersection is an intersection which is interior to at least two
 95    * line segments.  Note that a proper intersection is not necessarily
 96    * in the interior of the entire Geometry, since another edge may have
 97    * an endpoint equal to the intersection, which according to SFS semantics
 98    * can result in the point being on the Boundary of the Geometry.
 99    */
100   public boolean hasProperIntersection() { return hasProper; }
101   /**
102    * A proper interior intersection is a proper intersection which is <b>not</b>
103    * contained in the set of boundary nodes set for this SegmentIntersector.
104    */
105   public boolean hasProperInteriorIntersection() { return hasProperInterior; }
106  
107  
108   /**
109    * A trivial intersection is an apparent self-intersection which in fact
110    * is simply the point shared by adjacent line segments.
111    * Note that closed edges require a special check for the point shared by the beginning
112    * and end segments.
113    */
114   private boolean isTrivialIntersection(Edge e0, int segIndex0, Edge e1, int segIndex1)
115   {
116     if (e0 == e1) {
117       if (li.getIntersectionNum() == 1) {
118         if (isAdjacentSegments(segIndex0, segIndex1))
119           return true;
120         if (e0.isClosed()) {
121           int maxSegIndex = e0.getNumPoints() - 1;
122           if (    (segIndex0 == 0 && segIndex1 == maxSegIndex)
123               ||  (segIndex1 == 0 && segIndex0 == maxSegIndex) ) {
124             return true;
125           }
126         }
127       }
128     }
129     return false;
130   }
131  
132   /**
133    * This method is called by clients of the EdgeIntersector class to test for and add
134    * intersections for two segments of the edges being intersected.
135    * Note that clients (such as MonotoneChainEdges) may choose not to intersect
136    * certain pairs of segments for efficiency reasons.
137    */
138   public void addIntersections(
139     Edge e0,  int segIndex0,
140     Edge e1,  int segIndex1
141      )
142   {
143     if (e0 == e1 && segIndex0 == segIndex1) return;
144 numTests++;
145     Coordinate p00 = e0.getCoordinates()[segIndex0];
146     Coordinate p01 = e0.getCoordinates()[segIndex0 + 1];
147     Coordinate p10 = e1.getCoordinates()[segIndex1];
148     Coordinate p11 = e1.getCoordinates()[segIndex1 + 1];
149  
150     li.computeIntersection(p00, p01, p10, p11);
151 //if (li.hasIntersection() && li.isProper()) Debug.println(li);
152     /**
153      *  Always record any non-proper intersections.
154      *  If includeProper is true, record any proper intersections as well.
155      */
156     if (li.hasIntersection()) {
157       if (recordIsolated) {
158         e0.setIsolated(false);
159         e1.setIsolated(false);
160       }
161       //intersectionFound = true;
162       numIntersections++;
163       // if the segments are adjacent they have at least one trivial intersection,
164       // the shared endpoint.  Don't bother adding it if it is the
165       // only intersection.
166       if (! isTrivialIntersection(e0, segIndex0, e1, segIndex1)) {
167         hasIntersection = true;
168         if (includeProper || ! li.isProper() ) {
169 //Debug.println(li);
170           e0.addIntersections(li, segIndex0, 0);
171           e1.addIntersections(li, segIndex1, 1);
172         }
173         if (li.isProper()) {
174           properIntersectionPoint = li.getIntersection(0).copy();
175           hasProper = true;
176           if (isDoneWhenProperInt) {
177               isDone = true;
178           }
179           if (! isBoundaryPoint(li, bdyNodes))
180             hasProperInterior = true;
181         }
182         //if (li.isCollinear())
183           //hasCollinear = true;
184       }
185     }
186   }
187  
188   private boolean isBoundaryPoint(LineIntersector li, Collection[] bdyNodes)
189   {
190     if (bdyNodes == null) return false;
191     if (isBoundaryPointInternal(li, bdyNodes[0])) return true;
192     if (isBoundaryPointInternal(li, bdyNodes[1])) return true;
193     return false;
194   }
195  
196   private boolean isBoundaryPointInternal(LineIntersector li, Collection bdyNodes)
197   {
198     for (Iterator i = bdyNodes.iterator(); i.hasNext(); ) {
199       Node node = (Node) i.next();
200       Coordinate pt = node.getCoordinate();
201       if (li.isIntersection(pt)) return true;
202     }
203     return false;
204   }
205  
206 }
207