1 /* -------------------------------------------------------------------
2 GeoVISTA Center (Penn State, Dept. of Geography)
3 Java source file for the class FillOrderScan
4 Copyright (c), 2002, GeoVISTA Center
5 All Rights Reserved.
6 Original Author: Frank Hardisty
7 $Author: hardisty $
8 $Id: FillOrder.java,v 1.2 2003/04/25 20:14:41 hardisty Exp $
9 $Date: 2003/04/25 20:14:41 $
10 Reference: Document no:
11 ___ ___
12 ------------------------------------------------------------------- *
13
14 */
15
16
17 package edu.psu.geovista.app.spacefill;
18
19 import javax.swing.*;
20 import java.awt.*;
21 import java.awt.image.*;
22 import java.awt.geom.*;
23
24
25 public class FillOrder {
26
27 public static final int NULL_VALUE = Integer.MIN_VALUE;
28
29 public static final int FILL_ORDER_SCAN_LINE = 0;
30 public static final int FILL_ORDER_BOSTROPHEDON = 1;
31 public static final int FILL_ORDER_SPIRAL = 2;
32 public static final int FILL_ORDER_PEANO = 3;
33 public static final int FILL_ORDER_MAX = 3;
34
35 private static final String SHORT_DESC_SCAN_LINE = "Scan line";
36 private static final String SHORT_DESC_BOSTROPHEDON = "Bostrophedon";
37 private static final String SHORT_DESC_SPIRAL = "Spiral";
38 private static final String SHORT_DESC_PEANO = "Peano";
39
40 //H for heading
41 private static final int H_SOUTH = 0;
42 private static final int H_EAST = 1;
43 private static final int H_NORTH = 2;
44 private static final int H_WEST = 3;
45
46 //bostrophedon
47 //private final transient String name;
48
49 public FillOrder() {
50
51 }
52 public static String[] findFillOrderDescriptions() {
53 String[] desc = new String[FillOrder.FILL_ORDER_MAX+1];//zero based arrays
54 desc[FillOrder.FILL_ORDER_SCAN_LINE] = FillOrder.SHORT_DESC_SCAN_LINE;
55 desc[FillOrder.FILL_ORDER_BOSTROPHEDON] = FillOrder.SHORT_DESC_BOSTROPHEDON;
56 desc[FillOrder.FILL_ORDER_SPIRAL] = FillOrder.SHORT_DESC_SPIRAL;
57 desc[FillOrder.FILL_ORDER_PEANO] = FillOrder.SHORT_DESC_PEANO;
58 return desc;
59 }
60 /***
61 * this method returns a two-dimensional array int[i][j] where
62 * i = row
63 * j = column
64 * and the entry indicates the rank order.
65 */
66 public static int[][] findFillOrder(long nVals, int[][] fillOrder, int kind){
67 if (kind == FillOrder.FILL_ORDER_SCAN_LINE){
68 return getFillOrderScanLine(nVals, fillOrder);
69 } else if (kind == FillOrder.FILL_ORDER_BOSTROPHEDON) {
70 return getFillOrderBostrophedon(nVals, fillOrder);
71 } else if (kind == FillOrder.FILL_ORDER_SPIRAL) {
72 return getFillOrderSpiral(nVals, fillOrder);
73 } else if (kind == FillOrder.FILL_ORDER_PEANO) {
74 return getFillOrderPeano(nVals, fillOrder);
75 } else {
76 throw new IllegalArgumentException("Outside range of legal fill orders");
77 }
78 //return null;
79 }
80
81 private static int[][] makeArray(int[][] fillOrder, int sizeX, int sizeY) {
82 int[][] indexArray = null;
83 //dim array if necassary
84 if (fillOrder == null) {
85 indexArray = new int[sizeY][sizeX];
86 } else if (fillOrder.length == sizeY && fillOrder[0].length == sizeX) {
87 indexArray = fillOrder;
88 } else {
89 indexArray = new int[sizeY][sizeX];
90 }
91 return indexArray;
92 }
93
94 //the second arg is optional. if included and the right size, will be used
95 //if not, new array
96 private static int[][] getFillOrderScanLine(long nVals, int[][] fillOrder){
97 //start with a square array
98 double root = Math.sqrt((double)nVals);
99 int sizeX = (int)Math.ceil(root);
100
101 //now trim
102 long sizeArray = sizeX * sizeX;
103 long leftOver = sizeArray - nVals;
104 //how many rows is this?
105 double divide = ((double)leftOver/(double)sizeX);
106 double whole = Math.floor(divide);
107 int numRows = (int)whole;
108 int sizeY = sizeX - numRows;
109 int[][] indexArray = FillOrder.makeArray(fillOrder, sizeX, sizeY);
110
111 int counter = 0;
112 for (int pixelY = sizeY-1; pixelY > -1; pixelY--) {
113 for (int pixelX = 0; pixelX < sizeX; pixelX++) {
114 if (counter < nVals){
115 indexArray[pixelY][pixelX] = counter;
116 } else {
117 indexArray[pixelY][pixelX] = FillOrder.NULL_VALUE;
118 }
119 counter++;
120
121 }
122 }
123 return indexArray;
124 }//end method
125
126 //the second arg is optional. if included and the right size, will be used
127 //if not, new array
128 private static int[][] getFillOrderBostrophedon(long nVals, int[][] fillOrder){
129 //start with a square array
130 double root = Math.sqrt((double)nVals);
131 int sizeX = (int)Math.ceil(root);
132
133 //now trim
134 long sizeArray = sizeX * sizeX;
135 long leftOver = sizeArray - nVals;
136 //how many rows is this?
137 double divide = ((double)leftOver/(double)sizeX);
138 double whole = Math.floor(divide);
139 int numRows = (int)whole;
140 int sizeY = sizeX - numRows;
141 int[][] indexArray = FillOrder.makeArray(fillOrder, sizeX, sizeY);
142
143 int counter = 0;
144 for (int pixelY = 0; pixelY < sizeY; pixelY++) {
145 double remainder = (double)pixelY / 2;
146 boolean isOdd;
147 if (remainder == 0) {
148 isOdd = false;
149 } else {
150 isOdd = true;
151 }
152 if (isOdd) {
153 for (int pixelX = sizeX-1; pixelX > -1; pixelX--) {
154 if (counter < nVals){
155 indexArray[pixelY][pixelX] = counter;
156 } else {
157 indexArray[pixelY][pixelX] = FillOrder.NULL_VALUE;
158 }
159 counter++;
160 }//next pixelX
161 } else {
162 for (int pixelX = 0; pixelX < sizeX; pixelX++) {
163 if (counter < nVals){
164 indexArray[pixelY][pixelX] = counter;
165 } else {
166 indexArray[pixelY][pixelX] = FillOrder.NULL_VALUE;
167 }
168 counter++;
169 }//next pixelX
170 }//end if odd
171 }
172 return indexArray;
173 }//end method
174
175
176 //the second arg is optional. if included and the right size, will be used
177 //if not, new array
178 private static int[][] getFillOrderSpiral(long nVals, int[][] fillOrder){
179 //start with a square array
180 double root = Math.sqrt((double)nVals);
181 int sizeY = (int)Math.ceil(root);
182
183 //now trim
184 long sizeArray = sizeY * sizeY;
185 long leftOver = sizeArray - nVals;
186 //how many rows is this?
187 double divide = ((double)leftOver/(double)sizeY);
188 double whole = Math.floor(divide);
189 int numCols = (int)whole;
190 int sizeX = sizeY - numCols;
191 int[][] indexArray = FillOrder.makeArray(fillOrder, sizeX, sizeY);
192
193 int counter = 0;
194 int pixelX = 0;
195 int pixelY = 0;
196 //find our start point
197 double half = (double)sizeX/2;
198 half = Math.ceil(half);
199 pixelX = (int)half -1;
200
201 half = (double)sizeY/2;
202 half = Math.ceil(half);
203 pixelY = (int)half -1;
204
205 indexArray[pixelY][pixelX] = counter;
206 counter++;
207 int nSpaces = sizeX * sizeY;
208
209 int heading = FillOrder.H_SOUTH;
210
211 int currSize = 1;
212
213 while (counter < nSpaces) {
214 try{
215 if (counter == (currSize * currSize) ){
216 //go one unit forward in the current heading, then turn.
217 pixelX = FillOrder.findNextSpiralPixelX(pixelX,heading);
218 pixelY = FillOrder.findNextSpiralPixelY(pixelY,heading);
219 indexArray[pixelY][pixelX] = counter;
220 counter++;
221 //heading = FillOrder.findNextHeading(heading);
222 currSize++;
223 } else {
224 // turn. then go currSize -1 units in the new heading,
225 heading = FillOrder.findNextHeading(heading);
226 for (int i = 1; i < currSize; i++){
227 pixelX = FillOrder.findNextSpiralPixelX(pixelX,heading);
228 pixelY = FillOrder.findNextSpiralPixelY(pixelY,heading);
229 if (counter < nVals){
230 indexArray[pixelY][pixelX] = counter;
231 } else {
232 indexArray[pixelY][pixelX] = FillOrder.NULL_VALUE;
233 }
234
235 counter++;
236 if (counter >= nSpaces) {
237 return indexArray;
238 }
239 }//next i
240 //heading = FillOrder.findNextHeading(heading);
241 }//end if
242 } catch (Exception ex) {
243 System.out.println("Help! ");
244 System.out.println("PixelX = " + pixelX);
245 System.out.println("PixelY = " + pixelY);
246 System.out.println("heading " + heading);
247 System.out.println("counter " + counter);
248 ex.printStackTrace();
249 }
250 }//end while
251
252 return indexArray;
253 }//end method
254
255 private static int findNextHeading(int heading) {
256 int newHeading = 0;
257 if (heading <= 2) {
258 newHeading = heading + 1;
259 }
260 return newHeading;
261 }
262
263 private static int findNextSpiralPixelX(int pixelX, int heading) {
264 int newX = pixelX;
265 if (heading == FillOrder.H_EAST) {
266 newX = newX + 1;
267 } else if (heading == FillOrder.H_WEST ){
268 newX = newX - 1;
269 }
270 return newX;
271 }
272 private static int findNextSpiralPixelY(int pixelY, int heading) {
273 int newY = pixelY;
274 if (heading == FillOrder.H_SOUTH ){
275 newY = newY + 1;
276 } else if (heading == FillOrder.H_NORTH) {
277 newY = newY - 1;
278 }
279 return newY;
280 }
281
282 //the second arg is optional. if included and the right size, will be used
283 //if not, new array
284 private static int[][] getFillOrderPeano(long nVals, int[][] fillOrder){
285 //start with a square array
286 int pow = 0; //pow is the number of nested "z" patterns
287 int nSpaces = 1; //total number of spaces in array
288 Double d = null;
289 while (nSpaces < nVals) {
290 pow++;
291 d = new Double(Math.pow(4,(double)pow));
292 nSpaces = d.intValue();
293 }
294
295 int sizeX = FillOrder.findWidthPeano(nVals,pow);
296 int sizeY = FillOrder.findHeightPeano(nVals,pow);
297 nSpaces = sizeX * sizeY;
298 int[][] indexArray = FillOrder.makeArray(fillOrder, sizeX, sizeY);
299
300 int counter = 0;
301 int pixelX = 0;
302 int pixelY = 0;
303 //find our start point
304
305
306
307 try{
308 Integer count = new Integer(counter);
309 FillOrder.setIndexesPeano(indexArray,pixelY,pixelX,counter,pow, (int)nVals);
310 //indexArray[pixelY][pixelX] = counter;
311
312 /*
313 d = new Double(Math.pow(2,pow));
314 powSideLen = d.intValue();
315 for (int i = 0; i < powSideLen; i++) {
316 for (int j = 0; j < powSideLen; j++) {
317
318 }
319 }
320 */
321
322 } catch (Exception ex) {
323 System.out.println("Help! ");
324 System.out.println("PixelX = " + pixelX);
325 System.out.println("PixelY = " + pixelY);
326 System.out.println("pow " + pow);
327 System.out.println("counter " + counter);
328 ex.printStackTrace();
329 }//end try
330
331 return indexArray;
332 }//end method
333
334 private static int findWidthPeano(long nVals, int pow) {
335 if (nVals == 1) {
336 return 1;
337 }
338 Double d = null;
339 int width = 0;
340 long valsCopy = nVals;
341 d = new Double(Math.pow(4,pow-1));
342 int nForThisPow = d.intValue();
343 int div = (int)valsCopy / nForThisPow;
344 valsCopy = valsCopy - (div * nForThisPow);
345
346 //take this by cases
347 if (div == 0) {
348 width = findWidthPeano(valsCopy,pow-1);
349 } else if (div == 1){
350 if (pow <= 1) {
351 width = 1;
352 } else {
353 width = pow + findWidthPeano(valsCopy,pow-1);
354 }
355 } else if (div == 2){
356 d = new Double(Math.pow(2,(double)pow));
357 width = d.intValue();
358 } else if (div == 3){
359 d = new Double(Math.pow(2,(double)pow));
360 width = d.intValue();
361 } else if (div == 4){
362 d = new Double(Math.pow(2,(double)pow));
363 width = d.intValue();
364 }
365
366 return width;
367 }
368
369 private static int findHeightPeano(long nVals, int pow) {
370 if (nVals == 1) {
371 return 1;
372 }
373 Double d = null;
374 int height = 0;
375 long valsCopy = nVals;
376 d = new Double(Math.pow(4,pow-1));
377 int nForThisPow = d.intValue();
378 int div = (int)valsCopy / nForThisPow;
379 valsCopy = valsCopy - (div * nForThisPow);
380
381 //take this by cases
382 if (div == 0) {
383 height = findHeightPeano(valsCopy,pow-1);
384 } else if (div == 1){
385 d = new Double(Math.pow(2,(double)pow-1));
386 height = d.intValue();
387 } else if (div == 2){
388 if (pow <= 1) {
389 height = 1;
390 } else {
391 height = pow + findHeightPeano(valsCopy,pow-1);
392 }
393 } else if (div == 3){
394 d = new Double(Math.pow(2,(double)pow));
395 height = d.intValue();
396 } else if (div == 4){
397 d = new Double(Math.pow(2,(double)pow));
398 height = d.intValue();
399 }
400
401 return height;
402 }
403
404 private static void setIndexesPeano(int[][] indexArray,
405 int pixelY, int pixelX,
406 int currPlace, int pow, int nVals){
407
408
409 if (pow == 0) {//recusion bottoms out
410 if (pixelY < indexArray.length && pixelX < indexArray[0].length) {
411 if (currPlace < nVals) {
412 indexArray[pixelY][pixelX] = currPlace;
413 } else {
414 indexArray[pixelY][pixelX] = FillOrder.NULL_VALUE;
415 }
416 }
417 } else {
418 Double d = null;
419 //four cases
420 //need to know the length of a side
421 d = new Double(Math.pow(2,pow-1));
422 int lenPow = d.intValue();
423 //and the number of spaces occupied by sub-boxes
424 d = new Double(Math.pow(4,pow-1));
425 int sizeBox = d.intValue();
426
427 //first case, nw box
428 setIndexesPeano(indexArray,pixelY,pixelX,currPlace,pow-1, nVals);
429 currPlace = currPlace + sizeBox;
430
431 //second case, ne box
432 pixelX = pixelX + lenPow;
433 setIndexesPeano(indexArray,pixelY,pixelX,currPlace,pow-1, nVals);
434 currPlace = currPlace + sizeBox;
435
436 //third case, sw box
437 pixelX = pixelX - lenPow;
438 pixelY = pixelY + lenPow;
439 setIndexesPeano(indexArray,pixelY,pixelX,currPlace,pow-1, nVals);
440 currPlace = currPlace + sizeBox;
441
442 //fourth case, se box
443 pixelX = pixelX + lenPow;
444 setIndexesPeano(indexArray,pixelY,pixelX,currPlace,pow-1, nVals);
445 currPlace = currPlace + sizeBox;
446 }
447
448 }
449 }
This page was automatically generated by Maven