001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.osm.visitor.paint;
003
004import static java.awt.geom.Rectangle2D.OUT_BOTTOM;
005import static java.awt.geom.Rectangle2D.OUT_LEFT;
006import static java.awt.geom.Rectangle2D.OUT_RIGHT;
007import static java.awt.geom.Rectangle2D.OUT_TOP;
008
009import java.awt.Point;
010import java.awt.Rectangle;
011
012/**
013 * Computes the part of a line that is visible in a given rectangle.
014 * Using int leads to overflow, so we need long int.
015 */
016public class LineClip {
017    private Point p1, p2;
018    private final Rectangle clipBounds;
019
020    /**
021     * Constructs a new {@code LineClip}.
022     * @param p1 start point of the clipped line
023     * @param p2 end point of the clipped line
024     * @param clipBounds Clip bounds
025     */
026    public LineClip(Point p1, Point p2, Rectangle clipBounds) {
027        this.p1 = p1;
028        this.p2 = p2;
029        this.clipBounds = clipBounds;
030    }
031
032    /**
033     * run the clipping algorithm
034     * @return true if the some parts of the line lies within the clip bounds
035     */
036    public boolean execute() {
037        if (clipBounds == null) {
038            return false;
039        }
040        return cohenSutherland(p1.x, p1.y, p2.x, p2.y, clipBounds.x, clipBounds.y,
041                clipBounds.x + clipBounds.width, clipBounds.y + clipBounds.height);
042    }
043
044    /**
045     * @return start point of the clipped line
046     */
047    public Point getP1() {
048        return p1;
049    }
050
051    /**
052     * @return end point of the clipped line
053     */
054    public Point getP2() {
055        return p2;
056    }
057
058    /**
059     * Cohen–Sutherland algorithm.
060     * See <a href="https://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm">Wikipedia article</a>
061     * @param x1 X coordinate of first point
062     * @param y1 Y coordinate of first point
063     * @param x2 X coordinate of second point
064     * @param y2 Y coordinate of second point
065     * @param xmin minimal X coordinate
066     * @param ymin minimal Y coordinate
067     * @param xmax maximal X coordinate
068     * @param ymax maximal Y coordinate
069     * @return true, if line is visible in the given clip region
070     */
071    private boolean cohenSutherland(long x1, long y1, long x2, long y2, long xmin, long ymin, long xmax, long ymax) {
072        int outcode0, outcode1, outcodeOut;
073        boolean accept = false;
074        boolean done = false;
075
076        outcode0 = computeOutCode(x1, y1, xmin, ymin, xmax, ymax);
077        outcode1 = computeOutCode(x2, y2, xmin, ymin, xmax, ymax);
078
079        do {
080            if ((outcode0 | outcode1) == 0) {
081                accept = true;
082                done = true;
083            } else if ((outcode0 & outcode1) > 0) {
084                done = true;
085            } else {
086                long x = 0, y = 0;
087                outcodeOut = outcode0 != 0 ? outcode0 : outcode1;
088                if ((outcodeOut & OUT_TOP) > 0) {
089                    x = x1 + (x2 - x1) * (ymax - y1)/(y2 - y1);
090                    y = ymax;
091                } else if ((outcodeOut & OUT_BOTTOM) > 0) {
092                    x = x1 + (x2 - x1) * (ymin - y1)/(y2 - y1);
093                    y = ymin;
094                } else if ((outcodeOut & OUT_RIGHT) > 0) {
095                    y = y1 + (y2 - y1) * (xmax - x1)/(x2 - x1);
096                    x = xmax;
097                } else if ((outcodeOut & OUT_LEFT) > 0) {
098                    y = y1 + (y2 - y1) * (xmin - x1)/(x2 - x1);
099                    x = xmin;
100                }
101                if (outcodeOut == outcode0) {
102                    x1 = x;
103                    y1 = y;
104                    outcode0 = computeOutCode(x1, y1, xmin, ymin, xmax, ymax);
105                } else {
106                    x2 = x;
107                    y2 = y;
108                    outcode1 = computeOutCode(x2, y2, xmin, ymin, xmax, ymax);
109                }
110            }
111        }
112        while (!done);
113
114        if (accept) {
115            p1 = new Point((int) x1, (int) y1);
116            p2 = new Point((int) x2, (int) y2);
117            return true;
118        }
119        return false;
120    }
121
122    /**
123     * The outcode of the point.
124     * We cannot use {@link Rectangle#outcode} since it does not work with long ints.
125     * @param x X coordinate
126     * @param y Y coordinate
127     * @param xmin minimal X coordinate
128     * @param ymin minimal Y coordinate
129     * @param xmax maximal X coordinate
130     * @param ymax maximal Y coordinate
131     * @return outcode
132     */
133    private static int computeOutCode(long x, long y, long xmin, long ymin, long xmax, long ymax) {
134        int code = 0;
135        if (y > ymax) {
136            code |= OUT_TOP;
137        } else if (y < ymin) {
138            code |= OUT_BOTTOM;
139        }
140        if (x > xmax) {
141            code |= OUT_RIGHT;
142        } else if (x < xmin) {
143            code |= OUT_LEFT;
144        }
145        return code;
146    }
147}