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