Doc Classic

Class RelateComputer

  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.operation.relate;
 16  
 17 /**
 18  * @version 1.7
 19  */
 20 import java.util.ArrayList;
 21 import java.util.Iterator;
 22 import java.util.List;
 23  
 24 import org.locationtech.jts.algorithm.LineIntersector;
 25 import org.locationtech.jts.algorithm.PointLocator;
 26 import org.locationtech.jts.algorithm.RobustLineIntersector;
 27 import org.locationtech.jts.geom.Coordinate;
 28 import org.locationtech.jts.geom.Geometry;
 29 import org.locationtech.jts.geom.IntersectionMatrix;
 30 import org.locationtech.jts.geom.Location;
 31 import org.locationtech.jts.geomgraph.Edge;
 32 import org.locationtech.jts.geomgraph.EdgeEnd;
 33 import org.locationtech.jts.geomgraph.EdgeIntersection;
 34 import org.locationtech.jts.geomgraph.GeometryGraph;
 35 import org.locationtech.jts.geomgraph.Label;
 36 import org.locationtech.jts.geomgraph.Node;
 37 import org.locationtech.jts.geomgraph.NodeMap;
 38 import org.locationtech.jts.geomgraph.index.SegmentIntersector;
 39 import org.locationtech.jts.util.Assert;
 40  
 41 /**
 42  * Computes the topological relationship between two Geometries.
 43  * <p>
 44  * RelateComputer does not need to build a complete graph structure to compute
 45  * the IntersectionMatrix.  The relationship between the geometries can
 46  * be computed by simply examining the labelling of edges incident on each node.
 47  * <p>
 48  * RelateComputer does not currently support arbitrary GeometryCollections.
 49  * This is because GeometryCollections can contain overlapping Polygons.
 50  * In order to correct compute relate on overlapping Polygons, they
 51  * would first need to be noded and merged (if not explicitly, at least
 52  * implicitly).
 53  *
 54  * @version 1.7
 55  */
 56 public class RelateComputer
 57 {
 58   private LineIntersector li = new RobustLineIntersector();
 59   private PointLocator ptLocator = new PointLocator();
 60   private GeometryGraph[] arg;  // the arg(s) of the operation
 61   private NodeMap nodes = new NodeMap(new RelateNodeFactory());
 62   // this intersection matrix will hold the results compute for the relate
 63   private IntersectionMatrix im = null;
 64   private ArrayList isolatedEdges = new ArrayList();
 65  
 66   // the intersection point found (if any)
 67   private Coordinate invalidPoint;
 68  
 69   public RelateComputer(GeometryGraph[] arg) {
 70     this.arg = arg;
 71   }
 72  
 73   public IntersectionMatrix computeIM()
 74   {
 75     IntersectionMatrix im = new IntersectionMatrix();
 76     // since Geometries are finite and embedded in a 2-D space, the EE element must always be 2
 77     im.set(Location.EXTERIOR, Location.EXTERIOR, 2);
 78  
 79     // if the Geometries don't overlap there is nothing to do
 80     if (! arg[0].getGeometry().getEnvelopeInternal().intersects(
 81             arg[1].getGeometry().getEnvelopeInternal()) ) {
 82       computeDisjointIM(im);
 83       return im;
 84     }
 85     arg[0].computeSelfNodes(li, false);
 86     arg[1].computeSelfNodes(li, false);
 87  
 88     // compute intersections between edges of the two input geometries
 89     SegmentIntersector intersector = arg[0].computeEdgeIntersections(arg[1], li, false);
 90 //System.out.println("computeIM: # segment intersection tests: " + intersector.numTests);
 91     computeIntersectionNodes(0);
 92     computeIntersectionNodes(1);
 93     /**
 94      * Copy the labelling for the nodes in the parent Geometries.  These override
 95      * any labels determined by intersections between the geometries.
 96      */
 97     copyNodesAndLabels(0);
 98     copyNodesAndLabels(1);
 99  
100     // complete the labelling for any nodes which only have a label for a single geometry
101 //Debug.addWatch(nodes.find(new Coordinate(110, 200)));
102 //Debug.printWatch();
103     labelIsolatedNodes();
104 //Debug.printWatch();
105  
106     // If a proper intersection was found, we can set a lower bound on the IM.
107     computeProperIntersectionIM(intersector, im);
108  
109     /**
110      * Now process improper intersections
111      * (eg where one or other of the geometries has a vertex at the intersection point)
112      * We need to compute the edge graph at all nodes to determine the IM.
113      */
114  
115     // build EdgeEnds for all intersections
116     EdgeEndBuilder eeBuilder = new EdgeEndBuilder();
117     List ee0 = eeBuilder.computeEdgeEnds(arg[0].getEdgeIterator());
118     insertEdgeEnds(ee0);
119     List ee1 = eeBuilder.computeEdgeEnds(arg[1].getEdgeIterator());
120     insertEdgeEnds(ee1);
121  
122 //Debug.println("==== NodeList ===");
123 //Debug.print(nodes);
124  
125     labelNodeEdges();
126  
127   /**
128    * Compute the labeling for isolated components
129    * <br>
130    * Isolated components are components that do not touch any other components in the graph.
131    * They can be identified by the fact that they will
132    * contain labels containing ONLY a single element, the one for their parent geometry.
133    * We only need to check components contained in the input graphs, since
134    * isolated components will not have been replaced by new components formed by intersections.
135    */
136 //debugPrintln("Graph A isolated edges - ");
137     labelIsolatedEdges(0, 1);
138 //debugPrintln("Graph B isolated edges - ");
139     labelIsolatedEdges(1, 0);
140  
141     // update the IM from all components
142     updateIM(im);
143     return im;
144   }
145  
146   private void insertEdgeEnds(List ee)
147   {
148     for (Iterator i = ee.iterator(); i.hasNext(); ) {
149       EdgeEnd e = (EdgeEnd) i.next();
150       nodes.add(e);
151     }
152   }
153  
154   private void computeProperIntersectionIM(SegmentIntersector intersector, IntersectionMatrix im)
155   {
156     // If a proper intersection is found, we can set a lower bound on the IM.
157     int dimA = arg[0].getGeometry().getDimension();
158     int dimB = arg[1].getGeometry().getDimension();
159     boolean hasProper         = intersector.hasProperIntersection();
160     boolean hasProperInterior = intersector.hasProperInteriorIntersection();
161  
162       // For Geometry's of dim 0 there can never be proper intersections.
163  
164       /**
165        * If edge segments of Areas properly intersect, the areas must properly overlap.
166        */
167     if (dimA == 2 && dimB == 2) {
168       if (hasProper) im.setAtLeast("212101212");
169     }
170       /**
171        * If an Line segment properly intersects an edge segment of an Area,
172        * it follows that the Interior of the Line intersects the Boundary of the Area.
173        * If the intersection is a proper <i>interior</i> intersection, then
174        * there is an Interior-Interior intersection too.
175        * Note that it does not follow that the Interior of the Line intersects the Exterior
176        * of the Area, since there may be another Area component which contains the rest of the Line.
177        */
178     else if (dimA == 2 && dimB == 1) {
179       if (hasProper)          im.setAtLeast("FFF0FFFF2");
180       if (hasProperInterior)  im.setAtLeast("1FFFFF1FF");
181     }
182     else if (dimA == 1 && dimB == 2) {
183       if (hasProper)          im.setAtLeast("F0FFFFFF2");
184       if (hasProperInterior)  im.setAtLeast("1F1FFFFFF");
185     }
186     /* If edges of LineStrings properly intersect *in an interior point*, all
187         we can deduce is that
188         the interiors intersect.  (We can NOT deduce that the exteriors intersect,
189         since some other segments in the geometries might cover the points in the
190         neighbourhood of the intersection.)
191         It is important that the point be known to be an interior point of
192         both Geometries, since it is possible in a self-intersecting geometry to
193         have a proper intersection on one segment that is also a boundary point of another segment.
194     */
195     else if (dimA == 1 && dimB == 1) {
196       if (hasProperInterior)    im.setAtLeast("0FFFFFFFF");
197     }
198   }
199  
200     /**
201      * Copy all nodes from an arg geometry into this graph.
202      * The node label in the arg geometry overrides any previously computed
203      * label for that argIndex.
204      * (E.g. a node may be an intersection node with
205      * a computed label of BOUNDARY,
206      * but in the original arg Geometry it is actually
207      * in the interior due to the Boundary Determination Rule)
208      */
209   private void copyNodesAndLabels(int argIndex)
210   {
211     for (Iterator i = arg[argIndex].getNodeIterator(); i.hasNext(); ) {
212       Node graphNode = (Node) i.next();
213       Node newNode = nodes.addNode(graphNode.getCoordinate());
214       newNode.setLabel(argIndex, graphNode.getLabel().getLocation(argIndex));
215 //node.print(System.out);
216     }
217   }
218   /**
219    * Insert nodes for all intersections on the edges of a Geometry.
220    * Label the created nodes the same as the edge label if they do not already have a label.
221    * This allows nodes created by either self-intersections or
222    * mutual intersections to be labelled.
223    * Endpoint nodes will already be labelled from when they were inserted.
224    */
225   private void computeIntersectionNodes(int argIndex)
226   {
227     for (Iterator i = arg[argIndex].getEdgeIterator(); i.hasNext(); ) {
228       Edge e = (Edge) i.next();
229       int eLoc = e.getLabel().getLocation(argIndex);
230       for (Iterator eiIt = e.getEdgeIntersectionList().iterator(); eiIt.hasNext(); ) {
231         EdgeIntersection ei = (EdgeIntersection) eiIt.next();
232         RelateNode n = (RelateNode) nodes.addNode(ei.coord);
233         if (eLoc == Location.BOUNDARY)
234           n.setLabelBoundary(argIndex);
235         else {
236           if (n.getLabel().isNull(argIndex))
237             n.setLabel(argIndex, Location.INTERIOR);
238         }
239 //Debug.println(n);
240       }
241     }
242   }
243   /**
244    * For all intersections on the edges of a Geometry,
245    * label the corresponding node IF it doesn't already have a label.
246    * This allows nodes created by either self-intersections or
247    * mutual intersections to be labelled.
248    * Endpoint nodes will already be labelled from when they were inserted.
249    */
250   private void labelIntersectionNodes(int argIndex)
251   {
252     for (Iterator i = arg[argIndex].getEdgeIterator(); i.hasNext(); ) {
253       Edge e = (Edge) i.next();
254       int eLoc = e.getLabel().getLocation(argIndex);
255       for (Iterator eiIt = e.getEdgeIntersectionList().iterator(); eiIt.hasNext(); ) {
256         EdgeIntersection ei = (EdgeIntersection) eiIt.next();
257         RelateNode n = (RelateNode) nodes.find(ei.coord);
258         if (n.getLabel().isNull(argIndex)) {
259           if (eLoc == Location.BOUNDARY)
260             n.setLabelBoundary(argIndex);
261           else
262             n.setLabel(argIndex, Location.INTERIOR);
263         }
264 //n.print(System.out);
265       }
266     }
267   }
268   /**
269    * If the Geometries are disjoint, we need to enter their dimension and
270    * boundary dimension in the Ext rows in the IM
271    */
272   private void computeDisjointIM(IntersectionMatrix im)
273   {
274     Geometry ga = arg[0].getGeometry();
275     if (! ga.isEmpty()) {
276       im.set(Location.INTERIOR, Location.EXTERIOR, ga.getDimension());
277       im.set(Location.BOUNDARY, Location.EXTERIOR, ga.getBoundaryDimension());
278     }
279     Geometry gb = arg[1].getGeometry();
280     if (! gb.isEmpty()) {
281       im.set(Location.EXTERIOR, Location.INTERIOR, gb.getDimension());
282       im.set(Location.EXTERIOR, Location.BOUNDARY, gb.getBoundaryDimension());
283     }
284   }
285  
286   private void labelNodeEdges()
287   {
288     for (Iterator ni = nodes.iterator(); ni.hasNext(); ) {
289       RelateNode node = (RelateNode) ni.next();
290       node.getEdges().computeLabelling(arg);
291 //Debug.print(node.getEdges());
292 //node.print(System.out);
293     }
294   }
295  
296   /**
297    * update the IM with the sum of the IMs for each component
298    */
299   private void updateIM(IntersectionMatrix im)
300   {
301 //Debug.println(im);
302     for (Iterator ei = isolatedEdges.iterator(); ei.hasNext(); ) {
303       Edge e = (Edge) ei.next();
304       e.updateIM(im);
305 //Debug.println(im);
306     }
307     for (Iterator ni = nodes.iterator(); ni.hasNext(); ) {
308       RelateNode node = (RelateNode) ni.next();
309       node.updateIM(im);
310 //Debug.println(im);
311       node.updateIMFromEdges(im);
312 //Debug.println(im);
313 //node.print(System.out);
314     }
315   }
316  
317   /**
318    * Processes isolated edges by computing their labelling and adding them
319    * to the isolated edges list.
320    * Isolated edges are guaranteed not to touch the boundary of the target (since if they
321    * did, they would have caused an intersection to be computed and hence would
322    * not be isolated)
323    */
324   private void labelIsolatedEdges(int thisIndex, int targetIndex)
325   {
326     for (Iterator ei = arg[thisIndex].getEdgeIterator(); ei.hasNext(); ) {
327       Edge e = (Edge) ei.next();
328       if (e.isIsolated()) {
329         labelIsolatedEdge(e, targetIndex, arg[targetIndex].getGeometry());
330         isolatedEdges.add(e);
331       }
332     }
333   }
334   /**
335    * Label an isolated edge of a graph with its relationship to the target geometry.
336    * If the target has dim 2 or 1, the edge can either be in the interior or the exterior.
337    * If the target has dim 0, the edge must be in the exterior
338    */
339   private void labelIsolatedEdge(Edge e, int targetIndex, Geometry target)
340   {
341     // this won't work for GeometryCollections with both dim 2 and 1 geoms
342     if ( target.getDimension() > 0) {
343     // since edge is not in boundary, may not need the full generality of PointLocator?
344     // Possibly should use ptInArea locator instead?  We probably know here
345     // that the edge does not touch the bdy of the target Geometry
346       int loc = ptLocator.locate(e.getCoordinate(), target);
347       e.getLabel().setAllLocations(targetIndex, loc);
348     }
349     else {
350       e.getLabel().setAllLocations(targetIndex, Location.EXTERIOR);
351     }
352 //System.out.println(e.getLabel());
353   }
354  
355   /**
356    * Isolated nodes are nodes whose labels are incomplete
357    * (e.g. the location for one Geometry is null).
358    * This is the case because nodes in one graph which don't intersect
359    * nodes in the other are not completely labelled by the initial process
360    * of adding nodes to the nodeList.
361    * To complete the labelling we need to check for nodes that lie in the
362    * interior of edges, and in the interior of areas.
363    */
364   private void labelIsolatedNodes()
365   {
366     for (Iterator ni = nodes.iterator(); ni.hasNext(); ) {
367       Node n = (Node) ni.next();
368       Label label = n.getLabel();
369       // isolated nodes should always have at least one geometry in their label
370       Assert.isTrue(label.getGeometryCount() > 0, "node with empty label found");
371       if (n.isIsolated()) {
372         if (label.isNull(0))
373           labelIsolatedNode(n, 0);
374         else
375           labelIsolatedNode(n, 1);
376       }
377     }
378   }
379  
380   /**
381    * Label an isolated node with its relationship to the target geometry.
382    */
383   private void labelIsolatedNode(Node n, int targetIndex)
384   {
385     int loc = ptLocator.locate(n.getCoordinate(), arg[targetIndex].getGeometry());
386     n.getLabel().setAllLocations(targetIndex, loc);
387 //debugPrintln(n.getLabel());
388   }
389 }
390