001/** 002 * Copyright (c) 2011, The University of Southampton and the individual contributors. 003 * All rights reserved. 004 * 005 * Redistribution and use in source and binary forms, with or without modification, 006 * are permitted provided that the following conditions are met: 007 * 008 * * Redistributions of source code must retain the above copyright notice, 009 * this list of conditions and the following disclaimer. 010 * 011 * * Redistributions in binary form must reproduce the above copyright notice, 012 * this list of conditions and the following disclaimer in the documentation 013 * and/or other materials provided with the distribution. 014 * 015 * * Neither the name of the University of Southampton nor the names of its 016 * contributors may be used to endorse or promote products derived from this 017 * software without specific prior written permission. 018 * 019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR 023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 029 */ 030package org.openimaj.image.pixel.util; 031 032import java.util.ArrayList; 033import java.util.Iterator; 034import java.util.List; 035 036import org.openimaj.image.pixel.Pixel; 037 038/** 039 * Iterators for producing discrete pixel positions along a line. 040 * 041 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 042 * 043 */ 044public class LineIterators { 045 /** 046 * Pixel iterator based on Bresenham's algorithm for a line between two 047 * discrete endpoints. <b>The pixel returned by the iterator will always be 048 * the same object for efficiency; if you need to hold on to it, you should 049 * clone it first.</b> 050 * 051 * @param start 052 * the coordinate of the start point 053 * @param end 054 * the coordinate of the end point 055 * @return an iterator over the pixels in the line 056 */ 057 public static Iterator<Pixel> bresenham(final Pixel start, final Pixel end) { 058 return bresenham(start.x, start.y, end.x, end.y); 059 } 060 061 /** 062 * Pixel iterator based on Bresenham's algorithm for a line between two 063 * discrete endpoints. <b>The pixel returned by the iterator will always be 064 * the same object for efficiency; if you need to hold on to it, you should 065 * clone it first.</b> 066 * 067 * @param x0 068 * the x-ordinate of the start point 069 * @param y0 070 * the y-ordinate of the start point 071 * @param x1 072 * the x-ordinate of the end point 073 * @param y1 074 * the y-ordinate of the end point 075 * @return an iterator over the pixels in the line 076 */ 077 public static Iterator<Pixel> bresenham(final int x0, final int y0, final int x1, final int y1) { 078 return new Iterator<Pixel>() { 079 int x = x0; 080 int y = y0; 081 final int dx = Math.abs(x1 - x); 082 final int dy = Math.abs(y1 - y); 083 final int sx = (x < x1) ? 1 : -1; 084 final int sy = (y < y1) ? 1 : -1; 085 int err = dx - dy; 086 Pixel p = new Pixel(); 087 boolean finished = false; 088 089 @Override 090 public boolean hasNext() { 091 return !finished; 092 } 093 094 @Override 095 public Pixel next() { 096 p.x = x; 097 p.y = y; 098 099 if (x == x1 && y == y1) 100 finished = true; 101 102 final int e2 = 2 * err; 103 if (e2 > -dy) { 104 err = err - dy; 105 x = x + sx; 106 } 107 if (e2 < dx) { 108 err = err + dx; 109 y = y + sy; 110 } 111 112 return p; 113 } 114 115 @Override 116 public void remove() { 117 throw new UnsupportedOperationException(); 118 } 119 }; 120 } 121 122 /** 123 * Pixel iterator based on Bresenham's algorithm for a line starting at a 124 * given point, with an angle given by the provided x and y deltas. <b>The 125 * pixel returned by the iterator will always be the same object for 126 * efficiency; if you need to hold on to it, you should clone it first.</b> 127 * <b>Note: The returned iterator is infinite; that is it won't ever 128 * end.</b> 129 * 130 * @param x0 131 * the x-ordinate of the start point 132 * @param y0 133 * the y-ordinate of the start point 134 * @param fdx 135 * the x-gradient 136 * @param fdy 137 * the y-gradient 138 * @return an iterator over the pixels in the line 139 */ 140 public static Iterator<Pixel> bresenham(final int x0, final int y0, final float fdx, final float fdy) { 141 return new Iterator<Pixel>() { 142 int x = x0; 143 int y = y0; 144 final float dx = Math.abs(fdx); 145 final float dy = Math.abs(fdy); 146 final int sx = (fdx > 0) ? 1 : -1; 147 final int sy = (fdy > 0) ? 1 : -1; 148 float err = dx - dy; 149 Pixel p = new Pixel(); 150 151 @Override 152 public boolean hasNext() { 153 return true; 154 } 155 156 @Override 157 public Pixel next() { 158 p.x = x; 159 p.y = y; 160 161 final float e2 = 2 * err; 162 if (e2 > -dy) { 163 err = err - dy; 164 x = x + sx; 165 } 166 if (e2 < dx) { 167 err = err + dx; 168 y = y + sy; 169 } 170 171 return p; 172 } 173 174 @Override 175 public void remove() { 176 throw new UnsupportedOperationException(); 177 } 178 }; 179 } 180 181 /** 182 * Generate the pixels for the supercover of the line between two points. 183 * Based directly on code from Eugen Dedu. 184 * 185 * @see "http://lifc.univ-fcomte.fr/~dedu/projects/bresenham/index.html" 186 * 187 * @param x1 188 * the x-ordinate of the start point 189 * @param y1 190 * the y-ordinate of the start point 191 * @param x2 192 * the x-ordinate of the end point 193 * @param y2 194 * the y-ordinate of the end point 195 * 196 * @return the iterator of pixels representing the supercover line 197 */ 198 public static Iterator<Pixel> supercover(int x1, int y1, int x2, int y2) { 199 return supercoverAsList(x1, y1, x2, y2).iterator(); 200 } 201 202 /** 203 * Generate the pixels for the supercover of the line between two points. 204 * Based directly on code from Eugen Dedu. 205 * 206 * @see "http://lifc.univ-fcomte.fr/~dedu/projects/bresenham/index.html" 207 * 208 * @param x1 209 * the x-ordinate of the start point 210 * @param y1 211 * the y-ordinate of the start point 212 * @param x2 213 * the x-ordinate of the end point 214 * @param y2 215 * the y-ordinate of the end point 216 * 217 * @return the list of pixels representing the supercover line 218 */ 219 public static List<Pixel> supercoverAsList(int x1, int y1, int x2, int y2) { 220 final List<Pixel> pixels = new ArrayList<Pixel>(); 221 222 int ystep, xstep; // the step on y and x axis 223 int error; // the error accumulated during the increment 224 int errorprev; // *vision the previous value of the error variable 225 int y = y1, x = x1; // the line points 226 int ddy, ddx; // compulsory variables: the double values of dy and dx 227 int dx = x2 - x1; 228 int dy = y2 - y1; 229 230 pixels.add(new Pixel(x1, y1)); // first point 231 // NB the last point can't be here, because of its previous point (which 232 // has to be verified) 233 if (dy < 0) { 234 ystep = -1; 235 dy = -dy; 236 } else 237 ystep = 1; 238 if (dx < 0) { 239 xstep = -1; 240 dx = -dx; 241 } else 242 xstep = 1; 243 244 ddy = 2 * dy; // work with double values for full precision 245 ddx = 2 * dx; 246 if (ddx >= ddy) { // first octant (0 <= slope <= 1) 247 // compulsory initialization (even for errorprev, needed when 248 // dx==dy) 249 errorprev = error = dx; // start in the middle of the square 250 for (int i = 0; i < dx; i++) { // do not use the first point 251 // (already 252 // done) 253 x += xstep; 254 error += ddy; 255 if (error > ddx) { // increment y if AFTER the middle ( > ) 256 y += ystep; 257 error -= ddx; 258 // three cases (octant == right->right-top for directions 259 // below): 260 if (error + errorprev < ddx) // bottom square also 261 pixels.add(new Pixel(x, y - ystep)); 262 else if (error + errorprev > ddx) // left square also 263 pixels.add(new Pixel(x - xstep, y)); 264 else { // corner: bottom and left squares also 265 pixels.add(new Pixel(x, y - ystep)); 266 pixels.add(new Pixel(x - xstep, y)); 267 } 268 } 269 pixels.add(new Pixel(x, y)); 270 errorprev = error; 271 } 272 } else { // the same as above 273 errorprev = error = dy; 274 for (int i = 0; i < dy; i++) { 275 y += ystep; 276 error += ddx; 277 if (error > ddy) { 278 x += xstep; 279 error -= ddy; 280 if (error + errorprev < ddy) 281 pixels.add(new Pixel(x - xstep, y)); 282 else if (error + errorprev > ddy) 283 pixels.add(new Pixel(x, y - ystep)); 284 else { 285 pixels.add(new Pixel(x - xstep, y)); 286 pixels.add(new Pixel(x, y - ystep)); 287 } 288 } 289 pixels.add(new Pixel(x, y)); 290 errorprev = error; 291 } 292 } 293 294 return pixels; 295 } 296 297 /** 298 * Generate the pixels for the supercover of the line between two points. 299 * Based directly on code from Eugen Dedu. 300 * 301 * @see "http://lifc.univ-fcomte.fr/~dedu/projects/bresenham/index.html" 302 * 303 * @param start 304 * the coordinate of the start point 305 * @param end 306 * the coordinate of the end point 307 * 308 * @return the list of pixels representing the supercover line 309 */ 310 public static List<Pixel> supercoverAsList(Pixel start, Pixel end) { 311 return supercoverAsList(start.x, start.y, end.x, end.y); 312 } 313}