Add createTJunctionFreeRegion
T-junction free regions are useful for rendering regions with various
geometric transformations, and the Region's span-ordered, sorted rect
list supports T-junction free storage without modification.
This approach creates a T-junction free region by splitting each
rectangle that is part of a vertical T-junction. This approach is two
pass (up and down) so that divisions can trickle up/down to other
adjacent spans.
Change-Id: Ifcf5e6fe0034c96b00ef09a4433b2b0fce8f4300
diff --git a/libs/ui/tests/Android.mk b/libs/ui/tests/Android.mk
index 50cad36..8b8e1d8 100644
--- a/libs/ui/tests/Android.mk
+++ b/libs/ui/tests/Android.mk
@@ -1,4 +1,28 @@
# Build the unit tests.
+LOCAL_PATH := $(call my-dir)
+include $(CLEAR_VARS)
+
+# Build the unit tests.
+test_src_files := \
+ Region_test.cpp
+
+shared_libraries := \
+ libui
+
+static_libraries := \
+ libgtest \
+ libgtest_main
+
+$(foreach file,$(test_src_files), \
+ $(eval include $(CLEAR_VARS)) \
+ $(eval LOCAL_SHARED_LIBRARIES := $(shared_libraries)) \
+ $(eval LOCAL_STATIC_LIBRARIES := $(static_libraries)) \
+ $(eval LOCAL_SRC_FILES := $(file)) \
+ $(eval LOCAL_MODULE := $(notdir $(file:%.cpp=%))) \
+ $(eval include $(BUILD_NATIVE_TEST)) \
+)
+
+# Build the unit tests.
LOCAL_PATH:= $(call my-dir)
include $(CLEAR_VARS)
diff --git a/libs/ui/tests/Region_test.cpp b/libs/ui/tests/Region_test.cpp
new file mode 100644
index 0000000..b104a46
--- /dev/null
+++ b/libs/ui/tests/Region_test.cpp
@@ -0,0 +1,156 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed 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.
+ */
+
+#define LOG_TAG "RegionTest"
+
+#include <stdlib.h>
+#include <ui/Region.h>
+#include <ui/Rect.h>
+#include <gtest/gtest.h>
+
+namespace android {
+
+class RegionTest : public testing::Test {
+protected:
+ void checkVertTJunction(const Rect* lhs, const Rect* rhs) {
+ EXPECT_FALSE((rhs->right > lhs->left && rhs->right < lhs->right) ||
+ (rhs->left > lhs->left && rhs->left < lhs->right));
+ }
+
+ void verifyNoTJunctions(const Region& r) {
+ for (const Rect* current = r.begin(); current < r.end(); current++) {
+ for (const Rect* other = current - 1; other >= r.begin(); other--) {
+ if (other->bottom < current->top) break;
+ if (other->bottom != current->top) continue;
+ checkVertTJunction(current, other);
+ }
+ for (const Rect* other = current + 1; other < r.end(); other++) {
+ if (other->top > current->bottom) break;
+ if (other->top != current->bottom) continue;
+ checkVertTJunction(current, other);
+ }
+ }
+ }
+
+ void checkTJunctionFreeFromRegion(const Region& original, int expectedCount = -1) {
+ Region modified = Region::createTJunctionFreeRegion(original);
+ verifyNoTJunctions(modified);
+ if (expectedCount != -1) {
+ EXPECT_EQ(modified.end() - modified.begin(), expectedCount);
+ }
+ EXPECT_TRUE((original ^ modified).isEmpty());
+ }
+};
+
+TEST_F(RegionTest, MinimalDivision_TJunction) {
+ Region r;
+ // | x |
+ // |xxx|
+ r.clear();
+ r.orSelf(Rect(1, 0, 2, 1));
+ r.orSelf(Rect(0, 1, 3, 2));
+ checkTJunctionFreeFromRegion(r, 4);
+
+ // | x |
+ // | |
+ // |xxx|
+ r.clear();
+ r.orSelf(Rect(1, 0, 2, 1));
+ r.orSelf(Rect(0, 2, 3, 3));
+ checkTJunctionFreeFromRegion(r, 2);
+}
+
+TEST_F(RegionTest, Trivial_TJunction) {
+ Region r;
+ checkTJunctionFreeFromRegion(r);
+
+ r.orSelf(Rect(100, 100, 500, 500));
+ checkTJunctionFreeFromRegion(r);
+}
+
+TEST_F(RegionTest, Simple_TJunction) {
+ Region r;
+ // | x |
+ // |xxxx|
+ // |xxxx|
+ // |xxxx|
+ r.clear();
+ r.orSelf(Rect(1, 0, 2, 1));
+ r.orSelf(Rect(0, 1, 3, 3));
+ checkTJunctionFreeFromRegion(r);
+
+ // | x |
+ // |xx |
+ // |xxx|
+ r.clear();
+ r.orSelf(Rect(2,0,4,2));
+ r.orSelf(Rect(0,2,4,4));
+ r.orSelf(Rect(0,4,6,6));
+ checkTJunctionFreeFromRegion(r);
+
+ // |x x|
+ // |xxx|
+ // |x x|
+ r.clear();
+ r.orSelf(Rect(0,0,2,6));
+ r.orSelf(Rect(4,0,6,6));
+ r.orSelf(Rect(0,2,6,4));
+ checkTJunctionFreeFromRegion(r);
+
+ // |xxx|
+ // | x |
+ // | x |
+ r.clear();
+ r.orSelf(Rect(0,0,6,2));
+ r.orSelf(Rect(2,2,4,6));
+ checkTJunctionFreeFromRegion(r);
+}
+
+TEST_F(RegionTest, Bigger_TJunction) {
+ Region r;
+ // |xxxx |
+ // | xxxx |
+ // | xxxx |
+ // | xxxx|
+ for (int i = 0; i < 4; i++) {
+ r.orSelf(Rect(i,i,i+4,i+1));
+ }
+ checkTJunctionFreeFromRegion(r, 16);
+}
+
+#define ITER_MAX 1000
+#define X_MAX 8
+#define Y_MAX 8
+
+TEST_F(RegionTest, Random_TJunction) {
+ Region r;
+ srandom(12345);
+
+ for (int iter = 0; iter < ITER_MAX; iter++) {
+ r.clear();
+ for (int i = 0; i < X_MAX; i++) {
+ for (int j = 0; j < Y_MAX; j++) {
+ if (random() % 2) {
+ r.orSelf(Rect(i, j, i + 1, j + 1));
+ }
+ }
+ }
+ checkTJunctionFreeFromRegion(r);
+ }
+}
+
+}; // namespace android
+
diff --git a/libs/ui/tests/region/Android.mk b/libs/ui/tests/region/Android.mk
deleted file mode 100644
index 6cc4a5a..0000000
--- a/libs/ui/tests/region/Android.mk
+++ /dev/null
@@ -1,16 +0,0 @@
-LOCAL_PATH:= $(call my-dir)
-include $(CLEAR_VARS)
-
-LOCAL_SRC_FILES:= \
- region.cpp
-
-LOCAL_SHARED_LIBRARIES := \
- libcutils \
- libutils \
- libui
-
-LOCAL_MODULE:= test-region
-
-LOCAL_MODULE_TAGS := tests
-
-include $(BUILD_EXECUTABLE)
diff --git a/libs/ui/tests/region/region.cpp b/libs/ui/tests/region/region.cpp
deleted file mode 100644
index 6347294..0000000
--- a/libs/ui/tests/region/region.cpp
+++ /dev/null
@@ -1,69 +0,0 @@
-/*
- * Copyright (C) 2009 The Android Open Source Project
- *
- * Licensed 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.
- */
-
-#define LOG_TAG "Region"
-
-#include <stdio.h>
-#include <utils/Debug.h>
-#include <ui/Rect.h>
-#include <ui/Region.h>
-
-using namespace android;
-
-int main()
-{
- Region empty;
- Region reg0( Rect( 0, 0, 100, 100 ) );
- Region reg1 = reg0;
- Region reg2, reg3;
-
- Region reg4 = empty | reg1;
- Region reg5 = reg1 | empty;
-
- reg4.dump("reg4");
- reg5.dump("reg5");
-
- reg0.dump("reg0");
- reg1.dump("reg1");
-
- reg0 = reg0 | reg0.translate(150, 0);
- reg0.dump("reg0");
- reg1.dump("reg1");
-
- reg0 = reg0 | reg0.translate(300, 0);
- reg0.dump("reg0");
- reg1.dump("reg1");
-
- //reg2 = reg0 | reg0.translate(0, 100);
- //reg0.dump("reg0");
- //reg1.dump("reg1");
- //reg2.dump("reg2");
-
- //reg3 = reg0 | reg0.translate(0, 150);
- //reg0.dump("reg0");
- //reg1.dump("reg1");
- //reg2.dump("reg2");
- //reg3.dump("reg3");
-
- ALOGD("---");
- reg2 = reg0 | reg0.translate(100, 0);
- reg0.dump("reg0");
- reg1.dump("reg1");
- reg2.dump("reg2");
-
- return 0;
-}
-