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     * @return true, if line is visible in the given clip region
062     */
063    private boolean cohenSutherland(long x1, long y1, long x2, long y2, long xmin, long ymin, long xmax, long ymax) {
064        int outcode0, outcode1, outcodeOut;
065        boolean accept = false;
066        boolean done = false;
067
068        outcode0 = computeOutCode(x1, y1, xmin, ymin, xmax, ymax);
069        outcode1 = computeOutCode(x2, y2, xmin, ymin, xmax, ymax);
070
071        do {
072            if ((outcode0 | outcode1) == 0) {
073                accept = true;
074                done = true;
075            } else if ((outcode0 & outcode1) > 0) {
076                done = true;
077            } else {
078                long x = 0, y = 0;
079                outcodeOut = outcode0 != 0 ? outcode0 : outcode1;
080                if ((outcodeOut & OUT_TOP) > 0) {
081                    x = x1 + (x2 - x1) * (ymax - y1)/(y2 - y1);
082                    y = ymax;
083                } else if ((outcodeOut & OUT_BOTTOM) > 0) {
084                    x = x1 + (x2 - x1) * (ymin - y1)/(y2 - y1);
085                    y = ymin;
086                } else if ((outcodeOut & OUT_RIGHT) > 0) {
087                    y = y1 + (y2 - y1) * (xmax - x1)/(x2 - x1);
088                    x = xmax;
089                } else if ((outcodeOut & OUT_LEFT) > 0) {
090                    y = y1 + (y2 - y1) * (xmin - x1)/(x2 - x1);
091                    x = xmin;
092                }
093                if (outcodeOut == outcode0) {
094                    x1 = x;
095                    y1 = y;
096                    outcode0 = computeOutCode(x1, y1, xmin, ymin, xmax, ymax);
097                } else {
098                    x2 = x;
099                    y2 = y;
100                    outcode1 = computeOutCode(x2, y2, xmin, ymin, xmax, ymax);
101                }
102            }
103        }
104        while (!done);
105
106        if (accept) {
107            p1 = new Point((int) x1, (int) y1);
108            p2 = new Point((int) x2, (int) y2);
109            return true;
110        }
111        return false;
112    }
113
114    /**
115     * The outcode of the point.
116     * We cannot use Rectangle.outcode since it does not work with long ints.
117     */
118    private static int computeOutCode(long x, long y, long xmin, long ymin, long xmax, long ymax) {
119        int code = 0;
120        if (y > ymax) {
121            code |= OUT_TOP;
122        } else if (y < ymin) {
123            code |= OUT_BOTTOM;
124        }
125        if (x > xmax) {
126            code |= OUT_RIGHT;
127        } else if (x < xmin) {
128            code |= OUT_LEFT;
129        }
130        return code;
131    }
132}