| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| /** |
| * @author Denis M. Kishenko |
| * @version $Revision$ |
| */ |
| package org.apache.harmony.awt.gl; |
| |
| import java.awt.Rectangle; |
| |
| public class MultiRectAreaOp { |
| |
| /** |
| * Rectangle buffer capacity |
| */ |
| public static final int RECT_CAPACITY = 16; |
| |
| /** |
| * If number of rectangle in MultiRectArea object less than MAX_SIMPLE simple algorithm applies |
| */ |
| private static final int MAX_SIMPLE = 8; |
| |
| /** |
| * Create buffer |
| */ |
| public static int[] createBuf(int capacity) { |
| if (capacity == 0) { |
| capacity = RECT_CAPACITY; |
| } |
| int[] buf = new int[capacity]; |
| buf[0] = 1; |
| return buf; |
| } |
| |
| /** |
| * Checks buffer size and reallocate if necessary |
| */ |
| public static int[] checkBufSize(int[] buf, int capacity) { |
| if (buf[0] + capacity >= buf.length) { |
| int length = buf[0] + (capacity > RECT_CAPACITY ? capacity : RECT_CAPACITY); |
| int[] tmp = new int[length]; |
| System.arraycopy(buf, 0, tmp, 0, buf[0]); |
| buf = tmp; |
| } |
| buf[0] += capacity; |
| return buf; |
| } |
| |
| /** |
| * Region class provides basic functionlity for MultiRectArea objects to make logical operations |
| */ |
| static class Region { |
| |
| int[] region; |
| int[] active; |
| int[] bottom; |
| int index; |
| |
| public Region(int[] region) { |
| this.region = region; |
| active = new int[RECT_CAPACITY]; |
| bottom = new int[RECT_CAPACITY]; |
| active[0] = 1; |
| bottom[0] = 1; |
| index = 1; |
| } |
| |
| void addActive(int index) { |
| int length = active[0]; |
| active = checkBufSize(active, 4); |
| int i = 1; |
| |
| while(i < length) { |
| if (region[index] < active[i]) { |
| // Insert |
| System.arraycopy(active, i, active, i + 4, length - i); |
| length = i; |
| break; |
| } |
| i += 4; |
| } |
| System.arraycopy(region, index, active, length, 4); |
| |
| } |
| |
| void findActive(int top, int bottom) { |
| while(index < region[0]) { |
| if (region[index + 1] > bottom) { // y1 > bottom |
| return; |
| } |
| if (region[index + 3] >= top) { // y2 >= top |
| addActive(index); |
| } |
| index += 4; |
| } |
| } |
| |
| void deleteActive(int bottom) { |
| int length = active[0]; |
| for(int i = 1; i < length;) { |
| if (active[i + 3] == bottom) { |
| length -= 4; |
| if (i < length) { |
| System.arraycopy(active, i + 4, active, i, length - i); |
| } |
| } else { |
| i += 4; |
| } |
| } |
| active[0] = length; |
| } |
| |
| void deleteActive() { |
| int length = active[0]; |
| for(int i = length - 4; i > 0; i -= 4) { |
| if (active[i + 1] > active[i + 3]) { |
| length -= 4; |
| if (i < length) { |
| System.arraycopy(active, i + 4, active, i, length - i); |
| } |
| } |
| } |
| active[0] = length; |
| } |
| |
| void createLevel(int[] level) { |
| int levelCount = 1; |
| int topIndex = 1; |
| int i = 1; |
| while(i < region[0]) { |
| |
| int top = region[i + 1]; |
| int bottom = region[i + 3] + 1; |
| int j = topIndex; |
| |
| addTop: { |
| while(j < levelCount) { |
| if (level[j] == top) { |
| break addTop; |
| } |
| if (level[j] > top) { |
| System.arraycopy(level, j, level, j + 1, levelCount - j); |
| break; |
| } |
| j++; |
| } |
| |
| level[j] = top; |
| levelCount++; |
| topIndex = j; |
| } |
| |
| addBottom: { |
| while(j < levelCount) { |
| if (level[j] == bottom) { |
| break addBottom; |
| } |
| if (level[j] > bottom) { |
| System.arraycopy(level, j, level, j + 1, levelCount - j); |
| break; |
| } |
| j++; |
| }; |
| |
| level[j] = bottom; |
| levelCount++; |
| } |
| |
| i += 4; |
| } |
| level[0] = levelCount; |
| } |
| |
| static void sortOrdered(int[] src1, int[] src2, int[] dst) { |
| int length1 = src1[0]; |
| int length2 = src2[0]; |
| int count = 1; |
| int i1 = 1; |
| int i2 = 1; |
| int v1 = src1[1]; |
| int v2 = src2[1]; |
| while(true) { |
| |
| LEFT: { |
| while(i1 < length1) { |
| v1 = src1[i1]; |
| if (v1 >= v2) { |
| break LEFT; |
| } |
| dst[count++] = v1; |
| i1++; |
| } |
| while(i2 < length2) { |
| dst[count++] = src2[i2++]; |
| } |
| dst[0] = count; |
| return; |
| } |
| |
| RIGHT: { |
| while(i2 < length2) { |
| v2 = src2[i2]; |
| if (v2 >= v1) { |
| break RIGHT; |
| } |
| dst[count++] = v2; |
| i2++; |
| } |
| while(i1 < length1) { |
| dst[count++] = src1[i1++]; |
| } |
| dst[0] = count; |
| return; |
| } |
| |
| if (v1 == v2) { |
| dst[count++] = v1; |
| i1++; |
| i2++; |
| if (i1 < length1) { |
| v1 = src1[i1]; |
| } |
| if (i2 < length2 - 1) { |
| v2 = src2[i2]; |
| } |
| } |
| } |
| // UNREACHABLE |
| } |
| |
| } |
| |
| /** |
| * Intersection class provides intersection of two MultiRectAre aobjects |
| */ |
| static class Intersection { |
| |
| static void intersectRegions(int[] reg1, int[] reg2, MultiRectArea.RectCash dst, int height1, int height2) { |
| |
| Region d1 = new Region(reg1); |
| Region d2 = new Region(reg2); |
| |
| int[] level = new int[height1 + height2]; |
| int[] level1 = new int[height1]; |
| int[] level2 = new int[height2]; |
| d1.createLevel(level1); |
| d2.createLevel(level2); |
| Region.sortOrdered(level1, level2, level); |
| |
| int top; |
| int bottom = level[1] - 1; |
| for(int i = 2; i < level[0]; i++) { |
| |
| top = bottom + 1; |
| bottom = level[i] - 1; |
| |
| d1.findActive(top, bottom); |
| d2.findActive(top, bottom); |
| |
| int i1 = 1; |
| int i2 = 1; |
| |
| while(i1 < d1.active[0] && i2 < d2.active[0]) { |
| |
| int x11 = d1.active[i1]; |
| int x12 = d1.active[i1 + 2]; |
| int x21 = d2.active[i2]; |
| int x22 = d2.active[i2 + 2]; |
| |
| if (x11 <= x21) { |
| if (x12 >= x21) { |
| if (x12 <= x22) { |
| dst.addRectCashed(x21, top, x12, bottom); |
| i1 += 4; |
| } else { |
| dst.addRectCashed(x21, top, x22, bottom); |
| i2 += 4; |
| } |
| } else { |
| i1 += 4; |
| } |
| } else { |
| if (x22 >= x11) { |
| if (x22 <= x12) { |
| dst.addRectCashed(x11, top, x22, bottom); |
| i2 += 4; |
| } else { |
| dst.addRectCashed(x11, top, x12, bottom); |
| i1 += 4; |
| } |
| } else { |
| i2 += 4; |
| } |
| } |
| } |
| |
| d1.deleteActive(bottom); |
| d2.deleteActive(bottom); |
| } |
| } |
| |
| static int[] simpleIntersect(MultiRectArea src1, MultiRectArea src2) { |
| int[] rect1 = src1.rect; |
| int[] rect2 = src2.rect; |
| int[] rect = createBuf(0); |
| |
| int k = 1; |
| for(int i = 1; i < rect1[0];) { |
| |
| int x11 = rect1[i++]; |
| int y11 = rect1[i++]; |
| int x12 = rect1[i++]; |
| int y12 = rect1[i++]; |
| |
| for(int j = 1; j < rect2[0];) { |
| |
| int x21 = rect2[j++]; |
| int y21 = rect2[j++]; |
| int x22 = rect2[j++]; |
| int y22 = rect2[j++]; |
| |
| if (x11 <= x22 && x12 >= x21 && |
| y11 <= y22 && y12 >= y21) |
| { |
| rect = checkBufSize(rect, 4); |
| rect[k++] = x11 > x21 ? x11 : x21; |
| rect[k++] = y11 > y21 ? y11 : y21; |
| rect[k++] = x12 > x22 ? x22 : x12; |
| rect[k++] = y12 > y22 ? y22 : y12; |
| } |
| } |
| } |
| |
| rect[0] = k; |
| return rect; |
| } |
| |
| public static MultiRectArea getResult(MultiRectArea src1, MultiRectArea src2) { |
| |
| if (src1 == null || src2 == null || src1.isEmpty() || src2.isEmpty()) { |
| return new MultiRectArea(); |
| } |
| |
| MultiRectArea.RectCash dst = new MultiRectArea.RectCash(); |
| |
| if (!src1.sorted || !src2.sorted || |
| src1.getRectCount() <= MAX_SIMPLE || src2.getRectCount() <= MAX_SIMPLE) |
| { |
| dst.setRect(simpleIntersect(src1, src2), false); |
| } else { |
| Rectangle bounds1 = src1.getBounds(); |
| Rectangle bounds2 = src2.getBounds(); |
| Rectangle bounds3 = bounds1.intersection(bounds2); |
| if (bounds3.width > 0 && bounds3.height > 0) { |
| intersectRegions(src1.rect, src2.rect, dst, bounds1.height + 2, bounds2.height + 2); |
| } |
| } |
| |
| return dst; |
| } |
| |
| } |
| |
| /** |
| * Union class provides union of two MultiRectAre aobjects |
| */ |
| static class Union { |
| |
| int rx1, rx2; |
| int top, bottom; |
| MultiRectArea.RectCash dst; |
| |
| boolean next(Region d, int index) { |
| int x1 = d.active[index]; |
| int x2 = d.active[index + 2]; |
| boolean res = false; |
| |
| if (x2 < rx1 - 1) { |
| res = true; |
| dst.addRectCashed(x1, top, x2, bottom); |
| } else |
| if (x1 > rx2 + 1) { |
| res = false; |
| dst.addRectCashed(rx1, top, rx2, bottom); |
| rx1 = x1; |
| rx2 = x2; |
| } else { |
| res = x2 <= rx2; |
| rx1 = Math.min(x1, rx1); |
| rx2 = Math.max(x2, rx2); |
| } |
| |
| // Top |
| if (d.active[index + 1] < top) { |
| dst.addRectCashed(x1, d.active[index + 1], x2, top - 1); |
| } |
| // Bottom |
| if (d.active[index + 3] > bottom) { |
| d.active[index + 1] = bottom + 1; |
| } |
| return res; |
| } |
| |
| void check(Region d, int index, boolean t) { |
| int x1 = d.active[index]; |
| int x2 = d.active[index + 2]; |
| // Top |
| if (d.active[index + 1] < top) { |
| dst.addRectCashed(x1, d.active[index + 1], x2, top - 1); |
| } |
| if (t) { |
| dst.addRectCashed(x1, top, x2, bottom); |
| } |
| // Bottom |
| if (d.active[index + 3] > bottom) { |
| d.active[index + 1] = bottom + 1; |
| } |
| } |
| |
| void unionRegions(int[] reg1, int[] reg2, int height1, int height2) { |
| Region d1 = new Region(reg1); |
| Region d2 = new Region(reg2); |
| |
| int[] level = new int[height1 + height2]; |
| int[] level1 = new int[height1]; |
| int[] level2 = new int[height2]; |
| d1.createLevel(level1); |
| d2.createLevel(level2); |
| Region.sortOrdered(level1, level2, level); |
| |
| bottom = level[1] - 1; |
| for(int i = 2; i < level[0]; i++) { |
| |
| top = bottom + 1; |
| bottom = level[i] - 1; |
| |
| d1.findActive(top, bottom); |
| d2.findActive(top, bottom); |
| |
| int i1 = 1; |
| int i2 = 1; |
| boolean res1, res2; |
| |
| if (d1.active[0] > 1) { |
| check(d1, 1, false); |
| rx1 = d1.active[1]; |
| rx2 = d1.active[3]; |
| i1 += 4; |
| res1 = false; |
| res2 = true; |
| } else |
| if (d2.active[0] > 1) { |
| check(d2, 1, false); |
| rx1 = d2.active[1]; |
| rx2 = d2.active[3]; |
| i2 += 4; |
| res1 = true; |
| res2 = false; |
| } else { |
| continue; |
| } |
| |
| outer: |
| while(true) { |
| |
| while (res1) { |
| if (i1 >= d1.active[0]) { |
| dst.addRectCashed(rx1, top, rx2, bottom); |
| while(i2 < d2.active[0]) { |
| check(d2, i2, true); |
| i2 += 4; |
| } |
| break outer; |
| } |
| res1 = next(d1, i1); |
| i1 += 4; |
| } |
| |
| while (res2) { |
| if (i2 >= d2.active[0]) { |
| dst.addRectCashed(rx1, top, rx2, bottom); |
| while(i1 < d1.active[0]) { |
| check(d1, i1, true); |
| i1 += 4; |
| } |
| break outer; |
| } |
| res2 = next(d2, i2); |
| i2 += 4; |
| } |
| |
| res1 = true; |
| res2 = true; |
| } // while |
| |
| d1.deleteActive(bottom); |
| d2.deleteActive(bottom); |
| |
| } |
| } |
| |
| static void simpleUnion(MultiRectArea src1, MultiRectArea src2, MultiRectArea dst) { |
| if (src1.getRectCount() < src2.getRectCount()) { |
| simpleUnion(src2, src1, dst); |
| } else { |
| Subtraction.simpleSubtract(src1, src2, dst); |
| int pos = dst.rect[0]; |
| int size = src2.rect[0] - 1; |
| dst.rect = checkBufSize(dst.rect, size); |
| System.arraycopy(src2.rect,1, dst.rect, pos, size); |
| dst.resort(); |
| } |
| } |
| |
| MultiRectArea getResult(MultiRectArea src1, MultiRectArea src2) { |
| |
| if (src1 == null || src1.isEmpty()) { |
| return new MultiRectArea(src2); |
| } |
| |
| if (src2 == null || src2.isEmpty()) { |
| return new MultiRectArea(src1); |
| } |
| |
| dst = new MultiRectArea.RectCash(); |
| |
| if (!src1.sorted || !src2.sorted || |
| src1.getRectCount() <= MAX_SIMPLE || src2.getRectCount() <= MAX_SIMPLE) |
| { |
| simpleUnion(src1, src2, dst); |
| } else { |
| Rectangle bounds1 = src1.getBounds(); |
| Rectangle bounds2 = src2.getBounds(); |
| Rectangle bounds3 = bounds1.intersection(bounds2); |
| |
| if (bounds3.width < 0 || bounds3.height < 0) { |
| if (bounds1.y + bounds1.height < bounds2.y) { |
| dst.setRect(addVerRegion(src1.rect, src2.rect), false); |
| } else |
| if (bounds2.y + bounds2.height < bounds1.y) { |
| dst.setRect(addVerRegion(src2.rect, src1.rect), false); |
| } else |
| if (bounds1.x < bounds2.x) { |
| dst.setRect(addHorRegion(src1.rect, src2.rect), false); |
| } else { |
| dst.setRect(addHorRegion(src2.rect, src1.rect), false); |
| } |
| } else { |
| unionRegions(src1.rect, src2.rect, bounds1.height + 2, bounds2.height + 2); |
| } |
| } |
| |
| return dst; |
| } |
| |
| int[] addVerRegion(int[] top, int[] bottom) { |
| int length = top[0] + bottom[0] - 1; |
| int[] dst = new int[length]; |
| dst[0] = length; |
| System.arraycopy(top, 1, dst, 1, top[0] - 1); |
| System.arraycopy(bottom, 1, dst, top[0], bottom[0] - 1); |
| return dst; |
| } |
| |
| int[] addHorRegion(int[] left, int[] right) { |
| int count1 = left[0]; |
| int count2 = right[0]; |
| int[] dst = new int[count1 + count2 + 1]; |
| int count = 1; |
| int index1 = 1; |
| int index2 = 1; |
| |
| int top1 = left[2]; |
| int top2 = right[2]; |
| int pos1, pos2; |
| |
| while(true) { |
| |
| if (index1 >= count1) { |
| System.arraycopy(right, index2, dst, count, count2 - index2); |
| count += count2 - index2; |
| break; |
| } |
| if (index2 >= count2) { |
| System.arraycopy(left, index1, dst, count, count1 - index1); |
| count += count1 - index1; |
| break; |
| } |
| |
| if (top1 < top2) { |
| pos1 = index1; |
| do { |
| index1 += 4; |
| } while (index1 < count1 && (top1 = left[index1 + 1]) < top2); |
| System.arraycopy(left, pos1, dst, count, index1 - pos1); |
| count += index1 - pos1; |
| continue; |
| } |
| |
| if (top1 > top2) { |
| pos2 = index2; |
| do { |
| index2 += 4; |
| } while (index2 < count2 && (top2 = right[index2 + 1]) < top1); |
| System.arraycopy(right, pos2, dst, count, index2 - pos2); |
| count += index2 - pos2; |
| continue; |
| } |
| |
| int top = top1; |
| pos1 = index1; |
| pos2 = index2; |
| do { |
| index1 += 4; |
| } while(index1 < count1 && (top1 = left[index1 + 1]) == top); |
| do { |
| index2 += 4; |
| } while(index2 < count2 && (top2 = right[index2 + 1]) == top); |
| |
| System.arraycopy(left, pos1, dst, count, index1 - pos1); |
| count += index1 - pos1; |
| System.arraycopy(right, pos2, dst, count, index2 - pos2); |
| count += index2 - pos2; |
| } |
| |
| dst[0] = count; |
| return dst; |
| } |
| |
| } |
| |
| /** |
| * Subtraction class provides subtraction of two MultiRectAre aobjects |
| */ |
| static class Subtraction { |
| |
| static void subtractRegions(int[] reg1, int[] reg2, MultiRectArea.RectCash dst, int height1, int height2) { |
| Region d1 = new Region(reg1); |
| Region d2 = new Region(reg2); |
| |
| int[] level = new int[height1 + height2]; |
| int[] level1 = new int[height1]; |
| int[] level2 = new int[height2]; |
| d1.createLevel(level1); |
| d2.createLevel(level2); |
| Region.sortOrdered(level1, level2, level); |
| |
| int top; |
| int bottom = level[1] - 1; |
| for(int i = 2; i < level[0]; i++) { |
| |
| top = bottom + 1; |
| bottom = level[i] - 1; |
| |
| d1.findActive(top, bottom); |
| if (d1.active[0] == 1) { |
| d2.deleteActive(bottom); |
| continue; |
| } |
| |
| d2.findActive(top, bottom); |
| |
| int i1 = 1; |
| int i2 = 1; |
| |
| int rx1 = 0; |
| int rx2 = 0; |
| |
| boolean next = true; |
| |
| while(true) { |
| |
| if (next) { |
| next = false; |
| if (i1 >= d1.active[0]) { |
| break; |
| } |
| // Bottom |
| d1.active[i1 + 1] = bottom + 1; |
| rx1 = d1.active[i1]; |
| rx2 = d1.active[i1 + 2]; |
| i1 += 4; |
| } |
| |
| if (i2 >= d2.active[0]) { |
| dst.addRectCashed(rx1, top, rx2, bottom); |
| for(int j = i1; j < d1.active[0]; j += 4) { |
| dst.addRectCashed(d1.active[j], top, d1.active[j + 2], bottom); |
| d1.active[j + 1] = bottom + 1; |
| } |
| break; |
| } |
| |
| int x1 = d2.active[i2]; |
| int x2 = d2.active[i2 + 2]; |
| |
| if (rx1 < x1) { |
| if (rx2 >= x1) { |
| if (rx2 <= x2) { |
| // [-----------] |
| // [-------------] |
| dst.addRectCashed(rx1, top, x1 - 1, bottom); |
| next = true; |
| } else { |
| // [-----------------] |
| // [------] |
| dst.addRectCashed(rx1, top, x1 - 1, bottom); |
| rx1 = x2 + 1; |
| i2 += 4; |
| } |
| } else { |
| // [-----] |
| // [----] |
| dst.addRectCashed(rx1, top, rx2, bottom); |
| next = true; |
| } |
| } else { |
| if (rx1 <= x2) { |
| if (rx2 <= x2) { |
| // [------] |
| // [-----------] |
| next = true; |
| } else { |
| // [------------] |
| // [---------] |
| rx1 = x2 + 1; |
| i2 += 4; |
| } |
| } else { |
| // [----] |
| // [-----] |
| i2 += 4; |
| } |
| } |
| |
| } |
| d1.deleteActive(); |
| d2.deleteActive(bottom); |
| } |
| } |
| |
| static void subtractRect(int x11, int y11, int x12, int y12, int[] rect, int index, MultiRectArea dst) { |
| |
| for(int i = index; i < rect[0]; i += 4) { |
| int x21 = rect[i + 0]; |
| int y21 = rect[i + 1]; |
| int x22 = rect[i + 2]; |
| int y22 = rect[i + 3]; |
| |
| if (x11 <= x22 && x12 >= x21 && y11 <= y22 && y12 >= y21) { |
| int top, bottom; |
| if (y11 < y21) { |
| subtractRect(x11, y11, x12, y21 - 1, rect, i + 4, dst); |
| top = y21; |
| } else { |
| top = y11; |
| } |
| if (y12 > y22) { |
| subtractRect(x11, y22 + 1, x12, y12, rect, i + 4, dst); |
| bottom = y22; |
| } else { |
| bottom = y12; |
| } |
| if (x11 < x21) { |
| subtractRect(x11, top, x21 - 1, bottom, rect, i + 4, dst); |
| } |
| if (x12 > x22) { |
| subtractRect(x22 + 1, top, x12, bottom, rect, i + 4, dst); |
| } |
| return; |
| } |
| } |
| dst.addRect(x11, y11, x12, y12); |
| } |
| |
| static void simpleSubtract(MultiRectArea src1, MultiRectArea src2, MultiRectArea dst) { |
| for(int i = 1; i < src1.rect[0]; i += 4) { |
| subtractRect( |
| src1.rect[i + 0], |
| src1.rect[i + 1], |
| src1.rect[i + 2], |
| src1.rect[i + 3], |
| src2.rect, |
| 1, |
| dst); |
| } |
| dst.resort(); |
| } |
| |
| public static MultiRectArea getResult(MultiRectArea src1, MultiRectArea src2) { |
| |
| if (src1 == null || src1.isEmpty()) { |
| return new MultiRectArea(); |
| } |
| |
| if (src2 == null || src2.isEmpty()) { |
| return new MultiRectArea(src1); |
| } |
| |
| MultiRectArea.RectCash dst = new MultiRectArea.RectCash(); |
| |
| if (!src1.sorted || !src2.sorted || |
| src1.getRectCount() <= MAX_SIMPLE || src2.getRectCount() <= MAX_SIMPLE) |
| { |
| simpleSubtract(src1, src2, dst); |
| } else { |
| Rectangle bounds1 = src1.getBounds(); |
| Rectangle bounds2 = src2.getBounds(); |
| Rectangle bounds3 = bounds1.intersection(bounds2); |
| |
| if (bounds3.width > 0 && bounds3.height > 0) { |
| subtractRegions(src1.rect, src2.rect, dst, bounds1.height + 2, bounds2.height + 2); |
| } else { |
| dst.setRect(src1.rect, true); |
| } |
| } |
| |
| return dst; |
| } |
| |
| } |
| |
| } |