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