1 /*
2  * Copyright (c) 2019 Martin Davis.
3  *
4  * All rights reserved. This program and the accompanying materials
5  * are made available under the terms of the Eclipse Public License 2.0
6  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8  * and the Eclipse Distribution License is available at
9  *
10  * http://www.eclipse.org/org/documents/edl-v10.php.
11  */
12 package org.locationtech.jts.operation.overlayng;
13 
14 import org.locationtech.jts.geom.Coordinate;
15 import org.locationtech.jts.geom.CoordinateSequence;
16 import org.locationtech.jts.geom.Envelope;
17 import org.locationtech.jts.geom.Geometry;
18 import org.locationtech.jts.geom.GeometryCollection;
19 import org.locationtech.jts.geom.LinearRing;
20 import org.locationtech.jts.geom.Polygon;
21 
22 /**
23  * Computes a robust clipping envelope for a pair of polygonal geometries.
24  * The envelope is computed to be large enough to include the full
25  * length of all geometry line segments which intersect
26  * a given target envelope.
27  * This ensures that line segments which might intersect are
28  * not perturbed when clipped using {@link RingClipper}.
29  *
30  * @author Martin Davis
31  *
32  */
33 class RobustClipEnvelopeComputer {
34 
getEnvelope(Geometry a, Geometry b, Envelope targetEnv)35   public static Envelope getEnvelope(Geometry a, Geometry b, Envelope targetEnv) {
36     RobustClipEnvelopeComputer cec = new RobustClipEnvelopeComputer(targetEnv);
37     cec.add(a);
38     cec.add(b);
39     return cec.getEnvelope();
40   }
41 
42   private Envelope targetEnv;
43   private Envelope clipEnv;
44 
RobustClipEnvelopeComputer(Envelope targetEnv)45   public RobustClipEnvelopeComputer(Envelope targetEnv) {
46     this.targetEnv = targetEnv;
47     clipEnv = targetEnv.copy();
48   }
49 
getEnvelope()50   public Envelope getEnvelope() {
51     return clipEnv;
52   }
53 
add(Geometry g)54   public void add(Geometry g) {
55     if ( g == null || g.isEmpty() )
56       return;
57 
58     if ( g instanceof Polygon )
59       addPolygon((Polygon) g);
60     else if ( g instanceof GeometryCollection )
61       addCollection((GeometryCollection) g);
62   }
63 
addCollection(GeometryCollection gc)64   private void addCollection(GeometryCollection gc) {
65     for (int i = 0; i < gc.getNumGeometries(); i++) {
66       Geometry g = gc.getGeometryN(i);
67       add(g);
68     }
69   }
70 
addPolygon(Polygon poly)71   private void addPolygon(Polygon poly) {
72     LinearRing shell = poly.getExteriorRing();
73     addPolygonRing(shell);
74 
75     for (int i = 0; i < poly.getNumInteriorRing(); i++) {
76       LinearRing hole = poly.getInteriorRingN(i);
77       addPolygonRing(hole);
78     }
79   }
80 
81   /**
82    * Adds a polygon ring to the graph. Empty rings are ignored.
83    */
addPolygonRing(LinearRing ring)84   private void addPolygonRing(LinearRing ring) {
85     // don't add empty lines
86     if ( ring.isEmpty() )
87       return;
88 
89     CoordinateSequence seq = ring.getCoordinateSequence();
90     for (int i = 1; i < seq.size(); i++) {
91       addSegment(seq.getCoordinate(i - 1), seq.getCoordinate(i));
92     }
93   }
94 
addSegment(Coordinate p1, Coordinate p2)95   private void addSegment(Coordinate p1, Coordinate p2) {
96     if (intersectsSegment(targetEnv, p1, p2)) {
97       clipEnv.expandToInclude(p1);
98       clipEnv.expandToInclude(p2);
99     }
100   }
101 
intersectsSegment(Envelope env, Coordinate p1, Coordinate p2)102   private static boolean intersectsSegment(Envelope env, Coordinate p1, Coordinate p2) {
103     /**
104      * This is a crude test of whether segment intersects envelope.
105      * It could be refined by checking exact intersection.
106      * This could be based on the algorithm in the HotPixel.intersectsScaled method.
107      */
108     return env.intersects(p1, p2);
109   }
110 }
111