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