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                (long) clipBounds.x + clipBounds.width,
042                (long) clipBounds.y + clipBounds.height);
043    }
044
045    /**
046     * @return start point of the clipped line
047     */
048    public Point getP1() {
049        return p1;
050    }
051
052    /**
053     * @return end point of the clipped line
054     */
055    public Point getP2() {
056        return p2;
057    }
058
059    /**
060     * Cohen–Sutherland algorithm.
061     * See <a href="https://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm">Wikipedia article</a>
062     * @param x1 X coordinate of first point
063     * @param y1 Y coordinate of first point
064     * @param x2 X coordinate of second point
065     * @param y2 Y coordinate of second point
066     * @param xmin minimal X coordinate
067     * @param ymin minimal Y coordinate
068     * @param xmax maximal X coordinate
069     * @param ymax maximal Y coordinate
070     * @return true, if line is visible in the given clip region
071     */
072    private boolean cohenSutherland(long x1, long y1, long x2, long y2, long xmin, long ymin, long xmax, long ymax) {
073        int outcode0, outcode1, outcodeOut;
074        boolean accept = false;
075        boolean done = false;
076
077        outcode0 = computeOutCode(x1, y1, xmin, ymin, xmax, ymax);
078        outcode1 = computeOutCode(x2, y2, xmin, ymin, xmax, ymax);
079
080        do {
081            if ((outcode0 | outcode1) == 0) {
082                accept = true;
083                done = true;
084            } else if ((outcode0 & outcode1) > 0) {
085                done = true;
086            } else {
087                long x = 0;
088                long y = 0;
089                outcodeOut = outcode0 != 0 ? outcode0 : outcode1;
090                if ((outcodeOut & OUT_TOP) != 0) {
091                    x = x1 + (x2 - x1) * (ymax - y1)/(y2 - y1);
092                    y = ymax;
093                } else if ((outcodeOut & OUT_BOTTOM) != 0) {
094                    x = x1 + (x2 - x1) * (ymin - y1)/(y2 - y1);
095                    y = ymin;
096                } else if ((outcodeOut & OUT_RIGHT) != 0) {
097                    y = y1 + (y2 - y1) * (xmax - x1)/(x2 - x1);
098                    x = xmax;
099                } else if ((outcodeOut & OUT_LEFT) != 0) {
100                    y = y1 + (y2 - y1) * (xmin - x1)/(x2 - x1);
101                    x = xmin;
102                }
103                if (outcodeOut == outcode0) {
104                    x1 = x;
105                    y1 = y;
106                    outcode0 = computeOutCode(x1, y1, xmin, ymin, xmax, ymax);
107                } else {
108                    x2 = x;
109                    y2 = y;
110                    outcode1 = computeOutCode(x2, y2, xmin, ymin, xmax, ymax);
111                }
112            }
113        }
114        while (!done);
115
116        if (accept) {
117            p1 = new Point((int) x1, (int) y1);
118            p2 = new Point((int) x2, (int) y2);
119            return true;
120        }
121        return false;
122    }
123
124    /**
125     * The outcode of the point.
126     * We cannot use {@link Rectangle#outcode} since it does not work with long ints.
127     * @param x X coordinate
128     * @param y Y coordinate
129     * @param xmin minimal X coordinate
130     * @param ymin minimal Y coordinate
131     * @param xmax maximal X coordinate
132     * @param ymax maximal Y coordinate
133     * @return outcode
134     */
135    private static int computeOutCode(long x, long y, long xmin, long ymin, long xmax, long ymax) {
136        int code = 0;
137        if (y > ymax) {
138            code |= OUT_TOP;
139        } else if (y < ymin) {
140            code |= OUT_BOTTOM;
141        }
142        if (x > xmax) {
143            code |= OUT_RIGHT;
144        } else if (x < xmin) {
145            code |= OUT_LEFT;
146        }
147        return code;
148    }
149}