source: josm/trunk/src/org/openstreetmap/josm/tools/ShapeClipper.java@ 16966

Last change on this file since 16966 was 14627, checked in by GerdP, 5 years ago

fix #17167 : Regression from #17119 clipped closed path was not closed
File size: 10.6 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.tools;
3
4import java.awt.Shape;
5import java.awt.geom.Path2D;
6import java.awt.geom.PathIterator;
7import java.awt.geom.Rectangle2D;
8import java.util.Arrays;
9
10/**
11 * Tools to clip a shape based on the Sutherland-Hodgman algorithm.
12 * See https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm
13 * @author Gerd Petermann
14 * @since 14583
15 */
16public final class ShapeClipper {
17 private static final int LEFT = 0;
18 private static final int TOP = 1;
19 private static final int RIGHT = 2;
20 private static final int BOTTOM = 3;
21
22 private ShapeClipper() {
23 // Hide default constructor for util classes
24 }
25
26 /**
27 * Clip a given (closed) shape with a given rectangle.
28 * @param shape the subject shape to clip
29 * @param clippingRect the clipping rectangle
30 * @return the intersection of the shape and the rectangle
31 * or null if they don't intersect or the shape is not closed.
32 * The intersection may contain dangling edges.
33 */
34 public static Path2D.Double clipShape(Shape shape, Rectangle2D clippingRect) {
35 Path2D.Double result = new Path2D.Double();
36 boolean hasData = false;
37 double minX, minY, maxX, maxY;
38 int num = 0;
39 minX = minY = Double.POSITIVE_INFINITY;
40 maxX = maxY = Double.NEGATIVE_INFINITY;
41
42 PathIterator pit = shape.getPathIterator(null);
43 double[] points = new double[512];
44 double[] res = new double[6];
45 while (!pit.isDone()) {
46 int type = pit.currentSegment(res);
47 if (num > 0 && (type == PathIterator.SEG_CLOSE || type == PathIterator.SEG_MOVETO || pit.isDone())) {
48 // we have extracted a single segment, maybe unclosed
49 boolean hasPath = addToResult(result, points, num,
50 new Rectangle2D.Double(minX, minY, maxX - minX, maxY - minY), clippingRect);
51 hasData |= hasPath;
52 if (hasPath && type == PathIterator.SEG_CLOSE) {
53 result.closePath();
54 }
55 num = 0;
56 minX = minY = Double.POSITIVE_INFINITY;
57 maxX = maxY = Double.NEGATIVE_INFINITY;
58 }
59 double x = res[0];
60 double y = res[1];
61 if (x < minX)
62 minX = x;
63 if (x > maxX)
64 maxX = x;
65 if (y < minY)
66 minY = y;
67 if (y > maxY)
68 maxY = y;
69 if (type == PathIterator.SEG_LINETO || type == PathIterator.SEG_MOVETO) {
70 if (num + 2 >= points.length) {
71 points = Arrays.copyOf(points, points.length * 2);
72 }
73 points[num++] = x;
74 points[num++] = y;
75 }
76 pit.next();
77 }
78 if (num > 2) {
79 // we get here if last segment was not closed
80 hasData |= addToResult(result, points, num,
81 new Rectangle2D.Double(minX, minY, maxX - minX, maxY - minY), clippingRect);
82 }
83 return hasData ? result : null;
84 }
85
86 /**
87 * Clip extracted segment if needed and add it to result if not completely outside of clipping rectangle.
88 * @param result the path that will describe the clipped shape (modified)
89 * @param points array of x/y pairs
90 * @param num the number of valid values in points
91 * @param bbox the bounding box of the path
92 * @param clippingRect the clipping rectangle
93 * @return true if data was added to result
94 */
95 private static boolean addToResult(Path2D.Double result, double[] points, int num,
96 Rectangle2D bbox, Rectangle2D clippingRect) {
97 Path2D.Double segment = null;
98 if (clippingRect.contains(bbox)) {
99 // 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}
Note: See TracBrowser for help on using the repository browser.