001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017: /**
018: * @author Denis M. Kishenko
019: * @version $Revision$
020: */package org.apache.harmony.awt.gl;
021:
022: import java.awt.Rectangle;
023:
024: public class MultiRectAreaOp {
025:
026: /**
027: * Rectangle buffer capacity
028: */
029: public static final int RECT_CAPACITY = 16;
030:
031: /**
032: * If number of rectangle in MultiRectArea object less than MAX_SIMPLE simple algorithm applies
033: */
034: private static final int MAX_SIMPLE = 8;
035:
036: /**
037: * Create buffer
038: */
039: public static int[] createBuf(int capacity) {
040: if (capacity == 0) {
041: capacity = RECT_CAPACITY;
042: }
043: int[] buf = new int[capacity];
044: buf[0] = 1;
045: return buf;
046: }
047:
048: /**
049: * Checks buffer size and reallocate if necessary
050: */
051: public static int[] checkBufSize(int[] buf, int capacity) {
052: if (buf[0] + capacity >= buf.length) {
053: int length = buf[0]
054: + (capacity > RECT_CAPACITY ? capacity
055: : RECT_CAPACITY);
056: int[] tmp = new int[length];
057: System.arraycopy(buf, 0, tmp, 0, buf[0]);
058: buf = tmp;
059: }
060: buf[0] += capacity;
061: return buf;
062: }
063:
064: /**
065: * Region class provides basic functionlity for MultiRectArea objects to make logical operations
066: */
067: static class Region {
068:
069: int[] region;
070: int[] active;
071: int[] bottom;
072: int index;
073:
074: public Region(int[] region) {
075: this .region = region;
076: active = new int[RECT_CAPACITY];
077: bottom = new int[RECT_CAPACITY];
078: active[0] = 1;
079: bottom[0] = 1;
080: index = 1;
081: }
082:
083: void addActive(int index) {
084: int length = active[0];
085: active = checkBufSize(active, 4);
086: int i = 1;
087:
088: while (i < length) {
089: if (region[index] < active[i]) {
090: // Insert
091: System.arraycopy(active, i, active, i + 4, length
092: - i);
093: length = i;
094: break;
095: }
096: i += 4;
097: }
098: System.arraycopy(region, index, active, length, 4);
099:
100: }
101:
102: void findActive(int top, int bottom) {
103: while (index < region[0]) {
104: if (region[index + 1] > bottom) { // y1 > bottom
105: return;
106: }
107: if (region[index + 3] >= top) { // y2 >= top
108: addActive(index);
109: }
110: index += 4;
111: }
112: }
113:
114: void deleteActive(int bottom) {
115: int length = active[0];
116: for (int i = 1; i < length;) {
117: if (active[i + 3] == bottom) {
118: length -= 4;
119: if (i < length) {
120: System.arraycopy(active, i + 4, active, i,
121: length - i);
122: }
123: } else {
124: i += 4;
125: }
126: }
127: active[0] = length;
128: }
129:
130: void deleteActive() {
131: int length = active[0];
132: for (int i = length - 4; i > 0; i -= 4) {
133: if (active[i + 1] > active[i + 3]) {
134: length -= 4;
135: if (i < length) {
136: System.arraycopy(active, i + 4, active, i,
137: length - i);
138: }
139: }
140: }
141: active[0] = length;
142: }
143:
144: void createLevel(int[] level) {
145: int levelCount = 1;
146: int topIndex = 1;
147: int i = 1;
148: while (i < region[0]) {
149:
150: int top = region[i + 1];
151: int bottom = region[i + 3] + 1;
152: int j = topIndex;
153:
154: addTop: {
155: while (j < levelCount) {
156: if (level[j] == top) {
157: break addTop;
158: }
159: if (level[j] > top) {
160: System.arraycopy(level, j, level, j + 1,
161: levelCount - j);
162: break;
163: }
164: j++;
165: }
166:
167: level[j] = top;
168: levelCount++;
169: topIndex = j;
170: }
171:
172: addBottom: {
173: while (j < levelCount) {
174: if (level[j] == bottom) {
175: break addBottom;
176: }
177: if (level[j] > bottom) {
178: System.arraycopy(level, j, level, j + 1,
179: levelCount - j);
180: break;
181: }
182: j++;
183: }
184: ;
185:
186: level[j] = bottom;
187: levelCount++;
188: }
189:
190: i += 4;
191: }
192: level[0] = levelCount;
193: }
194:
195: static void sortOrdered(int[] src1, int[] src2, int[] dst) {
196: int length1 = src1[0];
197: int length2 = src2[0];
198: int count = 1;
199: int i1 = 1;
200: int i2 = 1;
201: int v1 = src1[1];
202: int v2 = src2[1];
203: while (true) {
204:
205: LEFT: {
206: while (i1 < length1) {
207: v1 = src1[i1];
208: if (v1 >= v2) {
209: break LEFT;
210: }
211: dst[count++] = v1;
212: i1++;
213: }
214: while (i2 < length2) {
215: dst[count++] = src2[i2++];
216: }
217: dst[0] = count;
218: return;
219: }
220:
221: RIGHT: {
222: while (i2 < length2) {
223: v2 = src2[i2];
224: if (v2 >= v1) {
225: break RIGHT;
226: }
227: dst[count++] = v2;
228: i2++;
229: }
230: while (i1 < length1) {
231: dst[count++] = src1[i1++];
232: }
233: dst[0] = count;
234: return;
235: }
236:
237: if (v1 == v2) {
238: dst[count++] = v1;
239: i1++;
240: i2++;
241: if (i1 < length1) {
242: v1 = src1[i1];
243: }
244: if (i2 < length2 - 1) {
245: v2 = src2[i2];
246: }
247: }
248: }
249: // UNREACHABLE
250: }
251:
252: }
253:
254: /**
255: * Intersection class provides intersection of two MultiRectAre aobjects
256: */
257: static class Intersection {
258:
259: static void intersectRegions(int[] reg1, int[] reg2,
260: MultiRectArea.RectCash dst, int height1, int height2) {
261:
262: Region d1 = new Region(reg1);
263: Region d2 = new Region(reg2);
264:
265: int[] level = new int[height1 + height2];
266: int[] level1 = new int[height1];
267: int[] level2 = new int[height2];
268: d1.createLevel(level1);
269: d2.createLevel(level2);
270: Region.sortOrdered(level1, level2, level);
271:
272: int top;
273: int bottom = level[1] - 1;
274: for (int i = 2; i < level[0]; i++) {
275:
276: top = bottom + 1;
277: bottom = level[i] - 1;
278:
279: d1.findActive(top, bottom);
280: d2.findActive(top, bottom);
281:
282: int i1 = 1;
283: int i2 = 1;
284:
285: while (i1 < d1.active[0] && i2 < d2.active[0]) {
286:
287: int x11 = d1.active[i1];
288: int x12 = d1.active[i1 + 2];
289: int x21 = d2.active[i2];
290: int x22 = d2.active[i2 + 2];
291:
292: if (x11 <= x21) {
293: if (x12 >= x21) {
294: if (x12 <= x22) {
295: dst
296: .addRectCashed(x21, top, x12,
297: bottom);
298: i1 += 4;
299: } else {
300: dst
301: .addRectCashed(x21, top, x22,
302: bottom);
303: i2 += 4;
304: }
305: } else {
306: i1 += 4;
307: }
308: } else {
309: if (x22 >= x11) {
310: if (x22 <= x12) {
311: dst
312: .addRectCashed(x11, top, x22,
313: bottom);
314: i2 += 4;
315: } else {
316: dst
317: .addRectCashed(x11, top, x12,
318: bottom);
319: i1 += 4;
320: }
321: } else {
322: i2 += 4;
323: }
324: }
325: }
326:
327: d1.deleteActive(bottom);
328: d2.deleteActive(bottom);
329: }
330: }
331:
332: static int[] simpleIntersect(MultiRectArea src1,
333: MultiRectArea src2) {
334: int[] rect1 = src1.rect;
335: int[] rect2 = src2.rect;
336: int[] rect = createBuf(0);
337:
338: int k = 1;
339: for (int i = 1; i < rect1[0];) {
340:
341: int x11 = rect1[i++];
342: int y11 = rect1[i++];
343: int x12 = rect1[i++];
344: int y12 = rect1[i++];
345:
346: for (int j = 1; j < rect2[0];) {
347:
348: int x21 = rect2[j++];
349: int y21 = rect2[j++];
350: int x22 = rect2[j++];
351: int y22 = rect2[j++];
352:
353: if (x11 <= x22 && x12 >= x21 && y11 <= y22
354: && y12 >= y21) {
355: rect = checkBufSize(rect, 4);
356: rect[k++] = x11 > x21 ? x11 : x21;
357: rect[k++] = y11 > y21 ? y11 : y21;
358: rect[k++] = x12 > x22 ? x22 : x12;
359: rect[k++] = y12 > y22 ? y22 : y12;
360: }
361: }
362: }
363:
364: rect[0] = k;
365: return rect;
366: }
367:
368: public static MultiRectArea getResult(MultiRectArea src1,
369: MultiRectArea src2) {
370:
371: if (src1 == null || src2 == null || src1.isEmpty()
372: || src2.isEmpty()) {
373: return new MultiRectArea();
374: }
375:
376: MultiRectArea.RectCash dst = new MultiRectArea.RectCash();
377:
378: if (!src1.sorted || !src2.sorted
379: || src1.getRectCount() <= MAX_SIMPLE
380: || src2.getRectCount() <= MAX_SIMPLE) {
381: dst.setRect(simpleIntersect(src1, src2), false);
382: } else {
383: Rectangle bounds1 = src1.getBounds();
384: Rectangle bounds2 = src2.getBounds();
385: Rectangle bounds3 = bounds1.intersection(bounds2);
386: if (bounds3.width > 0 && bounds3.height > 0) {
387: intersectRegions(src1.rect, src2.rect, dst,
388: bounds1.height + 2, bounds2.height + 2);
389: }
390: }
391:
392: return dst;
393: }
394:
395: }
396:
397: /**
398: * Union class provides union of two MultiRectAre aobjects
399: */
400: static class Union {
401:
402: int rx1, rx2;
403: int top, bottom;
404: MultiRectArea.RectCash dst;
405:
406: boolean next(Region d, int index) {
407: int x1 = d.active[index];
408: int x2 = d.active[index + 2];
409: boolean res = false;
410:
411: if (x2 < rx1 - 1) {
412: res = true;
413: dst.addRectCashed(x1, top, x2, bottom);
414: } else if (x1 > rx2 + 1) {
415: res = false;
416: dst.addRectCashed(rx1, top, rx2, bottom);
417: rx1 = x1;
418: rx2 = x2;
419: } else {
420: res = x2 <= rx2;
421: rx1 = Math.min(x1, rx1);
422: rx2 = Math.max(x2, rx2);
423: }
424:
425: // Top
426: if (d.active[index + 1] < top) {
427: dst.addRectCashed(x1, d.active[index + 1], x2, top - 1);
428: }
429: // Bottom
430: if (d.active[index + 3] > bottom) {
431: d.active[index + 1] = bottom + 1;
432: }
433: return res;
434: }
435:
436: void check(Region d, int index, boolean t) {
437: int x1 = d.active[index];
438: int x2 = d.active[index + 2];
439: // Top
440: if (d.active[index + 1] < top) {
441: dst.addRectCashed(x1, d.active[index + 1], x2, top - 1);
442: }
443: if (t) {
444: dst.addRectCashed(x1, top, x2, bottom);
445: }
446: // Bottom
447: if (d.active[index + 3] > bottom) {
448: d.active[index + 1] = bottom + 1;
449: }
450: }
451:
452: void unionRegions(int[] reg1, int[] reg2, int height1,
453: int height2) {
454: Region d1 = new Region(reg1);
455: Region d2 = new Region(reg2);
456:
457: int[] level = new int[height1 + height2];
458: int[] level1 = new int[height1];
459: int[] level2 = new int[height2];
460: d1.createLevel(level1);
461: d2.createLevel(level2);
462: Region.sortOrdered(level1, level2, level);
463:
464: bottom = level[1] - 1;
465: for (int i = 2; i < level[0]; i++) {
466:
467: top = bottom + 1;
468: bottom = level[i] - 1;
469:
470: d1.findActive(top, bottom);
471: d2.findActive(top, bottom);
472:
473: int i1 = 1;
474: int i2 = 1;
475: boolean res1, res2;
476:
477: if (d1.active[0] > 1) {
478: check(d1, 1, false);
479: rx1 = d1.active[1];
480: rx2 = d1.active[3];
481: i1 += 4;
482: res1 = false;
483: res2 = true;
484: } else if (d2.active[0] > 1) {
485: check(d2, 1, false);
486: rx1 = d2.active[1];
487: rx2 = d2.active[3];
488: i2 += 4;
489: res1 = true;
490: res2 = false;
491: } else {
492: continue;
493: }
494:
495: outer: while (true) {
496:
497: while (res1) {
498: if (i1 >= d1.active[0]) {
499: dst.addRectCashed(rx1, top, rx2, bottom);
500: while (i2 < d2.active[0]) {
501: check(d2, i2, true);
502: i2 += 4;
503: }
504: break outer;
505: }
506: res1 = next(d1, i1);
507: i1 += 4;
508: }
509:
510: while (res2) {
511: if (i2 >= d2.active[0]) {
512: dst.addRectCashed(rx1, top, rx2, bottom);
513: while (i1 < d1.active[0]) {
514: check(d1, i1, true);
515: i1 += 4;
516: }
517: break outer;
518: }
519: res2 = next(d2, i2);
520: i2 += 4;
521: }
522:
523: res1 = true;
524: res2 = true;
525: } // while
526:
527: d1.deleteActive(bottom);
528: d2.deleteActive(bottom);
529:
530: }
531: }
532:
533: static void simpleUnion(MultiRectArea src1, MultiRectArea src2,
534: MultiRectArea dst) {
535: if (src1.getRectCount() < src2.getRectCount()) {
536: simpleUnion(src2, src1, dst);
537: } else {
538: Subtraction.simpleSubtract(src1, src2, dst);
539: int pos = dst.rect[0];
540: int size = src2.rect[0] - 1;
541: dst.rect = checkBufSize(dst.rect, size);
542: System.arraycopy(src2.rect, 1, dst.rect, pos, size);
543: dst.resort();
544: }
545: }
546:
547: MultiRectArea getResult(MultiRectArea src1, MultiRectArea src2) {
548:
549: if (src1 == null || src1.isEmpty()) {
550: return new MultiRectArea(src2);
551: }
552:
553: if (src2 == null || src2.isEmpty()) {
554: return new MultiRectArea(src1);
555: }
556:
557: dst = new MultiRectArea.RectCash();
558:
559: if (!src1.sorted || !src2.sorted
560: || src1.getRectCount() <= MAX_SIMPLE
561: || src2.getRectCount() <= MAX_SIMPLE) {
562: simpleUnion(src1, src2, dst);
563: } else {
564: Rectangle bounds1 = src1.getBounds();
565: Rectangle bounds2 = src2.getBounds();
566: Rectangle bounds3 = bounds1.intersection(bounds2);
567:
568: if (bounds3.width < 0 || bounds3.height < 0) {
569: if (bounds1.y + bounds1.height < bounds2.y) {
570: dst.setRect(addVerRegion(src1.rect, src2.rect),
571: false);
572: } else if (bounds2.y + bounds2.height < bounds1.y) {
573: dst.setRect(addVerRegion(src2.rect, src1.rect),
574: false);
575: } else if (bounds1.x < bounds2.x) {
576: dst.setRect(addHorRegion(src1.rect, src2.rect),
577: false);
578: } else {
579: dst.setRect(addHorRegion(src2.rect, src1.rect),
580: false);
581: }
582: } else {
583: unionRegions(src1.rect, src2.rect,
584: bounds1.height + 2, bounds2.height + 2);
585: }
586: }
587:
588: return dst;
589: }
590:
591: int[] addVerRegion(int[] top, int[] bottom) {
592: int length = top[0] + bottom[0] - 1;
593: int[] dst = new int[length];
594: dst[0] = length;
595: System.arraycopy(top, 1, dst, 1, top[0] - 1);
596: System.arraycopy(bottom, 1, dst, top[0], bottom[0] - 1);
597: return dst;
598: }
599:
600: int[] addHorRegion(int[] left, int[] right) {
601: int count1 = left[0];
602: int count2 = right[0];
603: int[] dst = new int[count1 + count2 + 1];
604: int count = 1;
605: int index1 = 1;
606: int index2 = 1;
607:
608: int top1 = left[2];
609: int top2 = right[2];
610: int pos1, pos2;
611:
612: while (true) {
613:
614: if (index1 >= count1) {
615: System.arraycopy(right, index2, dst, count, count2
616: - index2);
617: count += count2 - index2;
618: break;
619: }
620: if (index2 >= count2) {
621: System.arraycopy(left, index1, dst, count, count1
622: - index1);
623: count += count1 - index1;
624: break;
625: }
626:
627: if (top1 < top2) {
628: pos1 = index1;
629: do {
630: index1 += 4;
631: } while (index1 < count1
632: && (top1 = left[index1 + 1]) < top2);
633: System.arraycopy(left, pos1, dst, count, index1
634: - pos1);
635: count += index1 - pos1;
636: continue;
637: }
638:
639: if (top1 > top2) {
640: pos2 = index2;
641: do {
642: index2 += 4;
643: } while (index2 < count2
644: && (top2 = right[index2 + 1]) < top1);
645: System.arraycopy(right, pos2, dst, count, index2
646: - pos2);
647: count += index2 - pos2;
648: continue;
649: }
650:
651: int top = top1;
652: pos1 = index1;
653: pos2 = index2;
654: do {
655: index1 += 4;
656: } while (index1 < count1
657: && (top1 = left[index1 + 1]) == top);
658: do {
659: index2 += 4;
660: } while (index2 < count2
661: && (top2 = right[index2 + 1]) == top);
662:
663: System.arraycopy(left, pos1, dst, count, index1 - pos1);
664: count += index1 - pos1;
665: System
666: .arraycopy(right, pos2, dst, count, index2
667: - pos2);
668: count += index2 - pos2;
669: }
670:
671: dst[0] = count;
672: return dst;
673: }
674:
675: }
676:
677: /**
678: * Subtraction class provides subtraction of two MultiRectAre aobjects
679: */
680: static class Subtraction {
681:
682: static void subtractRegions(int[] reg1, int[] reg2,
683: MultiRectArea.RectCash dst, int height1, int height2) {
684: Region d1 = new Region(reg1);
685: Region d2 = new Region(reg2);
686:
687: int[] level = new int[height1 + height2];
688: int[] level1 = new int[height1];
689: int[] level2 = new int[height2];
690: d1.createLevel(level1);
691: d2.createLevel(level2);
692: Region.sortOrdered(level1, level2, level);
693:
694: int top;
695: int bottom = level[1] - 1;
696: for (int i = 2; i < level[0]; i++) {
697:
698: top = bottom + 1;
699: bottom = level[i] - 1;
700:
701: d1.findActive(top, bottom);
702: if (d1.active[0] == 1) {
703: d2.deleteActive(bottom);
704: continue;
705: }
706:
707: d2.findActive(top, bottom);
708:
709: int i1 = 1;
710: int i2 = 1;
711:
712: int rx1 = 0;
713: int rx2 = 0;
714:
715: boolean next = true;
716:
717: while (true) {
718:
719: if (next) {
720: next = false;
721: if (i1 >= d1.active[0]) {
722: break;
723: }
724: // Bottom
725: d1.active[i1 + 1] = bottom + 1;
726: rx1 = d1.active[i1];
727: rx2 = d1.active[i1 + 2];
728: i1 += 4;
729: }
730:
731: if (i2 >= d2.active[0]) {
732: dst.addRectCashed(rx1, top, rx2, bottom);
733: for (int j = i1; j < d1.active[0]; j += 4) {
734: dst.addRectCashed(d1.active[j], top,
735: d1.active[j + 2], bottom);
736: d1.active[j + 1] = bottom + 1;
737: }
738: break;
739: }
740:
741: int x1 = d2.active[i2];
742: int x2 = d2.active[i2 + 2];
743:
744: if (rx1 < x1) {
745: if (rx2 >= x1) {
746: if (rx2 <= x2) {
747: // [-----------]
748: // [-------------]
749: dst.addRectCashed(rx1, top, x1 - 1,
750: bottom);
751: next = true;
752: } else {
753: // [-----------------]
754: // [------]
755: dst.addRectCashed(rx1, top, x1 - 1,
756: bottom);
757: rx1 = x2 + 1;
758: i2 += 4;
759: }
760: } else {
761: // [-----]
762: // [----]
763: dst.addRectCashed(rx1, top, rx2, bottom);
764: next = true;
765: }
766: } else {
767: if (rx1 <= x2) {
768: if (rx2 <= x2) {
769: // [------]
770: // [-----------]
771: next = true;
772: } else {
773: // [------------]
774: // [---------]
775: rx1 = x2 + 1;
776: i2 += 4;
777: }
778: } else {
779: // [----]
780: // [-----]
781: i2 += 4;
782: }
783: }
784:
785: }
786: d1.deleteActive();
787: d2.deleteActive(bottom);
788: }
789: }
790:
791: static void subtractRect(int x11, int y11, int x12, int y12,
792: int[] rect, int index, MultiRectArea dst) {
793:
794: for (int i = index; i < rect[0]; i += 4) {
795: int x21 = rect[i + 0];
796: int y21 = rect[i + 1];
797: int x22 = rect[i + 2];
798: int y22 = rect[i + 3];
799:
800: if (x11 <= x22 && x12 >= x21 && y11 <= y22
801: && y12 >= y21) {
802: int top, bottom;
803: if (y11 < y21) {
804: subtractRect(x11, y11, x12, y21 - 1, rect,
805: i + 4, dst);
806: top = y21;
807: } else {
808: top = y11;
809: }
810: if (y12 > y22) {
811: subtractRect(x11, y22 + 1, x12, y12, rect,
812: i + 4, dst);
813: bottom = y22;
814: } else {
815: bottom = y12;
816: }
817: if (x11 < x21) {
818: subtractRect(x11, top, x21 - 1, bottom, rect,
819: i + 4, dst);
820: }
821: if (x12 > x22) {
822: subtractRect(x22 + 1, top, x12, bottom, rect,
823: i + 4, dst);
824: }
825: return;
826: }
827: }
828: dst.addRect(x11, y11, x12, y12);
829: }
830:
831: static void simpleSubtract(MultiRectArea src1,
832: MultiRectArea src2, MultiRectArea dst) {
833: for (int i = 1; i < src1.rect[0]; i += 4) {
834: subtractRect(src1.rect[i + 0], src1.rect[i + 1],
835: src1.rect[i + 2], src1.rect[i + 3], src2.rect,
836: 1, dst);
837: }
838: dst.resort();
839: }
840:
841: public static MultiRectArea getResult(MultiRectArea src1,
842: MultiRectArea src2) {
843:
844: if (src1 == null || src1.isEmpty()) {
845: return new MultiRectArea();
846: }
847:
848: if (src2 == null || src2.isEmpty()) {
849: return new MultiRectArea(src1);
850: }
851:
852: MultiRectArea.RectCash dst = new MultiRectArea.RectCash();
853:
854: if (!src1.sorted || !src2.sorted
855: || src1.getRectCount() <= MAX_SIMPLE
856: || src2.getRectCount() <= MAX_SIMPLE) {
857: simpleSubtract(src1, src2, dst);
858: } else {
859: Rectangle bounds1 = src1.getBounds();
860: Rectangle bounds2 = src2.getBounds();
861: Rectangle bounds3 = bounds1.intersection(bounds2);
862:
863: if (bounds3.width > 0 && bounds3.height > 0) {
864: subtractRegions(src1.rect, src2.rect, dst,
865: bounds1.height + 2, bounds2.height + 2);
866: } else {
867: dst.setRect(src1.rect, true);
868: }
869: }
870:
871: return dst;
872: }
873:
874: }
875:
876: }
|