Add functionality for isRect() to SkPath.
http://codereview.appspot.com/4807052/
M src/core/SkPath.cpp
M tests/PathTest.cpp
git-svn-id: http://skia.googlecode.com/svn/trunk@1964 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp
index 5a05b3e..c415697 100644
--- a/src/core/SkPath.cpp
+++ b/src/core/SkPath.cpp
@@ -186,11 +186,120 @@
return count == 0 || (count == 1 && fVerbs[0] == kMove_Verb);
}
-bool SkPath::isRect(SkRect*) const {
+/*
+ Determines if path is a rect by keeping track of changes in direction
+ and looking for a loop either clockwise or counterclockwise.
+
+ The direction is computed such that:
+ 0: vertical up
+ 1: horizontal right
+ 2: vertical down
+ 3: horizontal left
+
+A rectangle cycles up/right/down/left or up/left/down/right.
+
+The test fails if:
+ The path is closed, and followed by a line.
+ A second move creates a new endpoint.
+ A diagonal line is parsed.
+ There's more than four changes of direction.
+ There's a discontinuity on the line (e.g., a move in the middle)
+ The line reverses direction.
+ The rectangle doesn't complete a cycle.
+ The path contains a quadratic or cubic.
+ The path contains fewer than four points.
+ The final point isn't equal to the first point.
+
+It's OK if the path has:
+ Several colinear line segments composing a rectangle side.
+ Single points on the rectangle side.
+
+The direction takes advantage of the corners found since opposite sides
+must travel in opposite directions.
+
+FIXME: Allow colinear quads and cubics to be treated like lines.
+FIXME: If the API passes fill-only, return true if the filled stroke
+ is a rectangle, though the caller failed to close the path.
+ */
+bool SkPath::isRect(SkRect* rect) const {
SkDEBUGCODE(this->validate();)
- SkASSERT(!"unimplemented");
- return false;
+ int corners = 0;
+ SkPoint first, last;
+ int firstDirection;
+ int lastDirection;
+ int nextDirection;
+ bool closedOrMoved;
+ bool autoClose = false;
+ const uint8_t* verbs = fVerbs.begin();
+ const uint8_t* verbStop = fVerbs.end();
+ const SkPoint* pts = fPts.begin();
+ while (verbs != verbStop) {
+ switch (*verbs++) {
+ case kClose_Verb:
+ pts = fPts.begin();
+ autoClose = true;
+ case kLine_Verb: {
+ SkScalar left = last.fX;
+ SkScalar top = last.fY;
+ SkScalar right = pts->fX;
+ SkScalar bottom = pts->fY;
+ ++pts;
+ if (left != right && top != bottom) {
+ return false; // diagonal
+ }
+ if (left == right && top == bottom) {
+ break; // single point on side OK
+ }
+ nextDirection = (left != right) << 0 |
+ (left < right || top < bottom) << 1;
+ if (0 == corners) {
+ firstDirection = nextDirection;
+ first = last;
+ last = pts[-1];
+ corners = 1;
+ closedOrMoved = false;
+ break;
+ }
+ if (closedOrMoved) {
+ return false; // closed followed by a line
+ }
+ closedOrMoved = autoClose;
+ if (lastDirection != nextDirection) {
+ if (++corners > 4) {
+ return false; // too many direction changes
+ }
+ }
+ last = pts[-1];
+ if (lastDirection == nextDirection) {
+ break; // colinear segment
+ }
+ // Possible values for corners are 2, 3, and 4.
+ // When corners == 3, nextDirection opposes firstDirection.
+ // Otherwise, nextDirection at corner 2 opposes corner 4.
+ int turn = firstDirection ^ corners - 1;
+ int directionCycle = 3 == corners ? 0 : nextDirection ^ turn;
+ if ((directionCycle ^ turn) != nextDirection) {
+ return false; // direction didn't follow cycle
+ }
+ break;
+ }
+ case kQuad_Verb:
+ case kCubic_Verb:
+ return false; // quadratic, cubic not allowed
+ case kMove_Verb:
+ last = *pts++;
+ closedOrMoved = true;
+ break;
+ }
+ lastDirection = nextDirection;
+ }
+ // Success if 4 corners and first point equals last
+ bool result = 4 == corners && first == last;
+ if (result && rect) {
+ *rect = getBounds();
+ }
+ return result;
}
int SkPath::getPoints(SkPoint copy[], int max) const {
diff --git a/tests/PathTest.cpp b/tests/PathTest.cpp
index c793266..2aa06a7 100644
--- a/tests/PathTest.cpp
+++ b/tests/PathTest.cpp
@@ -263,6 +263,134 @@
}
}
+// Simple isRect test is inline TestPath, below.
+// test_isRect provides more extensive testing.
+static void test_isRect(skiatest::Reporter* reporter) {
+ // passing tests (all moveTo / lineTo...
+ SkPoint r1[] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
+ SkPoint r2[] = {{1, 0}, {1, 1}, {0, 1}, {0, 0}};
+ SkPoint r3[] = {{1, 1}, {0, 1}, {0, 0}, {1, 0}};
+ SkPoint r4[] = {{0, 1}, {0, 0}, {1, 0}, {1, 1}};
+ SkPoint r5[] = {{0, 0}, {0, 1}, {1, 1}, {1, 0}};
+ SkPoint r6[] = {{0, 1}, {1, 1}, {1, 0}, {0, 0}};
+ SkPoint r7[] = {{1, 1}, {1, 0}, {0, 0}, {0, 1}};
+ SkPoint r8[] = {{1, 0}, {0, 0}, {0, 1}, {1, 1}};
+ SkPoint r9[] = {{0, 1}, {1, 1}, {1, 0}, {0, 0}};
+ SkPoint ra[] = {{0, 0}, {0, .5f}, {0, 1}, {.5f, 1}, {1, 1}, {1, .5f},
+ {1, 0}, {.5f, 0}};
+ SkPoint rb[] = {{0, 0}, {.5f, 0}, {1, 0}, {1, .5f}, {1, 1}, {.5f, 1},
+ {0, 1}, {0, .5f}};
+ SkPoint rc[] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}, {0, 0}};
+ SkPoint rd[] = {{0, 0}, {0, 1}, {1, 1}, {1, 0}, {0, 0}};
+ SkPoint re[] = {{0, 0}, {1, 0}, {1, 0}, {1, 1}, {0, 1}};
+
+ // failing tests
+ SkPoint f1[] = {{0, 0}, {1, 0}, {1, 1}}; // too few points
+ SkPoint f2[] = {{0, 0}, {1, 1}, {0, 1}, {1, 0}}; // diagonal
+ SkPoint f3[] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}, {0, 0}, {1, 0}}; // wraps
+ SkPoint f4[] = {{0, 0}, {1, 0}, {0, 0}, {1, 0}, {1, 1}, {0, 1}}; // backs up
+ SkPoint f5[] = {{0, 0}, {1, 0}, {1, 1}, {2, 0}}; // end overshoots
+ SkPoint f6[] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}, {0, 2}}; // end overshoots
+ SkPoint f7[] = {{0, 0}, {1, 0}, {1, 1}, {0, 2}}; // end overshoots
+ SkPoint f8[] = {{0, 0}, {1, 0}, {1, 1}, {1, 0}}; // 'L'
+
+ // failing, no close
+ SkPoint c1[] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}}; // close doesn't match
+ SkPoint c2[] = {{0, 0}, {1, 0}, {1, 2}, {0, 2}, {0, 1}}; // ditto
+
+ size_t testLen[] = {
+ sizeof(r1), sizeof(r2), sizeof(r3), sizeof(r4), sizeof(r5), sizeof(r6),
+ sizeof(r7), sizeof(r8), sizeof(r9), sizeof(ra), sizeof(rb), sizeof(rc),
+ sizeof(rd), sizeof(re),
+ sizeof(f1), sizeof(f2), sizeof(f3), sizeof(f4), sizeof(f5), sizeof(f6),
+ sizeof(f7), sizeof(f8),
+ sizeof(c1), sizeof(c2)
+ };
+ SkPoint* tests[] = {
+ r1, r2, r3, r4, r5, r6, r7, r8, r9, ra, rb, rc, rd, re,
+ f1, f2, f3, f4, f5, f6, f7, f8,
+ c1, c2
+ };
+ SkPoint* lastPass = re;
+ SkPoint* lastClose = f8;
+ bool fail = false;
+ bool close = true;
+ const size_t testCount = sizeof(tests) / sizeof(tests[0]);
+ size_t index;
+ for (size_t testIndex = 0; testIndex < testCount; ++testIndex) {
+ SkPath path;
+ path.moveTo(tests[testIndex][0].fX, tests[testIndex][0].fY);
+ for (index = 1; index < testLen[testIndex] / sizeof(SkPoint); ++index) {
+ path.lineTo(tests[testIndex][index].fX, tests[testIndex][index].fY);
+ }
+ if (close) {
+ path.close();
+ }
+ REPORTER_ASSERT(reporter, fail ^ path.isRect(0));
+ if (tests[testIndex] == lastPass) {
+ fail = true;
+ }
+ if (tests[testIndex] == lastClose) {
+ close = false;
+ }
+ }
+
+ // fail, close then line
+ SkPath path1;
+ path1.moveTo(r1[0].fX, r1[0].fY);
+ for (index = 1; index < testLen[0] / sizeof(SkPoint); ++index) {
+ path1.lineTo(r1[index].fX, r1[index].fY);
+ }
+ path1.close();
+ path1.lineTo(1, 0);
+ REPORTER_ASSERT(reporter, fail ^ path1.isRect(0));
+
+ // fail, move in the middle
+ path1.reset();
+ path1.moveTo(r1[0].fX, r1[0].fY);
+ for (index = 1; index < testLen[0] / sizeof(SkPoint); ++index) {
+ if (index == 2) {
+ path1.moveTo(1, .5f);
+ }
+ path1.lineTo(r1[index].fX, r1[index].fY);
+ }
+ path1.close();
+ REPORTER_ASSERT(reporter, fail ^ path1.isRect(0));
+
+ // fail, move on the edge
+ path1.reset();
+ for (index = 1; index < testLen[0] / sizeof(SkPoint); ++index) {
+ path1.moveTo(r1[index - 1].fX, r1[index - 1].fY);
+ path1.lineTo(r1[index].fX, r1[index].fY);
+ }
+ path1.close();
+ REPORTER_ASSERT(reporter, fail ^ path1.isRect(0));
+
+ // fail, quad
+ path1.reset();
+ path1.moveTo(r1[0].fX, r1[0].fY);
+ for (index = 1; index < testLen[0] / sizeof(SkPoint); ++index) {
+ if (index == 2) {
+ path1.quadTo(1, .5f, 1, .5f);
+ }
+ path1.lineTo(r1[index].fX, r1[index].fY);
+ }
+ path1.close();
+ REPORTER_ASSERT(reporter, fail ^ path1.isRect(0));
+
+ // fail, cubic
+ path1.reset();
+ path1.moveTo(r1[0].fX, r1[0].fY);
+ for (index = 1; index < testLen[0] / sizeof(SkPoint); ++index) {
+ if (index == 2) {
+ path1.cubicTo(1, .5f, 1, .5f, 1, .5f);
+ }
+ path1.lineTo(r1[index].fX, r1[index].fY);
+ }
+ path1.close();
+ REPORTER_ASSERT(reporter, fail ^ path1.isRect(0));
+}
+
void TestPath(skiatest::Reporter* reporter);
void TestPath(skiatest::Reporter* reporter) {
{
@@ -315,9 +443,8 @@
p.offset(SK_Scalar1*3, SK_Scalar1*4);
REPORTER_ASSERT(reporter, bounds == p.getBounds());
-#if 0 // isRect needs to be implemented
REPORTER_ASSERT(reporter, p.isRect(NULL));
- bounds.setEmpty();
+ bounds2.setEmpty();
REPORTER_ASSERT(reporter, p.isRect(&bounds2));
REPORTER_ASSERT(reporter, bounds == bounds2);
@@ -325,7 +452,7 @@
bounds.set(0, 0, SK_Scalar1/2, SK_Scalar1/2);
p.addRect(bounds);
REPORTER_ASSERT(reporter, !p.isRect(NULL));
-#endif
+ test_isRect(reporter);
SkPoint pt;