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