001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.tools; 003 004import java.awt.Shape; 005import java.awt.geom.Path2D; 006import java.awt.geom.PathIterator; 007import java.awt.geom.Rectangle2D; 008import java.util.Arrays; 009 010/** 011 * Tools to clip a shape based on the Sutherland-Hodgman algorithm. 012 * See https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm 013 * @author Gerd Petermann 014 * @since 14583 015 */ 016public final class ShapeClipper { 017 private static final int LEFT = 0; 018 private static final int TOP = 1; 019 private static final int RIGHT = 2; 020 private static final int BOTTOM = 3; 021 022 private ShapeClipper() { 023 // Hide default constructor for util classes 024 } 025 026 /** 027 * Clip a given (closed) shape with a given rectangle. 028 * @param shape the subject shape to clip 029 * @param clippingRect the clipping rectangle 030 * @return the intersection of the shape and the rectangle 031 * or null if they don't intersect or the shape is not closed. 032 * The intersection may contain dangling edges. 033 */ 034 public static Path2D.Double clipShape(Shape shape, Rectangle2D clippingRect) { 035 Path2D.Double result = new Path2D.Double(); 036 boolean hasData = false; 037 double minX, minY, maxX, maxY; 038 int num = 0; 039 minX = minY = Double.POSITIVE_INFINITY; 040 maxX = maxY = Double.NEGATIVE_INFINITY; 041 042 PathIterator pit = shape.getPathIterator(null); 043 double[] points = new double[512]; 044 double[] res = new double[6]; 045 while (!pit.isDone()) { 046 int type = pit.currentSegment(res); 047 if (num > 0 && (type == PathIterator.SEG_CLOSE || type == PathIterator.SEG_MOVETO || pit.isDone())) { 048 // we have extracted a single segment, maybe unclosed 049 boolean hasPath = addToResult(result, points, num, 050 new Rectangle2D.Double(minX, minY, maxX - minX, maxY - minY), clippingRect); 051 hasData |= hasPath; 052 if (hasPath && type == PathIterator.SEG_CLOSE) { 053 result.closePath(); 054 } 055 num = 0; 056 minX = minY = Double.POSITIVE_INFINITY; 057 maxX = maxY = Double.NEGATIVE_INFINITY; 058 } 059 double x = res[0]; 060 double y = res[1]; 061 if (x < minX) 062 minX = x; 063 if (x > maxX) 064 maxX = x; 065 if (y < minY) 066 minY = y; 067 if (y > maxY) 068 maxY = y; 069 if (type == PathIterator.SEG_LINETO || type == PathIterator.SEG_MOVETO) { 070 if (num + 2 >= points.length) { 071 points = Arrays.copyOf(points, points.length * 2); 072 } 073 points[num++] = x; 074 points[num++] = y; 075 } 076 pit.next(); 077 } 078 if (num > 2) { 079 // we get here if last segment was not closed 080 hasData |= addToResult(result, points, num, 081 new Rectangle2D.Double(minX, minY, maxX - minX, maxY - minY), clippingRect); 082 } 083 return hasData ? result : null; 084 } 085 086 /** 087 * Clip extracted segment if needed and add it to result if not completely outside of clipping rectangle. 088 * @param result the path that will describe the clipped shape (modified) 089 * @param points array of x/y pairs 090 * @param num the number of valid values in points 091 * @param bbox the bounding box of the path 092 * @param clippingRect the clipping rectangle 093 * @return true if data was added to result 094 */ 095 private static boolean addToResult(Path2D.Double result, double[] points, int num, 096 Rectangle2D bbox, Rectangle2D clippingRect) { 097 Path2D.Double segment = null; 098 if (clippingRect.contains(bbox)) { 099 // all points are inside clipping rectangle 100 segment = pointsToPath2D(points, num); 101 } else { 102 segment = clipSinglePathWithSutherlandHodgman(points, num, bbox, clippingRect); 103 } 104 if (segment != null) { 105 result.append(segment, false); 106 return true; 107 } 108 return false; 109 } 110 111 /** 112 * Convert a list of points to a Path2D.Double 113 * @param points array of x/y pairs 114 * @param num the number of valid values in points 115 * @return the path or null if the path describes a point or line. 116 */ 117 private static Path2D.Double pointsToPath2D(double[] points, int num) { 118 if (num < 2) 119 return null; 120 if (Double.compare(points[0], points[num - 2]) == 0 && Double.compare(points[1], points[num - 1]) == 0) { 121 num -= 2; 122 } 123 if (num < 6) 124 return null; 125 Path2D.Double path = new Path2D.Double(); 126 double lastX = points[0], lastY = points[1]; 127 path.moveTo(lastX, lastY); 128 int numOut = 1; 129 for (int i = 2; i < num; i += 2) { 130 double x = points[i], y = points[i+1]; 131 if (Double.compare(x, lastX) != 0 || Double.compare(y, lastY) != 0) { 132 path.lineTo(x, y); 133 lastX = x; 134 lastY = y; 135 ++numOut; 136 } 137 } 138 if (numOut < 3) 139 return null; 140 return path; 141 } 142 143 /** 144 * Clip a single path with a given rectangle using the Sutherland-Hodgman algorithm. This is much faster compared to 145 * the area.intersect method, but may create dangling edges. 146 * @param points array of x/y pairs 147 * @param num the number of valid values in points 148 * @param bbox the bounding box of the path 149 * @param clippingRect the clipping rectangle 150 * @return the clipped path as a Path2D.Double or null if the result is empty 151 */ 152 private static Path2D.Double clipSinglePathWithSutherlandHodgman(double[] points, int num, Rectangle2D bbox, 153 Rectangle2D clippingRect) { 154 if (num <= 2 || !bbox.intersects(clippingRect)) { 155 return null; 156 } 157 158 int countVals = num; 159 if (Double.compare(points[0], points[num - 2]) == 0 && Double.compare(points[1], points[num - 1]) == 0) { 160 countVals -= 2; 161 } 162 163 double[] outputList = points; 164 double[] input; 165 166 double leftX = clippingRect.getMinX(); 167 double rightX = clippingRect.getMaxX(); 168 double lowerY = clippingRect.getMinY(); 169 double upperY = clippingRect.getMaxY(); 170 boolean eIsIn = false, sIsIn = false; 171 for (int side = LEFT; side <= BOTTOM; side++) { 172 if (countVals < 6) 173 return null; // ignore point or line 174 175 boolean skipTestForThisSide; 176 switch (side) { 177 case LEFT: 178 skipTestForThisSide = (bbox.getMinX() >= leftX); 179 break; 180 case TOP: 181 skipTestForThisSide = (bbox.getMaxY() < upperY); 182 break; 183 case RIGHT: 184 skipTestForThisSide = (bbox.getMaxX() < rightX); 185 break; 186 default: 187 skipTestForThisSide = (bbox.getMinY() >= lowerY); 188 } 189 if (skipTestForThisSide) 190 continue; 191 192 input = outputList; 193 outputList = new double[countVals + 16]; 194 double sx = 0, sy = 0; 195 double px = 0, py = 0; // intersection 196 int posIn = countVals - 2; 197 int posOut = 0; 198 for (int i = 0; i < countVals + 2; i += 2) { 199 if (posIn >= countVals) 200 posIn = 0; 201 double ex = input[posIn++]; 202 double ey = input[posIn++]; 203 switch (side) { 204 case LEFT: 205 eIsIn = (ex >= leftX); 206 break; 207 case TOP: 208 eIsIn = (ey < upperY); 209 break; 210 case RIGHT: 211 eIsIn = (ex < rightX); 212 break; 213 default: 214 eIsIn = (ey >= lowerY); 215 } 216 if (i > 0) { 217 if (eIsIn != sIsIn) { 218 // compute intersection 219 double slope; 220 boolean isNotZero = Math.abs(ex - sx) > 1e-12; 221 if (isNotZero) 222 slope = (ey - sy) / (ex - sx); 223 else 224 slope = 1; 225 226 switch (side) { 227 case LEFT: 228 px = leftX; 229 py = slope * (leftX - sx) + sy; 230 break; 231 case RIGHT: 232 px = rightX; 233 py = slope * (rightX - sx) + sy; 234 break; 235 236 case TOP: 237 if (isNotZero) 238 px = sx + (upperY - sy) / slope; 239 else 240 px = sx; 241 py = upperY; 242 break; 243 default: // BOTTOM 244 if (isNotZero) 245 px = sx + (lowerY - sy) / slope; 246 else 247 px = sx; 248 py = lowerY; 249 break; 250 251 } 252 } 253 int toAdd = 0; 254 if (eIsIn) { 255 if (!sIsIn) { 256 toAdd += 2; 257 } 258 toAdd += 2; 259 } else { 260 if (sIsIn) { 261 toAdd += 2; 262 } 263 } 264 if (posOut + toAdd >= outputList.length) { 265 // unlikely 266 outputList = Arrays.copyOf(outputList, outputList.length * 2); 267 } 268 if (eIsIn) { 269 if (!sIsIn) { 270 outputList[posOut++] = px; 271 outputList[posOut++] = py; 272 } 273 outputList[posOut++] = ex; 274 outputList[posOut++] = ey; 275 } else { 276 if (sIsIn) { 277 outputList[posOut++] = px; 278 outputList[posOut++] = py; 279 } 280 } 281 } 282 // S = E 283 sx = ex; 284 sy = ey; 285 sIsIn = eIsIn; 286 } 287 countVals = posOut; 288 } 289 return pointsToPath2D(outputList, countVals); 290 } 291}