001 /* 002 * ArrayRotation 003 * 004 * Copyright (c) 2000, 2001, 2002 Marco Schmidt <marcoschmidt@users.sourceforge.net> 005 * All rights reserved. 006 */ 007 008 package net.sourceforge.jiu.util; 009 010 /** 011 * Provides static methods to rotate (in steps of 90 degrees), flip and mirror array elements. 012 * The image data is expected to be available as an array of integer values, being stored as rows top-to-bottom. 013 * Within each row, the data is laid out from left to right. 014 * This class may also been useful for transposing matrices. 015 * <p> 016 * The rotation by 90 and 270 degrees in-place (i.e., without using a 017 * second array to copy to) is based on ideas and code developed 018 * by others. 019 * See <a target="_top" href="http://facweb.cs.depaul.edu/tchristopher/rotates.htm">Rotation of arrays</a> 020 * by Thomas W. Christopher. 021 * <p> 022 * I also got very useful advice from Hans-Bernhard Broeker and others in 023 * <a href="news:comp.graphics.algorithms">comp.graphics.algorithms</a>. 024 * There is a thread titled <em>In-place rotation of pixel images</em> starting Oct 11, 2000. 025 * <p> 026 * <em>Note: This class should be adjusted if Java ever supports genericity. 027 * Then rotation functionality could be provided for all kinds of arrays.</em> 028 * @author Hans-Bernhard Broeker 029 * @author Thomas W. Christopher 030 * @author Marco Schmidt 031 */ 032 public class ArrayRotation 033 { 034 private ArrayRotation() 035 { 036 } 037 038 /** 039 * This method checks several properties of the arguments. 040 * If any of the properties is not fulfilled, an explaining 041 * {@link java.lang.IllegalArgumentException} is thrown. 042 * Otherwise, nothing happens. 043 * This method is supposed to be called at the beginning of several 044 * other methods in this class. 045 * Properties checked: 046 * <ul> 047 * <li><code>pixels</code> is non-null</li> 048 * <li><code>width</code> and <code>height</code> are larger than zero</li> 049 * <li>number of elements in <code>pixels</code> is at least <code>width</code> times <code>height</code></li> 050 * </ul> 051 */ 052 public static void checkPixelArray(int[] pixels, int width, int height) 053 { 054 if (pixels == null) 055 { 056 throw new IllegalArgumentException("Error -- the pixel array must be initialized."); 057 } 058 if (width < 1 || height < 1) 059 { 060 throw new IllegalArgumentException("Error -- width and height must be >= 1 (width=" + 061 width + ", height=" + height + ")."); 062 } 063 if (pixels.length < width * height) 064 { 065 throw new IllegalArgumentException("Error -- pixel array must have at least width * height pixels, has only " + 066 pixels.length + " pixels."); 067 } 068 } 069 070 /** 071 * Flips the argument image, i.e., the top line becomes the bottom line 072 * and vice versa, etc. 073 * This method first checks the validity of the arguments that define the image 074 * by a call to {@link checkPixelArray}. 075 * Then the image data is flipped in place, no additional memory is required. 076 * Note that after applying this operation twice you will get the original 077 * image back. 078 * 079 * @param pixels the array of pixels that form the image to be flipped 080 * @param width the horizontal resolution of the image; must be larger than 0 081 * @param height the vertical resolution of the image; must be larger than 0 082 * @exception IllegalArgumentException if the arguments are invalid 083 */ 084 private static final void flipInPlace(int[] pixels, int width, int height) 085 { 086 checkPixelArray(pixels, width, height); 087 int y1 = 0; 088 int y2 = height - 1; 089 while (y1 < y2) 090 { 091 int offset1 = y1 * width; 092 int offset2 = y2 * width; 093 for (int x = 0; x < width; x++) 094 { 095 int temp = pixels[offset1]; 096 pixels[offset1++] = pixels[offset2]; 097 pixels[offset2++] = temp; 098 } 099 } 100 } 101 102 private static final int[] flip(int[] pixels, int width, int height) 103 { 104 checkPixelArray(pixels, width, height); 105 int[] result = new int[width * height]; 106 for (int y1 = 0, y2 = height - 1; y1 < height; y1++, y2--) 107 { 108 int offset1 = y1 * width; 109 int offset2 = y2 * width; 110 for (int x = 0; x < width; x++) 111 { 112 result[offset2++] = pixels[offset1++]; 113 } 114 } 115 return result; 116 } 117 118 /** 119 * Flips the image given by the arguments. 120 * The inPlace argument determines if the pixels array is modified or not. 121 * If inPlace is true, no additional array is allocated. 122 * Otherwise, an array of width times height items is allocated and the 123 * flipped image will be stored in this array. 124 * @param inPlace if <code>true</code> all work is done on the <code>pixels</code> array; 125 * otherwise, a second array is allocated and the <code>pixels</code> array 126 * remains unmodified 127 * @param pixels the array of pixels that form the image to be flipped 128 * @param width the horizontal resolution of the image; must be larger than 0 129 * @param height the vertical resolution of the image; must be larger than 0 130 * @return the flipped image as int array; equals <code>pixels</code> if 131 * <code>inPlace</code> is true 132 * @exception IllegalArgumentException if the pixel resolution 133 * is invalid or the pixels array is not initialized or its length smaller 134 * than <code>width</code> times <code>height</code> 135 */ 136 public static final int[] flip(boolean inPlace, int[] pixels, int width, int height) 137 { 138 if (inPlace) 139 { 140 flipInPlace(pixels, width, height); 141 return pixels; 142 } 143 else 144 { 145 return flip(pixels, width, height); 146 } 147 } 148 149 /** 150 * Mirrors the image given by the arguments. 151 * For each row, pixels are swapped, leftmost and rightmost, 152 * second-leftmost and second-rightmost, and so on. 153 * The inPlace argument determines if the pixels array is modified or not. 154 * If inPlace is true, no additional array is used. 155 * Otherwise, an array of width times height items is allocated and the 156 * mirrored image will be stored in this array. 157 * @param inPlace if <code>true</code> all work is done on the <code>pixels</code> array; 158 * otherwise, a second array is allocated and the <code>pixels</code> array 159 * remains unmodified 160 * @param pixels the array of pixels that form the image to be flipped 161 * @param width the horizontal resolution of the image; must be larger than 0 162 * @param height the vertical resolution of the image; must be larger than 0 163 * @return the flipped image as int array; equals <code>pixels</code> if 164 * <code>inPlace</code> is true 165 * @exception IllegalArgumentException if the pixel resolution 166 * is invalid or the pixels array is not initialized or its length smaller 167 * than <code>width</code> times <code>height</code> 168 */ 169 public static int[] mirror(boolean inPlace, int[] pixels, int width, int height) 170 { 171 if (inPlace) 172 { 173 //flipInPlace(pixels, width, height); 174 return pixels; 175 } 176 else 177 { 178 return pixels;//flip(pixels, width, height); 179 } 180 } 181 182 /** 183 * Rotates the argument image by 180 degrees. 184 * The resulting image will have exactly the same pixel resolution. 185 * Note that this operation is the same as two consecutive 90 degree 186 * rotations in the same direction. 187 * Another way of implementing a 180 degree rotation is first flipping 188 * and then mirroring the original image (or vice versa). 189 * <p> 190 * If <code>inPlace</code> is true, the rotation is done on the 191 * argument <code>pixels</code> array. 192 * Otherwise a new array of sufficient length is allocated and the 193 * rotated image will be stored in this new array, not modifying the 194 * content of the <code>pixels</code> array. 195 * <p> 196 * @param inPlace determines whether the rotated image is written to the argument array 197 * @param pixels the array of pixels that form the image to be rotated 198 * @param width the horizontal resolution of the image; must be larger than 0 199 * @param height the vertical resolution of the image; must be larger than 0 200 * @return the flipped image as int array; equals <code>pixels</code> if 201 * <code>inPlace</code> is true 202 * @exception IllegalArgumentException if the pixel resolution 203 * is invalid or the pixels array is not initialized or its length smaller 204 * than <code>width</code> times <code>height</code> 205 */ 206 public static int[] rotate180(boolean inPlace, int[] pixels, int width, int height) 207 { 208 if (inPlace) 209 { 210 rotateInPlace180(pixels, width, height); 211 return pixels; 212 } 213 else 214 { 215 return pixels;//rotateToCopy180(pixels, width, height); 216 } 217 } 218 219 private static int[] rotate180(int[] pixels, int width, int height) 220 { 221 checkPixelArray(pixels, width, height); 222 int numPixels = width * height; 223 int[] result = new int[numPixels]; 224 int x1 = 0; 225 int x2 = numPixels - 1; 226 while (x1 < x2) 227 { 228 int temp = pixels[x1]; 229 pixels[x1++] = pixels[x2]; 230 pixels[x2--] = temp; 231 } 232 return result; 233 } 234 235 private static void rotateInPlace180(int[] pixels, int width, int height) 236 { 237 checkPixelArray(pixels, width, height); 238 int x1 = 0; 239 int x2 = width * height - 1; 240 while (x1 < x2) 241 { 242 int temp = pixels[x1]; 243 pixels[x1++] = pixels[x2]; 244 pixels[x2--] = temp; 245 } 246 } 247 248 private static void rotateToArray90Left(int[] src, int[] dest, int width, int height) 249 { 250 //System.out.println("90 left (to copy) width=" + width + " height=" + height + " dest.length=" + dest.length); 251 checkPixelArray(src, width, height); 252 checkPixelArray(dest, width, height); 253 if (src == dest) 254 { 255 throw new IllegalArgumentException("rotate90Left assumes that the argument arrays are not the same."); 256 } 257 int x_ = -1; 258 int y_ = -1; 259 try 260 { 261 int offset = 0; 262 for (int y = 0; y < height; y++) 263 { 264 for (int x = 0; x < width; x++) 265 { 266 x_ = x; 267 y_ = y; 268 dest[(width - x - 1) * height + y] = src[offset++]; 269 } 270 } 271 } 272 catch (ArrayIndexOutOfBoundsException ae) 273 { 274 System.out.println("bounds; x=" + x_ + " y=" + y_); 275 } 276 } 277 278 private static int pred(int k, int width, int height) 279 { 280 return (k % height) * width + k / height; 281 } 282 283 private static void rotateInPlace90Left(int[] pixels, int width, int height) 284 { 285 //System.out.println("90 left in-place"); 286 int LxM = height * width; 287 int i, j, k, stillToMove; 288 for (i = 0, stillToMove = LxM; stillToMove > 0; i++) 289 { 290 for (j = pred(i, width, height); j > i; j = pred(j, width, height)) 291 ; 292 if (j < i) 293 { 294 continue; 295 } 296 for (k = i, j = pred(i, width, height); j != i; k = j, 297 j = pred(j, width, height)) 298 { 299 //exchange(k,j); 300 int temp = pixels[k]; 301 pixels[k] = pixels[j]; 302 pixels[j] = temp; 303 --stillToMove; 304 } 305 --stillToMove; 306 } 307 } 308 309 public static void rotate90Left(int width, int height, byte[] src, int srcOffset, byte[] dest, int destOffset) 310 { 311 int offset = srcOffset; 312 for (int y = 0; y < height; y++) 313 { 314 for (int x = 0; x < width; x++) 315 { 316 dest[destOffset + (width - x - 1) * height + y] = src[offset++]; 317 } 318 } 319 } 320 321 public static void rotate90Right(int width, int height, byte[] src, int srcOffset, byte[] dest, int destOffset) 322 { 323 int offset = srcOffset; 324 for (int y = 0; y < height; y++) 325 { 326 for (int x = 0; x < width; x++) 327 { 328 dest[destOffset + x * height + (height - 1 - y)] = src[offset++]; 329 } 330 } 331 } 332 333 public static void rotate180(int width, int height, byte[] src, int srcOffset, byte[] dest, int destOffset) 334 { 335 int n = width * height; 336 destOffset = destOffset + n - 1; 337 while (n-- > 0) 338 { 339 dest[destOffset--] = src[srcOffset++]; 340 } 341 } 342 343 /* public static int[] rotate90Left(boolean inPlace, int[] pixels, int width, 344 int height) throws IllegalArgumentException 345 { 346 if (inPlace) 347 { 348 rotateInPlace90Left(pixels, width, height); 349 return pixels; 350 } 351 else 352 { 353 int[] dest = new int[width * height]; 354 rotateToArray90Left(pixels, dest, width, height); 355 return dest; 356 } 357 }*/ 358 359 private static void rotateInPlace90Right(int[] pixels, int width, int height) 360 { 361 //System.out.println("90 right in-place (empty)"); 362 throw new IllegalArgumentException("This method not implemented yet."); 363 } 364 365 private static int[] rotate90Right(int[] pixels, int width, int height) 366 { 367 int[] result = new int[width * height]; 368 int offset = 0; 369 for (int y = 0; y < height; y++) 370 { 371 int srcOffset = height - 1 - y; 372 for (int x = 0; x < width; x++) 373 { 374 result[srcOffset] = pixels[offset++]; 375 srcOffset += height; 376 } 377 } 378 return result; 379 } 380 381 public static int[] rotate90Right(boolean inPlace, int[] pixels, int width, int height) 382 { 383 if (inPlace) 384 { 385 rotateInPlace90Right(pixels, width, height); 386 return pixels; 387 } 388 else 389 { 390 return rotate90Right(pixels, width, height); 391 } 392 } 393 }