diff options
-rw-r--r-- | src/core/SkPath.cpp | 115 | ||||
-rw-r--r-- | tests/PathTest.cpp | 133 |
2 files changed, 242 insertions, 6 deletions
diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp index 5a05b3e887..c415697bb0 100644 --- a/src/core/SkPath.cpp +++ b/src/core/SkPath.cpp @@ -186,11 +186,120 @@ bool SkPath::isEmpty() const { 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 c793266b17..2aa06a75db 100644 --- a/tests/PathTest.cpp +++ b/tests/PathTest.cpp @@ -263,6 +263,134 @@ static void test_convexity(skiatest::Reporter* reporter) { } } +// 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 @@ void TestPath(skiatest::Reporter* reporter) { 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 @@ void TestPath(skiatest::Reporter* reporter) { 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; |