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}