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}