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}