001    // License: GPL. For details, see LICENSE file.
002    package org.openstreetmap.josm.data.osm.visitor.paint;
003    
004    import static java.awt.geom.Rectangle2D.OUT_LEFT;
005    import static java.awt.geom.Rectangle2D.OUT_RIGHT;
006    import static java.awt.geom.Rectangle2D.OUT_TOP;
007    import static java.awt.geom.Rectangle2D.OUT_BOTTOM;
008    import java.awt.Point;
009    import 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     */
015    public 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    }