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