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.CoordinateList; 16 import org.locationtech.jts.geom.Envelope; 17 18 /** 19 * Clips rings of points to a rectangle. 20 * Uses a variant of Cohen-Sutherland clipping. 21 * <p> 22 * In general the output is not topologically valid. 23 * In particular, the output may contain coincident non-noded line segments 24 * along the clip rectangle sides. 25 * However, the output is sufficiently well-structured 26 * that it can be used as input to the {@link OverlayNG} algorithm 27 * (which is able to process coincident linework due 28 * to the need to handle topology collapse under precision reduction). 29 * <p> 30 * Because of the likelihood of creating 31 * extraneous line segments along the clipping rectangle sides, 32 * this class is not suitable for clipping linestrings. 33 * <p> 34 * The clipping envelope should be generated using {@link RobustClipEnvelopeComputer}, 35 * to ensure that intersecting line segments are not perturbed 36 * by clipping. 37 * This is required to ensure that the overlay of the 38 * clipped geometry is robust and correct (i.e. the same as 39 * if clipping was not used). 40 * 41 * @see LineLimiter 42 * 43 * @author Martin Davis 44 * 45 */ 46 public class RingClipper { 47 48 private static final int BOX_LEFT = 3; 49 private static final int BOX_TOP = 2; 50 private static final int BOX_RIGHT = 1; 51 private static final int BOX_BOTTOM = 0; 52 53 private Envelope clipEnv; 54 private double clipEnvMinY; 55 private double clipEnvMaxY; 56 private double clipEnvMinX; 57 private double clipEnvMaxX; 58 59 /** 60 * Creates a new clipper for the given envelope. 61 * 62 * @param clipEnv the clipping envelope 63 */ RingClipper(Envelope clipEnv)64 public RingClipper(Envelope clipEnv) { 65 this.clipEnv = clipEnv; 66 clipEnvMinY = clipEnv.getMinY(); 67 clipEnvMaxY = clipEnv.getMaxY(); 68 clipEnvMinX = clipEnv.getMinX(); 69 clipEnvMaxX = clipEnv.getMaxX(); 70 } 71 72 /** 73 * Clips a list of points to the clipping rectangle box. 74 * 75 * @param ring 76 * @param env 77 * @return 78 */ clip(Coordinate[] pts)79 public Coordinate[] clip(Coordinate[] pts) { 80 for (int edgeIndex = 0; edgeIndex < 4; edgeIndex++) { 81 boolean closeRing = edgeIndex == 3; 82 pts = clipToBoxEdge(pts, edgeIndex, closeRing); 83 if (pts.length == 0) return pts; 84 } 85 return pts; 86 } 87 88 /** 89 * Clips line to the axis-parallel line defined by a single box edge. 90 * 91 * @param pts 92 * @param edgeIndex 93 * @param closeRing 94 * @return 95 */ clipToBoxEdge(Coordinate[] pts, int edgeIndex, boolean closeRing)96 private Coordinate[] clipToBoxEdge(Coordinate[] pts, int edgeIndex, boolean closeRing) { 97 // TODO: is it possible to avoid copying array 4 times? 98 CoordinateList ptsClip = new CoordinateList(); 99 100 Coordinate p0 = pts[pts.length - 1]; 101 for (int i = 0; i < pts.length; i++) { 102 Coordinate p1 = pts[i]; 103 if ( isInsideEdge(p1, edgeIndex) ) { 104 if ( ! isInsideEdge(p0, edgeIndex) ) { 105 Coordinate intPt = intersection(p0, p1, edgeIndex); 106 ptsClip.add( intPt, false); 107 } 108 // TODO: avoid copying so much? 109 ptsClip.add( p1.copy(), false); 110 111 } else if ( isInsideEdge(p0, edgeIndex) ) { 112 Coordinate intPt = intersection(p0, p1, edgeIndex); 113 ptsClip.add( intPt, false); 114 } 115 // else p0-p1 is outside box, so it is dropped 116 117 p0 = p1; 118 } 119 120 // add closing point if required 121 if (closeRing && ptsClip.size() > 0) { 122 Coordinate start = ptsClip.get(0); 123 if (! start.equals2D(ptsClip.get(ptsClip.size() - 1))) { 124 ptsClip.add( start.copy() ); 125 } 126 } 127 return ptsClip.toCoordinateArray(); 128 } 129 130 /** 131 * Computes the intersection point of a segment 132 * with an edge of the clip box. 133 * The segment must be known to intersect the edge. 134 * 135 * @param a first endpoint of the segment 136 * @param b second endpoint of the segment 137 * @param edgeIndex index of box edge 138 * @return the intersection point with the box edge 139 */ intersection(Coordinate a, Coordinate b, int edgeIndex)140 private Coordinate intersection(Coordinate a, Coordinate b, int edgeIndex) { 141 Coordinate intPt; 142 switch (edgeIndex) { 143 case BOX_BOTTOM: 144 intPt = new Coordinate(intersectionLineY(a, b, clipEnvMinY), clipEnvMinY); 145 break; 146 case BOX_RIGHT: 147 intPt = new Coordinate(clipEnvMaxX, intersectionLineX(a, b, clipEnvMaxX)); 148 break; 149 case BOX_TOP: 150 intPt = new Coordinate(intersectionLineY(a, b, clipEnvMaxY), clipEnvMaxY); 151 break; 152 case BOX_LEFT: 153 default: 154 intPt = new Coordinate(clipEnvMinX, intersectionLineX(a, b, clipEnvMinX)); 155 } 156 return intPt; 157 } 158 intersectionLineY(Coordinate a, Coordinate b, double y)159 private double intersectionLineY(Coordinate a, Coordinate b, double y) { 160 double m = (b.x - a.x) / (b.y - a.y); 161 double intercept = (y - a.y) * m; 162 return a.x + intercept; 163 } 164 intersectionLineX(Coordinate a, Coordinate b, double x)165 private double intersectionLineX(Coordinate a, Coordinate b, double x) { 166 double m = (b.y - a.y) / (b.x - a.x); 167 double intercept = (x - a.x) * m; 168 return a.y + intercept; 169 } 170 isInsideEdge(Coordinate p, int edgeIndex)171 private boolean isInsideEdge(Coordinate p, int edgeIndex) { 172 boolean isInside = false; 173 switch (edgeIndex) { 174 case BOX_BOTTOM: // bottom 175 isInside = p.y > clipEnvMinY; 176 break; 177 case BOX_RIGHT: // right 178 isInside = p.x < clipEnvMaxX; 179 break; 180 case BOX_TOP: // top 181 isInside = p.y < clipEnvMaxY; 182 break; 183 case BOX_LEFT: 184 default: // left 185 isInside = p.x > clipEnvMinX; 186 } 187 return isInside; 188 } 189 190 } 191