diff options
author | caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2013-01-17 21:02:47 +0000 |
---|---|---|
committer | caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2013-01-17 21:02:47 +0000 |
commit | 73ca6243b31e225e9fd5b75a96cbc82d62557de6 (patch) | |
tree | f23c55585c47e26f28afdd7b8635b7065a81f06b /experimental | |
parent | 148a3961b1c82a891012f2feb2a875cea2593170 (diff) |
shape ops work in progress
mostly working on cubic/cubic intersect
git-svn-id: http://skia.googlecode.com/svn/trunk@7266 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat (limited to 'experimental')
36 files changed, 3674 insertions, 455 deletions
diff --git a/experimental/Intersection/CubicBezierClip.cpp b/experimental/Intersection/CubicBezierClip.cpp index d0141e9413..825a7b961e 100644 --- a/experimental/Intersection/CubicBezierClip.cpp +++ b/experimental/Intersection/CubicBezierClip.cpp @@ -26,7 +26,8 @@ bool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& } double distance[2]; - endLine.controlPtDistance(cubic1, distance); + distance[0] = endLine.controlPtDistance(cubic1, 1); + distance[1] = endLine.controlPtDistance(cubic1, 2); // find fat line double top = distance[0]; @@ -87,4 +88,3 @@ bool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& return minT < maxT; // returns false if distance shows no intersection } - diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp index fcd4119097..d5a5bdef78 100644 --- a/experimental/Intersection/CubicIntersection.cpp +++ b/experimental/Intersection/CubicIntersection.cpp @@ -159,3 +159,133 @@ bool intersect(const Cubic& c1, const Cubic& c2, Intersections& i) { return c.intersect(); } +#include "CubicUtilities.h" + +// this flavor approximates the cubics with quads to find the intersecting ts +// OPTIMIZE: if this strategy proves successful, the quad approximations, or the ts used +// to create the approximations, could be stored in the cubic segment +// fixme: this strategy needs to add short line segments on either end, or similarly extend the +// initial and final quadratics +bool intersect2(const Cubic& c1, const Cubic& c2, Intersections& i) { + SkTDArray<double> ts1; + double precision1 = calcPrecision(c1); + cubic_to_quadratics(c1, precision1, ts1); + SkTDArray<double> ts2; + double precision2 = calcPrecision(c2); + cubic_to_quadratics(c2, precision2, ts2); + double t1Start = 0; + int ts1Count = ts1.count(); + for (int i1 = 0; i1 <= ts1Count; ++i1) { + const double t1 = i1 < ts1Count ? ts1[i1] : 1; + Cubic part1; + sub_divide(c1, t1Start, t1, part1); + Quadratic q1; + demote_cubic_to_quad(part1, q1); + // start here; + // should reduceOrder be looser in this use case if quartic is going to blow up on an + // extremely shallow quadratic? + // maybe quadratics to lines need the same sort of recursive solution that I hope to find + // for cubics to quadratics ... + Quadratic s1; + int o1 = reduceOrder(q1, s1); + double t2Start = 0; + int ts2Count = ts2.count(); + for (int i2 = 0; i2 <= ts2Count; ++i2) { + const double t2 = i2 < ts2Count ? ts2[i2] : 1; + Cubic part2; + sub_divide(c2, t2Start, t2, part2); + Quadratic q2; + demote_cubic_to_quad(part2, q2); + Quadratic s2; + double o2 = reduceOrder(q2, s2); + Intersections locals; + if (o1 == 3 && o2 == 3) { + intersect2(q1, q2, locals); + } else if (o1 <= 2 && o2 <= 2) { + i.fUsed = intersect((const _Line&) s1, (const _Line&) s2, i.fT[0], i.fT[1]); + } else if (o1 == 3 && o2 <= 2) { + intersect(q1, (const _Line&) s2, i); + } else { + SkASSERT(o1 <= 2 && o2 == 3); + intersect(q2, (const _Line&) s1, i); + for (int s = 0; s < i.fUsed; ++s) { + SkTSwap(i.fT[0][s], i.fT[1][s]); + } + } + for (int tIdx = 0; tIdx < locals.used(); ++tIdx) { + double to1 = t1Start + (t1 - t1Start) * locals.fT[0][tIdx]; + double to2 = t2Start + (t2 - t2Start) * locals.fT[1][tIdx]; + i.insert(to1, to2); + } + t2Start = t2; + } + t1Start = t1; + } + return i.intersected(); +} + +int intersect(const Cubic& cubic, const Quadratic& quad, Intersections& i) { + SkTDArray<double> ts; + double precision = calcPrecision(cubic); + cubic_to_quadratics(cubic, precision, ts); + double tStart = 0; + Cubic part; + int tsCount = ts.count(); + for (int idx = 0; idx <= tsCount; ++idx) { + double t = idx < tsCount ? ts[idx] : 1; + Quadratic q1; + sub_divide(cubic, tStart, t, part); + demote_cubic_to_quad(part, q1); + Intersections locals; + intersect2(q1, quad, locals); + for (int tIdx = 0; tIdx < locals.used(); ++tIdx) { + double globalT = tStart + (t - tStart) * locals.fT[0][tIdx]; + i.insertOne(globalT, 0); + globalT = locals.fT[1][tIdx]; + i.insertOne(globalT, 1); + } + tStart = t; + } + return i.used(); +} + +bool intersect(const Cubic& cubic, Intersections& i) { + SkTDArray<double> ts; + double precision = calcPrecision(cubic); + cubic_to_quadratics(cubic, precision, ts); + int tsCount = ts.count(); + if (tsCount == 1) { + return false; + } + double t1Start = 0; + Cubic part; + for (int idx = 0; idx < tsCount; ++idx) { + double t1 = ts[idx]; + Quadratic q1; + sub_divide(cubic, t1Start, t1, part); + demote_cubic_to_quad(part, q1); + double t2Start = t1; + for (int i2 = idx + 1; i2 <= tsCount; ++i2) { + const double t2 = i2 < tsCount ? ts[i2] : 1; + Quadratic q2; + sub_divide(cubic, t2Start, t2, part); + demote_cubic_to_quad(part, q2); + Intersections locals; + intersect2(q1, q2, locals); + for (int tIdx = 0; tIdx < locals.used(); ++tIdx) { + // discard intersections at cusp? (maximum curvature) + double t1sect = locals.fT[0][tIdx]; + double t2sect = locals.fT[1][tIdx]; + if (idx + 1 == i2 && t1sect == 1 && t2sect == 0) { + continue; + } + double to1 = t1Start + (t1 - t1Start) * t1sect; + double to2 = t2Start + (t2 - t2Start) * t2sect; + i.insert(to1, to2); + } + t2Start = t2; + } + t1Start = t1; + } + return i.intersected(); +} diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp index 256529c939..7d27bf40b4 100644 --- a/experimental/Intersection/CubicIntersection_Test.cpp +++ b/experimental/Intersection/CubicIntersection_Test.cpp @@ -56,3 +56,212 @@ void CubicIntersection_Test() { } } } + +static void oneOff(const Cubic& cubic1, const Cubic& cubic2) { + SkTDArray<Quadratic> quads1; + cubic_to_quadratics(cubic1, calcPrecision(cubic1), quads1); + for (int index = 0; index < quads1.count(); ++index) { + const Quadratic& q = quads1[index]; + SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, + q[1].x, q[1].y, q[2].x, q[2].y); + } + SkDebugf("\n"); + SkTDArray<Quadratic> quads2; + cubic_to_quadratics(cubic2, calcPrecision(cubic2), quads2); + for (int index = 0; index < quads2.count(); ++index) { + const Quadratic& q = quads2[index]; + SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, + q[1].x, q[1].y, q[2].x, q[2].y); + } + SkDebugf("\n"); + Intersections intersections2; + intersect2(cubic1, cubic2, intersections2); + for (int pt = 0; pt < intersections2.used(); ++pt) { + double tt1 = intersections2.fT[0][pt]; + double tx1, ty1; + xy_at_t(cubic1, tt1, tx1, ty1); + int pt2 = intersections2.fFlip ? intersections2.used() - pt - 1 : pt; + double tt2 = intersections2.fT[1][pt2]; + double tx2, ty2; + xy_at_t(cubic2, tt2, tx2, ty2); + SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__, + tt1, tx1, ty1, tx2, ty2, tt2); + } +} + +static const Cubic testSet[] = { +{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306}, {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}, +{{61.336508189019057, 82.693132843213675}, {44.639380902349664, 54.074825790745592}, {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503699973002}}, + +{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826}, {75.3863417, 18.24489}}, +{{61.3365082, 82.6931328}, {44.6393809, 54.0748258}, {16.8156155, 20.0497047}, {41.866885, 56.7355037}}, + +{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945}, {18.5656052, 32.1268808}}, +{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981}, {56.4860195, 60.529264}}, +}; + +const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]); + +void CubicIntersection_OneOffTest() { + for (size_t outer = 0; outer < testSetCount - 1; ++outer) { + SkDebugf("%s quads1[%d]\n", __FUNCTION__, outer); + const Cubic& cubic1 = testSet[outer]; + for (size_t inner = outer + 1; inner < testSetCount; ++inner) { + SkDebugf("%s quads2[%d]\n", __FUNCTION__, inner); + const Cubic& cubic2 = testSet[inner]; + oneOff(cubic1, cubic2); + } + } +} + +#define DEBUG_CRASH 1 + +class CubicChopper { +public: + +// only finds one intersection +CubicChopper(const Cubic& c1, const Cubic& c2) + : cubic1(c1) + , cubic2(c2) + , depth(0) { +} + +bool intersect(double minT1, double maxT1, double minT2, double maxT2) { + Cubic sub1, sub2; + // FIXME: carry last subdivide and reduceOrder result with cubic + sub_divide(cubic1, minT1, maxT1, sub1); + sub_divide(cubic2, minT2, maxT2, sub2); + Intersections i; + intersect2(sub1, sub2, i); + if (i.used() == 0) { + return false; + } + double x1, y1, x2, y2; + t1 = minT1 + i.fT[0][0] * (maxT1 - minT1); + t2 = minT2 + i.fT[1][0] * (maxT2 - minT2); + xy_at_t(cubic1, t1, x1, y1); + xy_at_t(cubic2, t2, x2, y2); + if (AlmostEqualUlps(x1, x2) && AlmostEqualUlps(y1, y2)) { + return true; + } + double half1 = (minT1 + maxT1) / 2; + double half2 = (minT2 + maxT2) / 2; + ++depth; + bool result; + if (depth & 1) { + result = intersect(minT1, half1, minT2, maxT2) || intersect(half1, maxT1, minT2, maxT2) + || intersect(minT1, maxT1, minT2, half2) || intersect(minT1, maxT1, half2, maxT2); + } else { + result = intersect(minT1, maxT1, minT2, half2) || intersect(minT1, maxT1, half2, maxT2) + || intersect(minT1, half1, minT2, maxT2) || intersect(half1, maxT1, minT2, maxT2); + } + --depth; + return result; +} + +const Cubic& cubic1; +const Cubic& cubic2; +double t1; +double t2; +int depth; +}; + +#define TRY_OLD 0 // old way fails on test == 1 + +void CubicIntersection_RandTest() { + srand(0); + const int tests = 1000000; // 10000000; + double largestFactor = DBL_MAX; + for (int test = 0; test < tests; ++test) { + Cubic cubic1, cubic2; + for (int i = 0; i < 4; ++i) { + cubic1[i].x = (double) rand() / RAND_MAX * 100; + cubic1[i].y = (double) rand() / RAND_MAX * 100; + cubic2[i].x = (double) rand() / RAND_MAX * 100; + cubic2[i].y = (double) rand() / RAND_MAX * 100; + } + if (test == 2513) { // the pair crosses three times, but the quadratic approximation + continue; // only sees one -- should be OK to ignore the other two? + } + if (test == 12932) { // this exposes a weakness when one cubic touches the other but + continue; // does not touch the quad approximation. Captured in qc.htm as cubic15 + } + #if DEBUG_CRASH + char str[1024]; + sprintf(str, "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n" + "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", + cubic1[0].x, cubic1[0].y, cubic1[1].x, cubic1[1].y, cubic1[2].x, cubic1[2].y, + cubic1[3].x, cubic1[3].y, + cubic2[0].x, cubic2[0].y, cubic2[1].x, cubic2[1].y, cubic2[2].x, cubic2[2].y, + cubic2[3].x, cubic2[3].y); + #endif + _Rect rect1, rect2; + rect1.setBounds(cubic1); + rect2.setBounds(cubic2); + bool boundsIntersect = rect1.left <= rect2.right && rect2.left <= rect2.right + && rect1.top <= rect2.bottom && rect2.top <= rect1.bottom; + Intersections i1, i2; + #if TRY_OLD + bool oldIntersects = intersect(cubic1, cubic2, i1); + #else + bool oldIntersects = false; + #endif + if (test == -1) { + SkDebugf("ready...\n"); + } + bool newIntersects = intersect2(cubic1, cubic2, i2); + if (!boundsIntersect && (oldIntersects || newIntersects)) { + SkDebugf("%s %d unexpected intersection boundsIntersect=%d oldIntersects=%d" + " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect, + oldIntersects, newIntersects, __FUNCTION__, str); + assert(0); + } + if (oldIntersects && !newIntersects) { + SkDebugf("%s %d missing intersection oldIntersects=%d newIntersects=%d\n%s %s\n", + __FUNCTION__, test, oldIntersects, newIntersects, __FUNCTION__, str); + assert(0); + } + if (!oldIntersects && !newIntersects) { + continue; + } + if (i2.used() > 1) { + continue; + // just look at single intercepts for simplicity + } + Intersections self1, self2; // self-intersect checks + if (intersect(cubic1, self1)) { + continue; + } + if (intersect(cubic2, self2)) { + continue; + } + // binary search for range necessary to enclose real intersection + CubicChopper c(cubic1, cubic2); + bool result = c.intersect(0, 1, 0, 1); + if (!result) { + // FIXME: a failure here probably means that a core routine used by CubicChopper is failing + continue; + } + double delta1 = fabs(c.t1 - i2.fT[0][0]); + double delta2 = fabs(c.t2 - i2.fT[1][0]); + double calc1 = calcPrecision(cubic1); + double calc2 = calcPrecision(cubic2); + double factor1 = calc1 / delta1; + double factor2 = calc2 / delta2; + SkDebugf("%s %d calc1=%1.9g delta1=%1.9g factor1=%1.9g calc2=%1.9g delta2=%1.9g" + " factor2=%1.9g\n", __FUNCTION__, test, + calc1, delta1, factor1, calc2, delta2, factor2); + if (factor1 < largestFactor) { + SkDebugf("WE HAVE A WINNER! %1.9g\n", factor1); + SkDebugf("%s\n", str); + oneOff(cubic1, cubic2); + largestFactor = factor1; + } + if (factor2 < largestFactor) { + SkDebugf("WE HAVE A WINNER! %1.9g\n", factor2); + SkDebugf("%s\n", str); + oneOff(cubic1, cubic2); + largestFactor = factor2; + } + } +} diff --git a/experimental/Intersection/CubicIntersection_TestData.cpp b/experimental/Intersection/CubicIntersection_TestData.cpp index 645d7b04b9..c138a672da 100644 --- a/experimental/Intersection/CubicIntersection_TestData.cpp +++ b/experimental/Intersection/CubicIntersection_TestData.cpp @@ -4,7 +4,6 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ -#define IN_TEST 1 #include "CubicIntersection_TestData.h" #include <limits> diff --git a/experimental/Intersection/CubicIntersection_TestData.h b/experimental/Intersection/CubicIntersection_TestData.h index 27436f8dc7..9893b3c1ac 100644 --- a/experimental/Intersection/CubicIntersection_TestData.h +++ b/experimental/Intersection/CubicIntersection_TestData.h @@ -4,11 +4,8 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ -#if !defined(IN_TEST) - #define IN_TEST 1 -#endif - #include "DataTypes.h" +#include "DataTypes_Test.h" extern const Cubic pointDegenerates[]; extern const Cubic notPointDegenerates[]; diff --git a/experimental/Intersection/CubicReduceOrder.cpp b/experimental/Intersection/CubicReduceOrder.cpp index d1775d89f2..fdc7265923 100644 --- a/experimental/Intersection/CubicReduceOrder.cpp +++ b/experimental/Intersection/CubicReduceOrder.cpp @@ -149,22 +149,17 @@ static int check_linear(const Cubic& cubic, Cubic& reduction, bool isLinear(const Cubic& cubic, int startIndex, int endIndex) { LineParameters lineParameters; lineParameters.cubicEndPoints(cubic, startIndex, endIndex); - double normalSquared = lineParameters.normalSquared(); - double distance[2]; // distance is not normalized + // FIXME: maybe it's possible to avoid this and compare non-normalized + lineParameters.normalize(); int mask = other_two(startIndex, endIndex); int inner1 = startIndex ^ mask; int inner2 = endIndex ^ mask; - lineParameters.controlPtDistance(cubic, inner1, inner2, distance); - double limit = normalSquared; - int index; - for (index = 0; index < 2; ++index) { - double distSq = distance[index]; - distSq *= distSq; - if (approximately_greater(distSq, limit)) { - return false; - } + double distance = lineParameters.controlPtDistance(cubic, inner1); + if (!approximately_zero(distance)) { + return false; } - return true; + distance = lineParameters.controlPtDistance(cubic, inner2); + return approximately_zero(distance); } /* food for thought: diff --git a/experimental/Intersection/CubicToQuadratics.cpp b/experimental/Intersection/CubicToQuadratics.cpp index 424836c633..ff6d7a228b 100644 --- a/experimental/Intersection/CubicToQuadratics.cpp +++ b/experimental/Intersection/CubicToQuadratics.cpp @@ -40,11 +40,18 @@ Tdiv>=1 - the entire cubic can be approximated by the mid-point approximation confirmed by (maybe stolen from) http://www.caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html +// maybe in turn derived from http://www.cccg.ca/proceedings/2004/36.pdf +// also stored at http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf */ #include "CubicUtilities.h" #include "CurveIntersection.h" +#include "LineIntersection.h" + +const bool AVERAGE_END_POINTS = true; // results in better fitting curves + +#define USE_CUBIC_END_POINTS 1 static double calcTDiv(const Cubic& cubic, double precision, double start) { const double adjust = sqrt(3) / 36; @@ -62,54 +69,105 @@ static double calcTDiv(const Cubic& cubic, double precision, double start) { double dy = c[3].y - 3 * (c[2].y - c[1].y) - c[0].y; double dist = sqrt(dx * dx + dy * dy); double tDiv3 = precision / (adjust * dist); - return cube_root(tDiv3); + double t = cube_root(tDiv3); + if (start > 0) { + t = start + (1 - start) * t; + } + return t; } -static void demote(const Cubic& cubic, Quadratic& quad) { +void demote_cubic_to_quad(const Cubic& cubic, Quadratic& quad) { quad[0] = cubic[0]; - quad[1].x = (cubic[3].x - 3 * (cubic[2].x - cubic[1].x) - cubic[0].x) / 4; - quad[1].y = (cubic[3].y - 3 * (cubic[2].y - cubic[1].y) - cubic[0].y) / 4; +if (AVERAGE_END_POINTS) { + const _Point fromC1 = { (3 * cubic[1].x - cubic[0].x) / 2, (3 * cubic[1].y - cubic[0].y) / 2 }; + const _Point fromC2 = { (3 * cubic[2].x - cubic[3].x) / 2, (3 * cubic[2].y - cubic[3].y) / 2 }; + quad[1].x = (fromC1.x + fromC2.x) / 2; + quad[1].y = (fromC1.y + fromC2.y) / 2; +} else { + lineIntersect((const _Line&) cubic[0], (const _Line&) cubic[2], quad[1]); +} quad[2] = cubic[3]; } int cubic_to_quadratics(const Cubic& cubic, double precision, SkTDArray<Quadratic>& quadratics) { - quadratics.setCount(1); // FIXME: every place I have setCount(), I also want setReserve() + SkTDArray<double> ts; + cubic_to_quadratics(cubic, precision, ts); + int tsCount = ts.count(); + double t1Start = 0; + int order = 0; + for (int idx = 0; idx <= tsCount; ++idx) { + double t1 = idx < tsCount ? ts[idx] : 1; + Cubic part; + sub_divide(cubic, t1Start, t1, part); + Quadratic q1; + demote_cubic_to_quad(part, q1); + Quadratic s1; + int o1 = reduceOrder(q1, s1); + if (order < o1) { + order = o1; + } + memcpy(quadratics.append(), o1 < 2 ? s1 : q1, sizeof(Quadratic)); + t1Start = t1; + } + return order; +} + +static bool addSimpleTs(const Cubic& cubic, double precision, SkTDArray<double>& ts) { + double tDiv = calcTDiv(cubic, precision, 0); + if (tDiv >= 1) { + return true; + } + if (tDiv >= 0.5) { + *ts.append() = 0.5; + return true; + } + return false; +} + +static void addTs(const Cubic& cubic, double precision, double start, double end, + SkTDArray<double>& ts) { + double tDiv = calcTDiv(cubic, precision, 0); + double parts = ceil(1.0 / tDiv); + for (double index = 0; index < parts; ++index) { + double newT = start + (index / parts) * (end - start); + if (newT > 0 && newT < 1) { + *ts.append() = newT; + } + } +} + +// flavor that returns T values only, deferring computing the quads until they are needed +void cubic_to_quadratics(const Cubic& cubic, double precision, SkTDArray<double>& ts) { Cubic reduced; int order = reduceOrder(cubic, reduced, kReduceOrder_QuadraticsAllowed); if (order < 3) { - memcpy(quadratics[0], reduced, order * sizeof(_Point)); - return order; + return; } - double tDiv = calcTDiv(cubic, precision, 0); - if (approximately_greater_than_one(tDiv)) { - demote(cubic, quadratics[0]); - return 3; + double inflectT[2]; + int inflections = find_cubic_inflections(cubic, inflectT); + SkASSERT(inflections <= 2); + if (inflections == 0 && addSimpleTs(cubic, precision, ts)) { + return; } - if (tDiv >= 0.5) { + if (inflections == 1) { CubicPair pair; - chop_at(cubic, pair, 0.5); - quadratics.setCount(2); - demote(pair.first(), quadratics[0]); - demote(pair.second(), quadratics[1]); - return 3; + chop_at(cubic, pair, inflectT[0]); + addTs(pair.first(), precision, 0, inflectT[0], ts); + addTs(pair.second(), precision, inflectT[0], 1, ts); + return; } - double start = 0; - int index = -1; - // if we iterate but make little progress, check to see if the curve is flat - // or if the control points are tangent to each other - do { - Cubic part; - sub_divide(cubic, start, tDiv, part); - quadratics.append(); - demote(part, quadratics[++index]); - if (tDiv == 1) { - break; + if (inflections == 2) { + if (inflectT[0] > inflectT[1]) { + SkTSwap(inflectT[0], inflectT[1]); } - start = tDiv; - tDiv = calcTDiv(cubic, precision, start); - if (tDiv > 1) { - tDiv = 1; - } - } while (true); - return 3; + Cubic part; + sub_divide(cubic, 0, inflectT[0], part); + addTs(part, precision, 0, inflectT[0], ts); + sub_divide(cubic, inflectT[0], inflectT[1], part); + addTs(part, precision, inflectT[0], inflectT[1], ts); + sub_divide(cubic, inflectT[1], 1, part); + addTs(part, precision, inflectT[1], 1, ts); + return; + } + addTs(cubic, precision, 0, 1, ts); } diff --git a/experimental/Intersection/CubicToQuadratics_Test.cpp b/experimental/Intersection/CubicToQuadratics_Test.cpp index 24c0ffe03a..843833f92f 100644 --- a/experimental/Intersection/CubicToQuadratics_Test.cpp +++ b/experimental/Intersection/CubicToQuadratics_Test.cpp @@ -3,21 +3,14 @@ #include "Intersection_Tests.h" #include "QuadraticIntersection_TestData.h" #include "TestUtilities.h" +#include "SkGeometry.h" -static double calcPrecision(const Cubic& cubic) { - _Rect dRect; - dRect.setBounds(cubic); - double width = dRect.right - dRect.left; - double height = dRect.bottom - dRect.top; - return (width > height ? width : height) / 256; -} - -static void test(const Cubic(& cubics)[], const char* name, int firstTest, size_t testCount) { +static void test(const Cubic* cubics, const char* name, int firstTest, size_t testCount) { SkTDArray<Quadratic> quads; for (size_t index = firstTest; index < testCount; ++index) { const Cubic& cubic = cubics[index]; double precision = calcPrecision(cubic); - cubic_to_quadratics(cubic, precision, quads); + (void) cubic_to_quadratics(cubic, precision, quads); if (quads.count() != 1) { printf("%s [%d] cubic to quadratics failed count=%d\n", name, (int) index, quads.count()); @@ -25,14 +18,14 @@ static void test(const Cubic(& cubics)[], const char* name, int firstTest, size_ } } -static void test(const Quadratic(& quadTests)[], const char* name, int firstTest, size_t testCount) { +static void test(const Quadratic* quadTests, const char* name, int firstTest, size_t testCount) { SkTDArray<Quadratic> quads; for (size_t index = firstTest; index < testCount; ++index) { const Quadratic& quad = quadTests[index]; Cubic cubic; quad_to_cubic(quad, cubic); double precision = calcPrecision(cubic); - cubic_to_quadratics(cubic, precision, quads); + (void) cubic_to_quadratics(cubic, precision, quads); if (quads.count() != 1) { printf("%s [%d] cubic to quadratics failed count=%d\n", name, (int) index, quads.count()); @@ -40,7 +33,7 @@ static void test(const Quadratic(& quadTests)[], const char* name, int firstTest } } -static void testC(const Cubic(& cubics)[], const char* name, int firstTest, size_t testCount) { +static void testC(const Cubic* cubics, const char* name, int firstTest, size_t testCount) { SkTDArray<Quadratic> quads; // test if computed line end points are valid for (size_t index = firstTest; index < testCount; ++index) { @@ -63,15 +56,15 @@ static void testC(const Cubic(& cubics)[], const char* name, int firstTest, size } } -static void testC(const Cubic(& cubics)[][2], const char* name, int firstTest, size_t testCount) { +static void testC(const Cubic(* cubics)[2], const char* name, int firstTest, size_t testCount) { SkTDArray<Quadratic> quads; for (size_t index = firstTest; index < testCount; ++index) { for (int idx2 = 0; idx2 < 2; ++idx2) { const Cubic& cubic = cubics[index][idx2]; double precision = calcPrecision(cubic); int order = cubic_to_quadratics(cubic, precision, quads); - assert(order != 4); - if (order < 3) { + assert(order != 4); + if (order < 3) { continue; } if (!AlmostEqualUlps(cubic[0].x, quads[0][0].x) @@ -136,6 +129,8 @@ void CubicToQuadratics_Test() { } static Cubic locals[] = { + {{14.5975863, 41.632436}, {16.3518929, 26.2639684}, {18.5165519, 7.68775139}, {8.03767257, 89.1628526}}, + {{69.7292014, 38.6877352}, {24.7648688, 23.1501713}, {84.9283191, 90.2588441}, {80.392774, 61.3533852}}, {{ 60.776536520932126, 71.249307306133829 @@ -148,39 +143,113 @@ static Cubic locals[] = { }, { 45.261946574441133, 17.536076632112298 - }} + }}, }; static size_t localsCount = sizeof(locals) / sizeof(locals[0]); +#define DEBUG_CRASH 0 +#define TEST_AVERAGE_END_POINTS 0 // must take const off to test +extern const bool AVERAGE_END_POINTS; + void CubicsToQuadratics_RandTest() { for (size_t x = 0; x < localsCount; ++x) { const Cubic& cubic = locals[x]; + const SkPoint skcubic[4] = {{(float) cubic[0].x, (float) cubic[0].y}, + {(float) cubic[1].x, (float) cubic[1].y}, {(float) cubic[2].x, (float) cubic[2].y}, + {(float) cubic[3].x, (float) cubic[3].y}}; + SkScalar skinflect[2]; + int skin = SkFindCubicInflections(skcubic, skinflect); + SkDebugf("%s %d %1.9g\n", __FUNCTION__, skin, skinflect[0]); SkTDArray<Quadratic> quads; double precision = calcPrecision(cubic); - cubic_to_quadratics(cubic, precision, quads); + (void) cubic_to_quadratics(cubic, precision, quads); + SkDebugf("%s quads=%d\n", __FUNCTION__, quads.count()); } srand(0); - const int arrayMax = 1000; - const int tests = 1000000; + const int arrayMax = 8; + const int sampleMax = 10; + const int tests = 1000000; // 10000000; int quadDist[arrayMax]; bzero(quadDist, sizeof(quadDist)); + Cubic samples[arrayMax][sampleMax]; + int sampleCount[arrayMax]; + bzero(sampleCount, sizeof(sampleCount)); for (int x = 0; x < tests; ++x) { Cubic cubic; for (int i = 0; i < 4; ++i) { cubic[i].x = (double) rand() / RAND_MAX * 100; cubic[i].y = (double) rand() / RAND_MAX * 100; } + #if DEBUG_CRASH + char str[1024]; + sprintf(str, "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", + cubic[0].x, cubic[0].y, cubic[1].x, cubic[1].y, cubic[2].x, cubic[2].y, + cubic[3].x, cubic[3].y); + #endif SkTDArray<Quadratic> quads; double precision = calcPrecision(cubic); - cubic_to_quadratics(cubic, precision, quads); - assert(quads.count() < arrayMax); - quadDist[quads.count()]++; + (void) cubic_to_quadratics(cubic, precision, quads); + int count = quads.count(); + assert(count > 0); + assert(--count < arrayMax); + quadDist[count]++; + int sCount = sampleCount[count]; + if (sCount < sampleMax) { + memcpy(samples[count][sCount], cubic, sizeof(Cubic)); + sampleCount[count]++; + } } for (int x = 0; x < arrayMax; ++x) { if (!quadDist[x]) { continue; } - printf("%d 1.9%g%%\n", x, (double) quadDist[x] / tests * 100); + SkDebugf("%d %1.9g%%\n", x + 1, (double) quadDist[x] / tests * 100); + } + SkDebugf("\n"); + for (int x = 0; x < arrayMax; ++x) { + for (int y = 0; y < sampleCount[x]; ++y) { +#if TEST_AVERAGE_END_POINTS + for (int w = 0; w < 2; ++w) { + AVERAGE_END_POINTS = w; +#else + int w = 0; +#endif + SkDebugf("<div id=\"cubic%dx%d%s\">\n", x + 1, y, w ? "x" : ""); + const Cubic& cubic = samples[x][y]; + SkDebugf("{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", + cubic[0].x, cubic[0].y, cubic[1].x, cubic[1].y, cubic[2].x, cubic[2].y, + cubic[3].x, cubic[3].y); + SkTDArray<Quadratic> quads; + double precision = calcPrecision(cubic); + (void) cubic_to_quadratics(cubic, precision, quads); + for (int z = 0; z < quads.count(); ++z) { + const Quadratic& quad = quads[z]; + SkDebugf("{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", + quad[0].x, quad[0].y, quad[1].x, quad[1].y, quad[2].x, quad[2].y); + } + SkDebugf("</div>\n\n"); +#if TEST_AVERAGE_END_POINTS + } +#endif + } + } + SkDebugf("</div>\n\n"); + SkDebugf("<script type=\"text/javascript\">\n\n"); + SkDebugf("var testDivs = [\n"); + for (int x = 0; x < arrayMax; ++x) { + for (int y = 0; y < sampleCount[x]; ++y) { +#if TEST_AVERAGE_END_POINTS + for (int w = 0; w < 2; ++w) { +#else + int w = 0; +#endif + SkDebugf(" cubic%dx%d%s,\n", x + 1, y, w ? "x" : ""); +#if TEST_AVERAGE_END_POINTS + } +#endif + } } + SkDebugf("\n\n\n"); + SkDebugf("%s end\n", __FUNCTION__); } diff --git a/experimental/Intersection/CubicUtilities.cpp b/experimental/Intersection/CubicUtilities.cpp index 958cabb316..36aa9e8fde 100644 --- a/experimental/Intersection/CubicUtilities.cpp +++ b/experimental/Intersection/CubicUtilities.cpp @@ -7,6 +7,14 @@ #include "CubicUtilities.h" #include "QuadraticUtilities.h" +double calcPrecision(const Cubic& cubic) { + _Rect dRect; + dRect.setBounds(cubic); + double width = dRect.right - dRect.left; + double height = dRect.bottom - dRect.top; + return (width > height ? width : height) / 256; +} + void coefficients(const double* cubic, double& A, double& B, double& C, double& D) { A = cubic[6]; // d B = cubic[4] * 3; // 3*c @@ -93,15 +101,6 @@ double derivativeAtT(const double* cubic, double t) { return (b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t; } -// same as derivativeAtT -// which is more accurate? which is faster? -double derivativeAtT_2(const double* cubic, double t) { - double a = cubic[2] - cubic[0]; - double b = cubic[4] - 2 * cubic[2] + cubic[0]; - double c = cubic[6] + 3 * (cubic[2] - cubic[4]) - cubic[0]; - return c * c * t * t + 2 * b * t + a; -} - void dxdy_at_t(const Cubic& cubic, double t, double& dx, double& dy) { if (&dx) { dx = derivativeAtT(&cubic[0].x, t); @@ -111,6 +110,17 @@ void dxdy_at_t(const Cubic& cubic, double t, double& dx, double& dy) { } } +int find_cubic_inflections(const Cubic& src, double tValues[]) +{ + double Ax = src[1].x - src[0].x; + double Ay = src[1].y - src[0].y; + double Bx = src[2].x - 2 * src[1].x + src[0].x; + double By = src[2].y - 2 * src[1].y + src[0].y; + double Cx = src[3].x + 3 * (src[1].x - src[2].x) - src[0].x; + double Cy = src[3].y + 3 * (src[1].y - src[2].y) - src[0].y; + return quadraticRoots(Bx * Cy - By * Cx, (Ax * Cy - Ay * Cx) / 2, Ax * By - Ay * Bx, tValues); +} + bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath) { double dy = cubic[index].y - cubic[zero].y; double dx = cubic[index].x - cubic[zero].x; diff --git a/experimental/Intersection/CubicUtilities.h b/experimental/Intersection/CubicUtilities.h index 890ff00732..6159472f7e 100644 --- a/experimental/Intersection/CubicUtilities.h +++ b/experimental/Intersection/CubicUtilities.h @@ -10,15 +10,18 @@ #include "DataTypes.h" #include "SkTDArray.h" +double calcPrecision(const Cubic& cubic); double cube_root(double x); int cubic_to_quadratics(const Cubic& cubic, double precision, SkTDArray<Quadratic>& quadratics); +void cubic_to_quadratics(const Cubic& cubic, double precision, SkTDArray<double>& ts); void coefficients(const double* cubic, double& A, double& B, double& C, double& D); int cubicRoots(double A, double B, double C, double D, double t[3]); +int cubicRootsX(double A, double B, double C, double D, double s[3]); +void demote_cubic_to_quad(const Cubic& cubic, Quadratic& quad); double derivativeAtT(const double* cubic, double t); -// competing version that should produce same results -double derivativeAtT_2(const double* cubic, double t); void dxdy_at_t(const Cubic& , double t, double& x, double& y); +int find_cubic_inflections(const Cubic& src, double tValues[]); bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath); double secondDerivativeAtT(const double* cubic, double t); void xy_at_t(const Cubic& , double t, double& x, double& y); diff --git a/experimental/Intersection/CurveIntersection.h b/experimental/Intersection/CurveIntersection.h index 664145b104..4b34b31adb 100644 --- a/experimental/Intersection/CurveIntersection.h +++ b/experimental/Intersection/CurveIntersection.h @@ -50,7 +50,11 @@ int horizontalIntersect(const Quadratic& quad, double left, double right, int horizontalIntersect(const Quadratic& quad, double left, double right, double y, bool flipped, Intersections& ); bool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); -int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]); +// the following flavor uses quadratic approximation instead of convex hulls +bool intersect2(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); +bool intersect(const Cubic& cubic, Intersections& i); // return true if cubic self-intersects +int intersect(const Cubic& cubic, const Quadratic& quad, Intersections& ); +int intersect(const Cubic& cubic, const _Line& line, Intersections& ); bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& ); int intersect(const Quadratic& quad, const _Line& line, Intersections& ); // the following flavor uses the implicit form instead of convex hulls diff --git a/experimental/Intersection/DataTypes.cpp b/experimental/Intersection/DataTypes.cpp index 2832ab2c85..2be8938e07 100644 --- a/experimental/Intersection/DataTypes.cpp +++ b/experimental/Intersection/DataTypes.cpp @@ -74,11 +74,4 @@ int UlpsDiff(float A, float B) return abs(uA.i - uB.i); } - -int FloatAsInt(float A) -{ - Float_t uA(A); - return uA.i; -} #endif - diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h index 265e3b769c..56931d49bd 100644 --- a/experimental/Intersection/DataTypes.h +++ b/experimental/Intersection/DataTypes.h @@ -23,13 +23,9 @@ inline bool AlmostEqualUlps(double A, double B) { return AlmostEqualUlps((float) // FIXME: delete int UlpsDiff(float A, float B); -int FloatAsInt(float A); -#if defined(IN_TEST) -// FIXME: move to test-only header -const double PointEpsilon = 0.000001; -const double SquaredEpsilon = PointEpsilon * PointEpsilon; -#endif +const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON; +const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON); inline bool approximately_zero(double x) { @@ -47,7 +43,11 @@ inline bool approximately_zero(float x) { } inline bool approximately_zero_squared(double x) { - return fabs(x) < FLT_EPSILON * FLT_EPSILON; + return fabs(x) < FLT_EPSILON_SQUARED; +} + +inline bool approximately_zero_sqrt(double x) { + return fabs(x) < FLT_EPSILON_SQRT; } inline bool approximately_equal(double x, double y) { @@ -107,7 +107,7 @@ inline bool approximately_positive(double x) { } inline bool approximately_positive_squared(double x) { - return x > -(FLT_EPSILON * FLT_EPSILON); + return x > -(FLT_EPSILON_SQUARED); } inline bool approximately_zero_or_more(double x) { @@ -130,6 +130,11 @@ struct _Point { double x; double y; + friend _Point operator-(const _Point& a, const _Point& b) { + _Point v = {a.x - b.x, a.y - b.y}; + return v; + } + void operator-=(const _Point& v) { x -= v.x; y -= v.y; @@ -150,7 +155,10 @@ struct _Point { return AlmostEqualUlps((float) x, (float) a.x) && AlmostEqualUlps((float) y, (float) a.y); } - + + double dot(const _Point& a) { + return x * a.x + y * a.y; + } }; typedef _Point _Line[2]; diff --git a/experimental/Intersection/DataTypes_Test.h b/experimental/Intersection/DataTypes_Test.h new file mode 100644 index 0000000000..a8f14fa112 --- /dev/null +++ b/experimental/Intersection/DataTypes_Test.h @@ -0,0 +1,7 @@ +#ifndef __DataTypes_Test_h__ +#define __DataTypes_Test_h__ + +const double PointEpsilon = 0.000001; +const double SquaredEpsilon = PointEpsilon * PointEpsilon; + +#endif diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp index 12fe30da79..79334b41ed 100644 --- a/experimental/Intersection/EdgeWalker.cpp +++ b/experimental/Intersection/EdgeWalker.cpp @@ -80,7 +80,7 @@ static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3], const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; - return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]); + return intersect(aCubic, bLine, intersections); } static int QuadIntersect(const SkPoint a[3], const SkPoint b[3], diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp index 6bad957f31..8e6e63e0ec 100644 --- a/experimental/Intersection/Intersection_Tests.cpp +++ b/experimental/Intersection/Intersection_Tests.cpp @@ -15,9 +15,12 @@ void cubecode_test(int test); void Intersection_Tests() { int testsRun = 0; + QuadraticIntersection_Test(); + CubicIntersection_OneOffTest(); + CubicIntersection_RandTest(); + SimplifyNew_Test(); CubicsToQuadratics_RandTest(); CubicToQuadratics_Test(); - SimplifyNew_Test(); Simplify4x4RectsThreaded_Test(testsRun); Simplify4x4QuadraticsThreaded_Test(testsRun); QuadLineIntersectThreaded_Test(testsRun); @@ -26,7 +29,6 @@ void Intersection_Tests() { Simplify4x4QuadralateralsThreaded_Test(testsRun); ShapeOps4x4RectsThreaded_Test(testsRun); SkDebugf("%s total testsRun=%d\n", __FUNCTION__, testsRun); - QuadraticIntersection_Test(); LineQuadraticIntersection_Test(); MiniSimplify_Test(); SimplifyAngle_Test(); diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h index 7da4e097f5..2ca1e056c8 100644 --- a/experimental/Intersection/Intersection_Tests.h +++ b/experimental/Intersection/Intersection_Tests.h @@ -4,16 +4,16 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ -#if !defined(IN_TEST) - #define IN_TEST 1 -#endif +#include "DataTypes_Test.h" void ActiveEdge_Test(); void ConvexHull_Test(); void ConvexHull_X_Test(); void CubicBezierClip_Test(); void CubicCoincidence_Test(); +void CubicIntersection_OneOffTest(); void CubicIntersection_Test(); +void CubicIntersection_RandTest(); void CubicParameterization_Test(); void CubicReduceOrder_Test(); void CubicsToQuadratics_RandTest(); diff --git a/experimental/Intersection/Intersections.cpp b/experimental/Intersection/Intersections.cpp index 3f4e8cf32b..d1e0f9bdb2 100644 --- a/experimental/Intersection/Intersections.cpp +++ b/experimental/Intersection/Intersections.cpp @@ -8,9 +8,108 @@ #include "DataTypes.h" #include "Intersections.h" +void Intersections::addCoincident(double s1, double e1, double s2, double e2) { + assert((fCoincidentUsed & 1) != 1); + for (int index = 0; index < fCoincidentUsed; index += 2) { + double cs1 = fCoincidentT[fSwap][index]; + double ce1 = fCoincidentT[fSwap][index + 1]; + bool s1in = approximately_between(cs1, s1, ce1); + bool e1in = approximately_between(cs1, e1, ce1); + double cs2 = fCoincidentT[fSwap ^ 1][index]; + double ce2 = fCoincidentT[fSwap ^ 1][index + 1]; + bool s2in = approximately_between(cs2, s2, ce2); + bool e2in = approximately_between(cs2, e2, ce2); + if ((s1in | e1in) & (s2in | e2in)) { + double lesser1 = std::min(cs1, ce1); + index += cs1 > ce1; + if (s1in < lesser1) { + fCoincidentT[fSwap][index] = s1in; + } else if (e1in < lesser1) { + fCoincidentT[fSwap][index] = e1in; + } + index ^= 1; + double greater1 = fCoincidentT[fSwap][index]; + if (s1in > greater1) { + fCoincidentT[fSwap][index] = s1in; + } else if (e1in > greater1) { + fCoincidentT[fSwap][index] = e1in; + } + index &= ~1; + double lesser2 = std::min(cs2, ce2); + index += cs2 > ce2; + if (s2in < lesser2) { + fCoincidentT[fSwap ^ 1][index] = s2in; + } else if (e2in < lesser2) { + fCoincidentT[fSwap ^ 1][index] = e2in; + } + index ^= 1; + double greater2 = fCoincidentT[fSwap ^ 1][index]; + if (s2in > greater2) { + fCoincidentT[fSwap ^ 1][index] = s2in; + } else if (e2in > greater2) { + fCoincidentT[fSwap ^ 1][index] = e2in; + } + return; + } + } + assert(fCoincidentUsed < 9); + fCoincidentT[fSwap][fCoincidentUsed] = s1; + fCoincidentT[fSwap ^ 1][fCoincidentUsed] = s2; + ++fCoincidentUsed; + fCoincidentT[fSwap][fCoincidentUsed] = e1; + fCoincidentT[fSwap ^ 1][fCoincidentUsed] = e2; + ++fCoincidentUsed; +} + void Intersections::cleanUp() { assert(fCoincidentUsed); assert(fUsed); // find any entries in fT that could be part of the coincident range } + +void Intersections::insert(double one, double two) { + assert(fUsed <= 1 || fT[0][0] < fT[0][1]); + int index; + for (index = 0; index < fUsed; ++index) { + if (approximately_equal(fT[0][index], one) + && approximately_equal(fT[1][index], two)) { + return; + } + if (fT[0][index] > one) { + break; + } + } + assert(fUsed < 9); + int remaining = fUsed - index; + if (remaining > 0) { + memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); + memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); + } + fT[0][index] = one; + fT[1][index] = two; + ++fUsed; +} + +// FIXME: all callers should be moved to regular insert. Failures are likely +// if two separate callers differ on whether ts are equal or not +void Intersections::insertOne(double t, int side) { + int used = side ? fUsed2 : fUsed; + assert(used <= 1 || fT[side][0] < fT[side][1]); + int index; + for (index = 0; index < used; ++index) { + if (approximately_equal(fT[side][index], t)) { + return; + } + if (fT[side][index] > t) { + break; + } + } + assert(used < 9); + int remaining = used - index; + if (remaining > 0) { + memmove(&fT[side][index + 1], &fT[side][index], sizeof(fT[side][0]) * remaining); + } + fT[side][index] = t; + side ? ++fUsed2 : ++fUsed; +} diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h index fe12b25902..618c2c1b56 100644 --- a/experimental/Intersection/Intersections.h +++ b/experimental/Intersection/Intersections.h @@ -7,7 +7,8 @@ #ifndef Intersections_DEFINE #define Intersections_DEFINE -#include <algorithm> // for std::min +#include <algorithm> // for std::min -- Skia doesn't have a SkMinDouble +#include "SkTypes.h" class Intersections { public: @@ -15,8 +16,9 @@ public: : fUsed(0) , fUsed2(0) , fCoincidentUsed(0) + , fFlip(false) + , fUnsortable(false) , fSwap(0) - , fFlip(0) { // OPTIMIZE: don't need to be initialized in release bzero(fT, sizeof(fT)); @@ -50,64 +52,13 @@ public: ++fCoincidentUsed; } - void addCoincident(double s1, double e1, double s2, double e2) { - assert((fCoincidentUsed & 1) != 1); - for (int index = 0; index < fCoincidentUsed; index += 2) { - double cs1 = fCoincidentT[fSwap][index]; - double ce1 = fCoincidentT[fSwap][index + 1]; - bool s1in = approximately_between(cs1, s1, ce1); - bool e1in = approximately_between(cs1, e1, ce1); - double cs2 = fCoincidentT[fSwap ^ 1][index]; - double ce2 = fCoincidentT[fSwap ^ 1][index + 1]; - bool s2in = approximately_between(cs2, s2, ce2); - bool e2in = approximately_between(cs2, e2, ce2); - if ((s1in | e1in) & (s2in | e2in)) { - double lesser1 = std::min(cs1, ce1); - index += cs1 > ce1; - if (s1in < lesser1) { - fCoincidentT[fSwap][index] = s1in; - } else if (e1in < lesser1) { - fCoincidentT[fSwap][index] = e1in; - } - index ^= 1; - double greater1 = fCoincidentT[fSwap][index]; - if (s1in > greater1) { - fCoincidentT[fSwap][index] = s1in; - } else if (e1in > greater1) { - fCoincidentT[fSwap][index] = e1in; - } - index &= ~1; - double lesser2 = std::min(cs2, ce2); - index += cs2 > ce2; - if (s2in < lesser2) { - fCoincidentT[fSwap ^ 1][index] = s2in; - } else if (e2in < lesser2) { - fCoincidentT[fSwap ^ 1][index] = e2in; - } - index ^= 1; - double greater2 = fCoincidentT[fSwap ^ 1][index]; - if (s2in > greater2) { - fCoincidentT[fSwap ^ 1][index] = s2in; - } else if (e2in > greater2) { - fCoincidentT[fSwap ^ 1][index] = e2in; - } - return; - } - } - assert(fCoincidentUsed < 9); - fCoincidentT[fSwap][fCoincidentUsed] = s1; - fCoincidentT[fSwap ^ 1][fCoincidentUsed] = s2; - ++fCoincidentUsed; - fCoincidentT[fSwap][fCoincidentUsed] = e1; - fCoincidentT[fSwap ^ 1][fCoincidentUsed] = e2; - ++fCoincidentUsed; - } + void addCoincident(double s1, double e1, double s2, double e2); // FIXME: this is necessary because curve/curve intersections are noisy // remove once curve/curve intersections are improved void cleanUp(); - int coincidentUsed() { + int coincidentUsed() const{ return fCoincidentUsed; } @@ -120,51 +71,8 @@ public: } } - void insert(double one, double two) { - assert(fUsed <= 1 || fT[0][0] < fT[0][1]); - int index; - for (index = 0; index < fUsed; ++index) { - if (approximately_equal(fT[0][index], one) - && approximately_equal(fT[1][index], two)) { - return; - } - if (fT[0][index] > one) { - break; - } - } - assert(fUsed < 9); - int remaining = fUsed - index; - if (remaining > 0) { - memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); - memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); - } - fT[0][index] = one; - fT[1][index] = two; - ++fUsed; - } - - // FIXME: all callers should be moved to regular insert. Failures are likely - // if two separate callers differ on whether ts are equal or not - void insertOne(double t, int side) { - int used = side ? fUsed2 : fUsed; - assert(used <= 1 || fT[side][0] < fT[side][1]); - int index; - for (index = 0; index < used; ++index) { - if (approximately_equal(fT[side][index], t)) { - return; - } - if (fT[side][index] > t) { - break; - } - } - assert(used < 9); - int remaining = used - index; - if (remaining > 0) { - memmove(&fT[side][index + 1], &fT[side][index], sizeof(fT[side][0]) * remaining); - } - fT[side][index] = t; - side ? ++fUsed2 : ++fUsed; - } + void insert(double one, double two); + void insertOne(double t, int side); bool intersected() const { return fUsed > 0; @@ -175,14 +83,25 @@ public: } void swap() { - fSwap ^= 1; + fSwap ^= true; + } + + void swapPts() { + int index; + for (index = 0; index < fUsed; ++index) { + SkTSwap(fT[0][index], fT[1][index]); + } } - bool swapped() { + bool swapped() const { return fSwap; } - int used() { + bool unsortable() const { + return fUnsortable; + } + + int used() const { return fUsed; } @@ -191,10 +110,10 @@ public: int fUsed; int fUsed2; int fCoincidentUsed; - int fFlip; + bool fFlip; + bool fUnsortable; private: int fSwap; }; #endif - diff --git a/experimental/Intersection/LineCubicIntersection.cpp b/experimental/Intersection/LineCubicIntersection.cpp index 91a0b7df92..333e30f0e3 100644 --- a/experimental/Intersection/LineCubicIntersection.cpp +++ b/experimental/Intersection/LineCubicIntersection.cpp @@ -77,160 +77,213 @@ So the cubic coefficients are: */ -class LineCubicIntersections : public Intersections { +class LineCubicIntersections { public: -LineCubicIntersections(const Cubic& c, const _Line& l, double r[3]) +LineCubicIntersections(const Cubic& c, const _Line& l, Intersections& i) : cubic(c) , line(l) - , range(r) { + , intersections(i) { } -int intersect() { - double slope; - double axisIntercept; - moreHorizontal = implicitLine(line, slope, axisIntercept); +// see parallel routine in line quadratic intersections +int intersectRay(double roots[3]) { + double adj = line[1].x - line[0].x; + double opp = line[1].y - line[0].y; + Cubic r; + for (int n = 0; n < 4; ++n) { + r[n].x = (cubic[n].y - line[0].y) * adj - (cubic[n].x - line[0].x) * opp; + } double A, B, C, D; - coefficients(&cubic[0].x, A, B, C, D); - double E, F, G, H; - coefficients(&cubic[0].y, E, F, G, H); - if (moreHorizontal) { - A = A * slope - E; - B = B * slope - F; - C = C * slope - G; - D = D * slope - H + axisIntercept; - } else { - A = A - E * slope; - B = B - F * slope; - C = C - G * slope; - D = D - H * slope - axisIntercept; - } - return cubicRoots(A, B, C, D, range); -} - -int horizontalIntersect(double axisIntercept) { + coefficients(&r[0].x, A, B, C, D); + return cubicRoots(A, B, C, D, roots); +} + +int intersect() { + addEndPoints(); + double rootVals[3]; + int roots = intersectRay(rootVals); + for (int index = 0; index < roots; ++index) { + double cubicT = rootVals[index]; + double lineT = findLineT(cubicT); + if (pinTs(cubicT, lineT)) { + intersections.insert(cubicT, lineT); + } + } + return intersections.fUsed; +} + +int horizontalIntersect(double axisIntercept, double roots[3]) { double A, B, C, D; coefficients(&cubic[0].y, A, B, C, D); D -= axisIntercept; - return cubicRoots(A, B, C, D, range); + return cubicRoots(A, B, C, D, roots); } -int verticalIntersect(double axisIntercept) { +int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { + addHorizontalEndPoints(left, right, axisIntercept); + double rootVals[3]; + int roots = horizontalIntersect(axisIntercept, rootVals); + for (int index = 0; index < roots; ++index) { + double x; + double cubicT = rootVals[index]; + xy_at_t(cubic, cubicT, x, *(double*) NULL); + double lineT = (x - left) / (right - left); + if (pinTs(cubicT, lineT)) { + intersections.insert(cubicT, lineT); + } + } + if (flipped) { + flip(); + } + return intersections.fUsed; +} + +int verticalIntersect(double axisIntercept, double roots[3]) { double A, B, C, D; coefficients(&cubic[0].x, A, B, C, D); D -= axisIntercept; - return cubicRoots(A, B, C, D, range); + return cubicRoots(A, B, C, D, roots); +} + +int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { + addVerticalEndPoints(top, bottom, axisIntercept); + double rootVals[3]; + int roots = verticalIntersect(axisIntercept, rootVals); + for (int index = 0; index < roots; ++index) { + double y; + double cubicT = rootVals[index]; + xy_at_t(cubic, cubicT, *(double*) NULL, y); + double lineT = (y - top) / (bottom - top); + if (pinTs(cubicT, lineT)) { + intersections.insert(cubicT, lineT); + } + } + if (flipped) { + flip(); + } + return intersections.fUsed; +} + +protected: + +void addEndPoints() +{ + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + for (int lIndex = 0; lIndex < 2; lIndex++) { + if (cubic[cIndex] == line[lIndex]) { + intersections.insert(cIndex >> 1, lIndex); + } + } + } +} + +void addHorizontalEndPoints(double left, double right, double y) +{ + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + if (cubic[cIndex].y != y) { + continue; + } + if (cubic[cIndex].x == left) { + intersections.insert(cIndex >> 1, 0); + } + if (cubic[cIndex].x == right) { + intersections.insert(cIndex >> 1, 1); + } + } +} + +void addVerticalEndPoints(double top, double bottom, double x) +{ + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + if (cubic[cIndex].x != x) { + continue; + } + if (cubic[cIndex].y == top) { + intersections.insert(cIndex >> 1, 0); + } + if (cubic[cIndex].y == bottom) { + intersections.insert(cIndex >> 1, 1); + } + } } double findLineT(double t) { - const double* cPtr; - const double* lPtr; - if (moreHorizontal) { - cPtr = &cubic[0].x; - lPtr = &line[0].x; - } else { - cPtr = &cubic[0].y; - lPtr = &line[0].y; - } - // FIXME: should fold the following in with TestUtilities.cpp xy_at_t() - double s = 1 - t; - double cubicVal = cPtr[0] * s * s * s + 3 * cPtr[2] * s * s * t - + 3 * cPtr[4] * s * t * t + cPtr[6] * t * t * t; - return (cubicVal - lPtr[0]) / (lPtr[2] - lPtr[0]); + double x, y; + xy_at_t(cubic, t, x, y); + double dx = line[1].x - line[0].x; + double dy = line[1].y - line[0].y; + if (fabs(dx) > fabs(dy)) { + return (x - line[0].x) / dx; + } + return (y - line[0].y) / dy; +} + +void flip() { + // OPTIMIZATION: instead of swapping, pass original line, use [1].y - [0].y + int roots = intersections.fUsed; + for (int index = 0; index < roots; ++index) { + intersections.fT[1][index] = 1 - intersections.fT[1][index]; + } +} + +bool pinTs(double& cubicT, double& lineT) { + if (!approximately_one_or_less(lineT)) { + return false; + } + if (!approximately_zero_or_more(lineT)) { + return false; + } + if (cubicT < 0) { + cubicT = 0; + } else if (cubicT > 1) { + cubicT = 1; + } + if (lineT < 0) { + lineT = 0; + } else if (lineT > 1) { + lineT = 1; + } + return true; } private: const Cubic& cubic; const _Line& line; -double* range; -bool moreHorizontal; - +Intersections& intersections; }; -int horizontalIntersect(const Cubic& cubic, double y, double tRange[3]) { - LineCubicIntersections c(cubic, *((_Line*) 0), tRange); - return c.horizontalIntersect(y); -} - int horizontalIntersect(const Cubic& cubic, double left, double right, double y, double tRange[3]) { - LineCubicIntersections c(cubic, *((_Line*) 0), tRange); - int result = c.horizontalIntersect(y); - for (int index = 0; index < result; ) { + LineCubicIntersections c(cubic, *((_Line*) 0), *((Intersections*) 0)); + double rootVals[3]; + int result = c.horizontalIntersect(y, rootVals); + int tCount = 0; + for (int index = 0; index < result; ++index) { double x, y; - xy_at_t(cubic, tRange[index], x, y); + xy_at_t(cubic, rootVals[index], x, y); if (x < left || x > right) { - if (--result > index) { - tRange[index] = tRange[result]; - } continue; } - ++index; + tRange[tCount++] = rootVals[index]; } return result; } int horizontalIntersect(const Cubic& cubic, double left, double right, double y, bool flipped, Intersections& intersections) { - LineCubicIntersections c(cubic, *((_Line*) 0), intersections.fT[0]); - int result = c.horizontalIntersect(y); - for (int index = 0; index < result; ) { - double x, y; - xy_at_t(cubic, intersections.fT[0][index], x, y); - if (x < left || x > right) { - if (--result > index) { - intersections.fT[0][index] = intersections.fT[0][result]; - } - continue; - } - intersections.fT[1][index] = (x - left) / (right - left); - ++index; - } - if (flipped) { - // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x - for (int index = 0; index < result; ++index) { - intersections.fT[1][index] = 1 - intersections.fT[1][index]; - } - } - return result; + LineCubicIntersections c(cubic, *((_Line*) 0), intersections); + return c.horizontalIntersect(y, left, right, flipped); } int verticalIntersect(const Cubic& cubic, double top, double bottom, double x, bool flipped, Intersections& intersections) { - LineCubicIntersections c(cubic, *((_Line*) 0), intersections.fT[0]); - int result = c.verticalIntersect(x); - for (int index = 0; index < result; ) { - double x, y; - xy_at_t(cubic, intersections.fT[0][index], x, y); - if (y < top || y > bottom) { - if (--result > index) { - intersections.fT[1][index] = intersections.fT[0][result]; - } - continue; - } - intersections.fT[0][index] = (y - top) / (bottom - top); - ++index; - } - if (flipped) { - // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x - for (int index = 0; index < result; ++index) { - intersections.fT[1][index] = 1 - intersections.fT[1][index]; - } - } - return result; + LineCubicIntersections c(cubic, *((_Line*) 0), intersections); + return c.verticalIntersect(x, top, bottom, flipped); } -int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]) { - LineCubicIntersections c(cubic, line, cRange); - int roots; - if (AlmostEqualUlps(line[0].y, line[1].y)) { - roots = c.horizontalIntersect(line[0].y); - } else { - roots = c.intersect(); - } - for (int index = 0; index < roots; ++index) { - lRange[index] = c.findLineT(cRange[index]); - } - return roots; +int intersect(const Cubic& cubic, const _Line& line, Intersections& i) { + LineCubicIntersections c(cubic, line, i); + return c.intersect(); } diff --git a/experimental/Intersection/LineCubicIntersection_Test.cpp b/experimental/Intersection/LineCubicIntersection_Test.cpp index 48754ddc1d..b81a87e421 100644 --- a/experimental/Intersection/LineCubicIntersection_Test.cpp +++ b/experimental/Intersection/LineCubicIntersection_Test.cpp @@ -36,8 +36,10 @@ void LineCubicIntersection_Test() { printf("[%d] line order=%d\n", (int) index, order2); } if (order1 == 4 && order2 == 2) { - double range1[2], range2[2]; - int roots = intersect(reduce1, reduce2, range1, range2); + Intersections i; + double* range1 = i.fT[0]; + double* range2 = i.fT[1]; + int roots = intersect(reduce1, reduce2, i); for (int pt = 0; pt < roots; ++pt) { double tt1 = range1[pt]; double tx1, ty1; diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp index ab23c442ce..5308a26474 100644 --- a/experimental/Intersection/LineIntersection.cpp +++ b/experimental/Intersection/LineIntersection.cpp @@ -9,12 +9,28 @@ #include "LineIntersection.h" #include <algorithm> // used for std::swap +/* Determine the intersection point of two lines. This assumes the lines are not parallel, + and that that the lines are infinite. + From http://en.wikipedia.org/wiki/Line-line_intersection + */ +void lineIntersect(const _Line& a, const _Line& b, _Point& p) { + double axLen = a[1].x - a[0].x; + double ayLen = a[1].y - a[0].y; + double bxLen = b[1].x - b[0].x; + double byLen = b[1].y - b[0].y; + double denom = byLen * axLen - ayLen * bxLen; + assert(denom); + double term1 = a[1].x * a[0].y - a[1].y * a[0].x; + double term2 = b[1].x * b[0].y - b[1].y * b[0].x; + p.x = (term1 * bxLen - axLen * term2) / denom; + p.y = (term1 * byLen - ayLen * term2) / denom; +} /* Determine the intersection point of two line segments Return FALSE if the lines don't intersect from: http://paulbourke.net/geometry/lineline2d/ -*/ + */ int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2]) { double axLen = a[1].x - a[0].x; @@ -27,7 +43,7 @@ int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2] byLen * axLen == ayLen * bxLen byLen * axLen - ayLen * bxLen == 0 ( == denom ) */ - double denom = byLen * axLen - ayLen * bxLen; + double denom = byLen * axLen - ayLen * bxLen; if (approximately_zero(denom)) { /* See if the axis intercepts match: ay - ax * ayLen / axLen == by - bx * ayLen / axLen diff --git a/experimental/Intersection/LineIntersection.h b/experimental/Intersection/LineIntersection.h index 33076b68e9..adb578971a 100644 --- a/experimental/Intersection/LineIntersection.h +++ b/experimental/Intersection/LineIntersection.h @@ -12,9 +12,10 @@ int horizontalIntersect(const _Line& line, double y, double tRange[2]); int horizontalLineIntersect(const _Line& line, double left, double right, double y, double tRange[2]); -int verticalLineIntersect(const _Line& line, double top, double bottom, - double x, double tRange[2]); +void lineIntersect(const _Line& a, const _Line& b, _Point& p); int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2]); bool testIntersect(const _Line& a, const _Line& b); +int verticalLineIntersect(const _Line& line, double top, double bottom, + double x, double tRange[2]); #endif diff --git a/experimental/Intersection/LineParameters.h b/experimental/Intersection/LineParameters.h index fc1bcc873a..8155ad8b4e 100644 --- a/experimental/Intersection/LineParameters.h +++ b/experimental/Intersection/LineParameters.h @@ -80,15 +80,9 @@ public: } } - void controlPtDistance(const Cubic& pts, double distance[2]) const { - for (int index = 0; index < 2; ++index) { - distance[index] = a * pts[index + 1].x + b * pts[index + 1].y + c; - } - } - - void controlPtDistance(const Cubic& pts, int i, int j, double distance[2]) const { - distance[0] = a * pts[i].x + b * pts[i].y + c; - distance[1] = a * pts[j].x + b * pts[j].y + c; + double controlPtDistance(const Cubic& pts, int index) const { + assert(index == 1 || index == 2); + return a * pts[index].x + b * pts[index].y + c; } double controlPtDistance(const Quadratic& pts) const { diff --git a/experimental/Intersection/LineParameteters_Test.cpp b/experimental/Intersection/LineParameteters_Test.cpp index 6d853255ac..326477e792 100644 --- a/experimental/Intersection/LineParameteters_Test.cpp +++ b/experimental/Intersection/LineParameteters_Test.cpp @@ -45,7 +45,8 @@ void LineParameter_Test() { const Cubic& cubic = tests[index]; lineParameters.cubicEndPoints(cubic); double denormalizedDistance[2]; - lineParameters.controlPtDistance(cubic, denormalizedDistance); + denormalizedDistance[0] = lineParameters.controlPtDistance(cubic, 1); + denormalizedDistance[1] = lineParameters.controlPtDistance(cubic, 2); double normalSquared = lineParameters.normalSquared(); size_t inner; for (inner = 0; inner < 2; ++inner) { @@ -64,7 +65,8 @@ void LineParameter_Test() { } lineParameters.normalize(); double normalizedDistance[2]; - lineParameters.controlPtDistance(cubic, normalizedDistance); + normalizedDistance[0] = lineParameters.controlPtDistance(cubic, 1); + normalizedDistance[1] = lineParameters.controlPtDistance(cubic, 2); for (inner = 0; inner < 2; ++inner) { if (AlmostEqualUlps(fabs(normalizedDistance[inner]), answers[index][inner])) { continue; diff --git a/experimental/Intersection/QuadraticImplicit.cpp b/experimental/Intersection/QuadraticImplicit.cpp index d892ae97e0..72a4186203 100644 --- a/experimental/Intersection/QuadraticImplicit.cpp +++ b/experimental/Intersection/QuadraticImplicit.cpp @@ -5,11 +5,15 @@ // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormula.html#step +#include "CubicUtilities.h" #include "CurveIntersection.h" #include "Intersections.h" #include "QuadraticParameterization.h" #include "QuarticRoot.h" #include "QuadraticUtilities.h" +#include "TSearch.h" + +#include <algorithm> // for std::min, max /* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F * and given x = at^2 + bt + c (the parameterized form) @@ -17,8 +21,15 @@ * then * 0 = A(at^2+bt+c)(at^2+bt+c)+B(at^2+bt+c)(dt^2+et+f)+C(dt^2+et+f)(dt^2+et+f)+D(at^2+bt+c)+E(dt^2+et+f)+F */ + +#if SK_DEBUG +#define QUARTIC_DEBUG 1 +#else +#define QUARTIC_DEBUG 0 +#endif -static int findRoots(const QuadImplicitForm& i, const Quadratic& q2, double roots[4]) { +static int findRoots(const QuadImplicitForm& i, const Quadratic& q2, double roots[4], + bool useCubic, bool& disregardCount) { double a, b, c; set_abc(&q2[0].x, a, b, c); double d, e, f; @@ -45,6 +56,42 @@ static int findRoots(const QuadImplicitForm& i, const Quadratic& q2, double root + i.x() * c + i.y() * f + i.c(); +#if QUARTIC_DEBUG + // create a string mathematica understands + char str[1024]; + bzero(str, sizeof(str)); + sprintf(str, "Solve[%1.19g x^4 + %1.19g x^3 + %1.19g x^2 + %1.19g x + %1.19g == 0, x]", + t4, t3, t2, t1, t0); +#endif + if (approximately_zero(t4)) { + disregardCount = true; + if (approximately_zero(t3)) { + return quadraticRootsX(t2, t1, t0, roots); + } + return cubicRootsX(t3, t2, t1, t0, roots); + } + if (approximately_zero(t0)) { // 0 is one root + disregardCount = true; + int num = cubicRootsX(t4, t3, t2, t1, roots); + for (int i = 0; i < num; ++i) { + if (approximately_zero(roots[i])) { + return num; + } + } + roots[num++] = 0; + return num; + } + if (useCubic) { + assert(approximately_zero(t4 + t3 + t2 + t1 + t0)); // 1 is one root + int num = cubicRootsX(t4, t4 + t3, -(t1 + t0), -t0, roots); // note that -C==A+B+D+E + for (int i = 0; i < num; ++i) { + if (approximately_equal(roots[i], 1)) { + return num; + } + } + roots[num++] = 1; + return num; + } return quarticRoots(t4, t3, t2, t1, t0, roots); } @@ -83,7 +130,9 @@ static bool onlyEndPtsInCommon(const Quadratic& q1, const Quadratic& q2, Interse double adj = endPt[1]->x - origX; double opp = endPt[1]->y - origY; double sign = (q1[oddMan].y - origY) * adj - (q1[oddMan].x - origX) * opp; - assert(!approximately_zero(sign)); + if (approximately_zero(sign)) { + goto tryNextHalfPlane; + } for (int n = 0; n < 3; ++n) { double test = (q2[n].y - origY) * adj - (q2[n].x - origX) * opp; if (test * sign > 0) { @@ -105,12 +154,227 @@ tryNextHalfPlane: return false; } +// http://www.blackpawn.com/texts/pointinpoly/default.html +static bool pointInTriangle(const _Point& pt, const _Line* testLines[]) { + const _Point& A = (*testLines[0])[0]; + const _Point& B = (*testLines[1])[0]; + const _Point& C = (*testLines[2])[0]; + +// Compute vectors + _Point v0 = C - A; + _Point v1 = B - A; + _Point v2 = pt - A; + +// Compute dot products + double dot00 = v0.dot(v0); + double dot01 = v0.dot(v1); + double dot02 = v0.dot(v2); + double dot11 = v1.dot(v1); + double dot12 = v1.dot(v2); + +// Compute barycentric coordinates + double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); + double u = (dot11 * dot02 - dot01 * dot12) * invDenom; + double v = (dot00 * dot12 - dot01 * dot02) * invDenom; + +// Check if point is in triangle + return (u >= 0) && (v >= 0) && (u + v < 1); +} + +static bool addIntercept(const Quadratic& q1, const Quadratic& q2, double tMin, double tMax, + Intersections& i) { + double tMid = (tMin + tMax) / 2; + _Point mid; + xy_at_t(q2, tMid, mid.x, mid.y); + _Line line; + line[0] = line[1] = mid; + double dx, dy; + dxdy_at_t(q2, tMid, dx, dy); + line[0].x -= dx; + line[0].y -= dy; + line[1].x += dx; + line[1].y += dy; + Intersections rootTs; + int roots = intersect(q1, line, rootTs); + assert(roots == 1); + _Point pt2; + xy_at_t(q1, rootTs.fT[0][0], pt2.x, pt2.y); + if (!pt2.approximatelyEqual(mid)) { + return false; + } + i.add(rootTs.fT[0][0], tMid); + return true; +} + +static bool isLinearInner(const Quadratic& q1, double t1s, double t1e, const Quadratic& q2, + double t2s, double t2e, Intersections& i) { + Quadratic hull; + sub_divide(q1, t1s, t1e, hull); + _Line line = {hull[2], hull[0]}; + const _Line* testLines[] = { &line, (const _Line*) &hull[0], (const _Line*) &hull[1] }; + size_t testCount = sizeof(testLines) / sizeof(testLines[0]); + SkTDArray<double> tsFound; + for (size_t index = 0; index < testCount; ++index) { + Intersections rootTs; + int roots = intersect(q2, *testLines[index], rootTs); + for (int idx2 = 0; idx2 < roots; ++idx2) { + double t = rootTs.fT[0][idx2]; + if (approximately_negative(t - t2s) || approximately_positive(t - t2e)) { + continue; + } + *tsFound.append() = rootTs.fT[0][idx2]; + } + } + int tCount = tsFound.count(); + if (!tCount) { + return true; + } + double tMin, tMax; + _Point dxy1, dxy2; + if (tCount == 1) { + tMin = tMax = tsFound[0]; + } else if (tCount > 1) { + QSort<double>(tsFound.begin(), tsFound.end() - 1); + tMin = tsFound[0]; + tMax = tsFound[1]; + } + _Point end; + xy_at_t(q2, t2s, end.x, end.y); + bool startInTriangle = pointInTriangle(end, testLines); + if (startInTriangle) { + tMin = t2s; + } + xy_at_t(q2, t2e, end.x, end.y); + bool endInTriangle = pointInTriangle(end, testLines); + if (endInTriangle) { + tMax = t2e; + } + int split = 0; + if (tMin != tMax || tCount > 2) { + dxdy_at_t(q2, tMin, dxy2.x, dxy2.y); + for (int index = 1; index < tCount; ++index) { + dxy1 = dxy2; + dxdy_at_t(q2, tsFound[index], dxy2.x, dxy2.y); + double dot = dxy1.dot(dxy2); + if (dot < 0) { + split = index - 1; + break; + } + } + + } + if (split == 0) { // there's one point + if (addIntercept(q1, q2, tMin, tMax, i)) { + return true; + } + i.swap(); + return isLinearInner(q2, tMin, tMax, q1, t1s, t1e, i); + } + // At this point, we have two ranges of t values -- treat each separately at the split + bool result; + if (addIntercept(q1, q2, tMin, tsFound[split - 1], i)) { + result = true; + } else { + i.swap(); + result = isLinearInner(q2, tMin, tsFound[split - 1], q1, t1s, t1e, i); + } + if (addIntercept(q1, q2, tsFound[split], tMax, i)) { + result = true; + } else { + i.swap(); + result |= isLinearInner(q2, tsFound[split], tMax, q1, t1s, t1e, i); + } + return result; +} + +static double flatMeasure(const Quadratic& q) { + _Point mid; + xy_at_t(q, 0.5, mid.x, mid.y); + double dx = q[2].x - q[0].x; + double dy = q[2].y - q[0].y; + double length = sqrt(dx * dx + dy * dy); // OPTIMIZE: get rid of sqrt + return ((mid.x - q[0].x) * dy - (mid.y - q[0].y) * dx) / length; +} + +// FIXME ? should this measure both and then use the quad that is the flattest as the line? +static bool isLinear(const Quadratic& q1, const Quadratic& q2, Intersections& i) { + double measure = flatMeasure(q1); + // OPTIMIZE: (get rid of sqrt) use approximately_zero + if (!approximately_zero_sqrt(measure)) { + return false; + } + return isLinearInner(q1, 0, 1, q2, 0, 1, i); +} + +static bool relaxedIsLinear(const Quadratic& q1, const Quadratic& q2, Intersections& i) { + double m1 = flatMeasure(q1); + double m2 = flatMeasure(q2); + if (fabs(m1) < fabs(m2)) { + isLinearInner(q1, 0, 1, q2, 0, 1, i); + return false; + } else { + isLinearInner(q2, 0, 1, q1, 0, 1, i); + return true; + } +} + +#if 0 +static void unsortableExpanse(const Quadratic& q1, const Quadratic& q2, Intersections& i) { + const Quadratic* qs[2] = { &q1, &q2 }; + // need t values for start and end of unsortable expanse on both curves + // try projecting lines parallel to the end points + i.fT[0][0] = 0; + i.fT[0][1] = 1; + int flip = -1; // undecided + for (int qIdx = 0; qIdx < 2; qIdx++) { + for (int t = 0; t < 2; t++) { + _Point dxdy; + dxdy_at_t(*qs[qIdx], t, dxdy.x, dxdy.y); + _Line perp; + perp[0] = perp[1] = (*qs[qIdx])[t == 0 ? 0 : 2]; + perp[0].x += dxdy.y; + perp[0].y -= dxdy.x; + perp[1].x -= dxdy.y; + perp[1].y += dxdy.x; + Intersections hitData; + int hits = intersectRay(*qs[qIdx ^ 1], perp, hitData); + assert(hits <= 1); + if (hits) { + if (flip < 0) { + _Point dxdy2; + dxdy_at_t(*qs[qIdx ^ 1], hitData.fT[0][0], dxdy2.x, dxdy2.y); + double dot = dxdy.dot(dxdy2); + flip = dot < 0; + i.fT[1][0] = flip; + i.fT[1][1] = !flip; + } + i.fT[qIdx ^ 1][t ^ flip] = hitData.fT[0][0]; + } + } + } + i.fUnsortable = true; // failed, probably coincident or near-coincident + i.fUsed = 2; +} +#endif + bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) { // if the quads share an end point, check to see if they overlap if (onlyEndPtsInCommon(q1, q2, i)) { return i.intersected(); } + if (onlyEndPtsInCommon(q2, q1, i)) { + i.swapPts(); + return i.intersected(); + } + // see if either quad is really a line + if (isLinear(q1, q2, i)) { + return i.intersected(); + } + if (isLinear(q2, q1, i)) { + i.swapPts(); + return i.intersected(); + } QuadImplicitForm i1(q1); QuadImplicitForm i2(q2); if (i1.implicit_match(i2)) { @@ -135,15 +399,20 @@ bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) { return i.fCoincidentUsed > 0; } double roots1[4], roots2[4]; - int rootCount = findRoots(i2, q1, roots1); + bool disregardCount1 = false; + bool disregardCount2 = false; + bool useCubic = q1[0] == q2[0] || q1[0] == q2[2] || q1[2] == q2[0]; + int rootCount = findRoots(i2, q1, roots1, useCubic, disregardCount1); // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 -#ifndef NDEBUG - int rootCount2 = -#endif - findRoots(i1, q2, roots2); - assert(rootCount == rootCount2); + int rootCount2 = findRoots(i1, q2, roots2, useCubic, disregardCount2); + #if 0 + if (rootCount != rootCount2 && !disregardCount1 && !disregardCount2) { + unsortableExpanse(q1, q2, i); + return false; + } + #endif addValidRoots(roots1, rootCount, 0, i); - addValidRoots(roots2, rootCount, 1, i); + addValidRoots(roots2, rootCount2, 1, i); if (i.insertBalanced() && i.fUsed <= 1) { if (i.fUsed == 1) { _Point xy1, xy2; @@ -157,16 +426,13 @@ bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) { return i.intersected(); } _Point pts[4]; - bool matches[4]; - int flipCheck[4]; int closest[4]; double dist[4]; int index, ndex2; - int flipIndex = 0; for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) { xy_at_t(q2, i.fT[1][ndex2], pts[ndex2].x, pts[ndex2].y); - matches[ndex2] = false; } + bool foundSomething = false; for (index = 0; index < i.fUsed; ++index) { _Point xy; xy_at_t(q1, i.fT[0][index], xy.x, xy.y); @@ -193,38 +459,41 @@ bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) { } dist[index] = distance; closest[index] = ndex2; + foundSomething = true; next: ; } } - for (index = 0; index < i.fUsed; ) { - for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) { - if (closest[index] == ndex2) { - assert(flipIndex < 4); - flipCheck[flipIndex++] = ndex2; - matches[ndex2] = true; - goto next2; - } - } - if (--i.fUsed > index) { - memmove(&i.fT[0][index], &i.fT[0][index + 1], (i.fUsed - index) * sizeof(i.fT[0][0])); - memmove(&closest[index], &closest[index + 1], (i.fUsed - index) * sizeof(closest[0])); - continue; + if (i.fUsed && i.fUsed2 && !foundSomething) { + if (relaxedIsLinear(q1, q2, i)) { + i.swapPts(); } - next2: - ++index; + return i.intersected(); } - for (ndex2 = 0; ndex2 < i.fUsed2; ) { - if (!matches[ndex2]) { - if (--i.fUsed2 > ndex2) { - memmove(&i.fT[1][ndex2], &i.fT[1][ndex2 + 1], (i.fUsed2 - ndex2) * sizeof(i.fT[1][0])); - memmove(&matches[ndex2], &matches[ndex2 + 1], (i.fUsed2 - ndex2) * sizeof(matches[0])); + double roots1Copy[4], roots2Copy[4]; + memcpy(roots1Copy, i.fT[0], i.fUsed * sizeof(double)); + memcpy(roots2Copy, i.fT[1], i.fUsed2 * sizeof(double)); + int used = 0; + do { + double lowest = DBL_MAX; + int lowestIndex = -1; + for (index = 0; index < i.fUsed; ++index) { + if (closest[index] < 0) { continue; - } + } + if (roots1Copy[index] < lowest) { + lowestIndex = index; + lowest = roots1Copy[index]; + } } - ++ndex2; - } - i.fFlip = i.fUsed >= 2 && flipCheck[0] > flipCheck[1]; - assert(i.insertBalanced()); + if (lowestIndex < 0) { + break; + } + i.fT[0][used] = roots1Copy[lowestIndex]; + i.fT[1][used] = roots2Copy[closest[lowestIndex]]; + closest[lowestIndex] = -1; + } while (++used < i.fUsed); + i.fUsed = i.fUsed2 = used; + i.fFlip = false; return i.intersected(); } diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp index bab6c73718..829dffebcc 100644 --- a/experimental/Intersection/QuadraticIntersection_Test.cpp +++ b/experimental/Intersection/QuadraticIntersection_Test.cpp @@ -59,9 +59,41 @@ static void standardTestCases() { } static const Quadratic testSet[] = { +{{53.774852327053594, 53.318060789841951}, {45.787877803416805, 51.393492026284981}, {46.703936967162392, 53.06860709822206}}, +{{46.703936967162392, 53.06860709822206}, {47.619996130907957, 54.74372217015916}, {53.020051653535361, 48.633140968832024}}, + +{{67.4265481,37.9937726}, {51.1295132,57.5422812}, {44.5947482,65.6442674}}, +{{61.3365082,82.6931328}, {54.8250789,71.6639328}, {47.7274442,61.4049645}}, + +{{50.934805397717923, 51.52391952648901}, {56.803308902971423, 44.246234610627596}, {69.776888596721406, 40.166645096692555}}, +{{50.230212796400401, 38.386469101526998}, {49.855620812184917, 38.818990392153609}, {56.356567496227363, 47.229909093319407}}, + +{{36.148792695174222, 70.336952793070424}, {36.141613037691357, 70.711654739870085}, {36.154708826402597, 71.088492662905836}}, +{{35.216235592661825, 70.580199617313212}, {36.244476835123969, 71.010897787304074}, {37.230244263238326, 71.423156953613102}}, + +// this pair is nearly coincident, and causes the quartic code to produce bad +// data. Mathematica doesn't think they touch. Graphically, I can't tell. +// it may not be so bad to pretend that they don't touch, if I can detect that +{{369.848602,145.680267}, {382.360413,121.298294}, {406.207703,121.298294}}, +{{369.850525,145.675964}, {382.362915,121.29287}, {406.211273,121.29287}}, + +{{33.567436351153468, 62.336347586395924}, {35.200980274619084, 65.038561460144479}, {36.479571811084995, 67.632178905412445}}, +{{41.349524945572696, 67.886658677862641}, {39.125562529359087, 67.429772735149214}, {35.600314083992416, 66.705372160552685}}, + +{{67.25299631583178, 21.109080184767524}, {43.617595267398613, 33.658034168577529}, {33.38371819435676, 44.214192553988745}}, +{{40.476838859398541, 39.543209911285999}, {36.701186108431131, 34.8817994016458}, {30.102144288878023, 26.739063172945315}}, + +{{25.367434474345036, 50.4712103169743}, {17.865013304933097, 37.356741010559439}, {16.818988838905465, 37.682915484123129}}, +{{16.818988838905465, 37.682915484123129}, {15.772964372877833, 38.009089957686811}, {20.624104547604965, 41.825131596683121}}, + +{{26.440225044088567, 79.695009812848298}, {26.085525979582247, 83.717928354134784}, {27.075079976297072, 84.820633667838905}}, +{{27.075079976297072, 84.820633667838905}, {28.276546859574015, 85.988574184029034}, {25.649263209500006, 87.166762066617025}}, + +{{34.879150914024962, 83.862726601601125}, {35.095810134304429, 83.693473210169543}, {35.359284111931586, 83.488069234177502}}, +{{54.503204203015471, 76.094098492518242}, {51.366889541918894, 71.609856061299155}, {46.53086955445437, 69.949863036494207}}, + {{0, 0}, {1, 0}, {0, 3}}, {{1, 0}, {0, 1}, {1, 1}}, -{{369.848602,145.680267}, {382.360413,121.298294}, {406.207703,121.298294}}, {{369.961151,137.980698}, {383.970093,121.298294}, {406.213287,121.298294}}, {{353.2948,194.351074}, {353.2948,173.767563}, {364.167572,160.819855}}, {{360.416077,166.795715}, {370.126831,147.872162}, {388.635406,147.872162}}, @@ -71,7 +103,6 @@ static const Quadratic testSet[] = { {{369.8543701171875, 145.66734313964844}, {382.36788940429688, 121.28203582763672}, {406.21844482421875, 121.28203582763672}}, {{369.96469116210938, 137.96672058105469}, {383.97555541992188, 121.28203582763672}, {406.2218017578125, 121.28203582763672}}, - {{369.850525, 145.675964}, {382.362915, 121.29287}, {406.211273, 121.29287}}, {{369.962311, 137.976044}, {383.971893, 121.29287}, {406.216125, 121.29287}}, {{400.121704, 149.468719}, {391.949493, 161.037186}, {391.949493, 181.202423}}, @@ -90,25 +121,27 @@ static void oneOffTest() { for (size_t inner = outer + 1; inner < testSetCount; ++inner) { const Quadratic& quad1 = testSet[outer]; const Quadratic& quad2 = testSet[inner]; - double tt1, tt2; Intersections intersections2; intersect2(quad1, quad2, intersections2); + if (intersections2.fUnsortable) { + continue; + } for (int pt = 0; pt < intersections2.used(); ++pt) { - tt1 = intersections2.fT[0][pt]; + double tt1 = intersections2.fT[0][pt]; double tx1, ty1; xy_at_t(quad1, tt1, tx1, ty1); int pt2 = intersections2.fFlip ? intersections2.used() - pt - 1 : pt; - tt2 = intersections2.fT[1][pt2]; + double tt2 = intersections2.fT[1][pt2]; double tx2, ty2; xy_at_t(quad2, tt2, tx2, ty2); - if (!approximately_equal(tx1, tx2)) { + if (!AlmostEqualUlps(tx1, tx2)) { SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", - __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); + __FUNCTION__, (int)outer, (int)inner, tt1, tx1, ty1, tt2, tx2, ty2); SkASSERT(0); } - if (!approximately_equal(ty1, ty2)) { + if (!AlmostEqualUlps(ty1, ty2)) { SkDebugf("%s [%d,%d] y!= t1=%g (%g,%g) t2=%g (%g,%g)\n", - __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); + __FUNCTION__, (int)outer, (int)inner, tt1, tx1, ty1, tt2, tx2, ty2); SkASSERT(0); } SkDebugf("%s [%d][%d] t1=%1.9g (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__, diff --git a/experimental/Intersection/QuadraticIntersection_TestData.h b/experimental/Intersection/QuadraticIntersection_TestData.h index 4c95d5efad..2dbf34a29c 100644 --- a/experimental/Intersection/QuadraticIntersection_TestData.h +++ b/experimental/Intersection/QuadraticIntersection_TestData.h @@ -4,11 +4,8 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ -#if !defined(IN_TEST) - #define IN_TEST 1 -#endif - #include "DataTypes.h" +#include "DataTypes_Test.h" extern const Quadratic quadraticLines[]; extern const Quadratic quadraticModEpsilonLines[]; diff --git a/experimental/Intersection/QuadraticUtilities.h b/experimental/Intersection/QuadraticUtilities.h index 5bc15eac92..3230e9beb5 100644 --- a/experimental/Intersection/QuadraticUtilities.h +++ b/experimental/Intersection/QuadraticUtilities.h @@ -4,6 +4,10 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ + +#if !defined QUADRATIC_UTILITIES_H +#define QUADRATIC_UTILITIES_H + #include "DataTypes.h" void dxdy_at_t(const Quadratic& , double t, double& x, double& y); @@ -24,5 +28,7 @@ inline void set_abc(const double* quad, double& a, double& b, double& c) { } int quadraticRoots(double A, double B, double C, double t[2]); - +int quadraticRootsX(const double A, const double B, const double C, double s[2]); void xy_at_t(const Quadratic& , double t, double& x, double& y); + +#endif diff --git a/experimental/Intersection/QuarticRoot.cpp b/experimental/Intersection/QuarticRoot.cpp index 66ce3bf415..86ea7a63fd 100644 --- a/experimental/Intersection/QuarticRoot.cpp +++ b/experimental/Intersection/QuarticRoot.cpp @@ -27,13 +27,20 @@ #include <math.h> #include "CubicUtilities.h" +#include "QuadraticUtilities.h" #include "QuarticRoot.h" +#if SK_DEBUG +#define QUARTIC_DEBUG 1 +#else +#define QUARTIC_DEBUG 0 +#endif + const double PI = 4 * atan(1); // unlike quadraticRoots in QuadraticUtilities.cpp, this does not discard // real roots <= 0 or >= 1 -static int quadraticRootsX(const double A, const double B, const double C, +int quadraticRootsX(const double A, const double B, const double C, double s[2]) { if (approximately_zero(A)) { if (approximately_zero(B)) { @@ -68,7 +75,7 @@ static int quadraticRootsX(const double A, const double B, const double C, #if USE_GEMS // unlike cubicRoots in CubicUtilities.cpp, this does not discard // real roots <= 0 or >= 1 -static int cubicRootsX(const double A, const double B, const double C, +int cubicRootsX(const double A, const double B, const double C, const double D, double s[3]) { int num; /* normal form: x^3 + Ax^2 + Bx + C = 0 */ @@ -119,7 +126,13 @@ static int cubicRootsX(const double A, const double B, const double C, } #else -static int cubicRootsX(double A, double B, double C, double D, double s[3]) { +int cubicRootsX(double A, double B, double C, double D, double s[3]) { +#if QUARTIC_DEBUG + // create a string mathematica understands + char str[1024]; + bzero(str, sizeof(str)); + sprintf(str, "Solve[%1.19g x^3 + %1.19g x^2 + %1.19g x + %1.19g == 0, x]", A, B, C, D); +#endif if (approximately_zero(A)) { // we're just a quadratic return quadraticRootsX(B, C, D, s); } @@ -202,34 +215,6 @@ static int cubicRootsX(double A, double B, double C, double D, double s[3]) { int quarticRoots(const double A, const double B, const double C, const double D, const double E, double s[4]) { - if (approximately_zero(A)) { - if (approximately_zero(B)) { - return quadraticRootsX(C, D, E, s); - } - return cubicRootsX(B, C, D, E, s); - } - int num; - int i; - if (approximately_zero(E)) { // 0 is one root - num = cubicRootsX(A, B, C, D, s); - for (i = 0; i < num; ++i) { - if (approximately_zero(s[i])) { - return num; - } - } - s[num++] = 0; - return num; - } - if (approximately_zero_squared(A + B + C + D + E)) { // 1 is one root - num = cubicRootsX(A, A + B, -(D + E), -E, s); // note that -C==A+B+D+E - for (i = 0; i < num; ++i) { - if (approximately_equal(s[i], 1)) { - return num; - } - } - s[num++] = 1; - return num; - } double u, v; /* normal form: x^4 + Ax^3 + Bx^2 + Cx + D = 0 */ const double invA = 1 / A; @@ -243,6 +228,7 @@ int quarticRoots(const double A, const double B, const double C, const double D, const double p = -3 * a2 / 8 + b; const double q = a2 * a / 8 - a * b / 2 + c; const double r = -3 * a2 * a2 / 256 + a2 * b / 16 - a * c / 4 + d; + int num; if (approximately_zero(r)) { /* no absolute term: y(y^3 + py + q) = 0 */ num = cubicRootsX(1, 0, p, q, s); @@ -250,19 +236,19 @@ int quarticRoots(const double A, const double B, const double C, const double D, } else { /* solve the resolvent cubic ... */ (void) cubicRootsX(1, -p / 2, -r, r * p / 2 - q * q / 8, s); - /* ... and take the one real solution ... */ + /* ... and take one real solution ... */ const double z = s[0]; /* ... to build two quadric equations */ u = z * z - r; v = 2 * z - p; - if (approximately_zero(u)) { + if (approximately_zero_squared(u)) { u = 0; } else if (u > 0) { u = sqrt(u); } else { return 0; } - if (approximately_zero(v)) { + if (approximately_zero_squared(v)) { v = 0; } else if (v > 0) { v = sqrt(v); @@ -273,7 +259,7 @@ int quarticRoots(const double A, const double B, const double C, const double D, num += quadraticRootsX(1, q < 0 ? v : -v, z + u, s + num); } // eliminate duplicates - for (i = 0; i < num - 1; ++i) { + for (int i = 0; i < num - 1; ++i) { for (int j = i + 1; j < num; ) { if (approximately_equal(s[i], s[j])) { if (j < --num) { @@ -286,10 +272,8 @@ int quarticRoots(const double A, const double B, const double C, const double D, } /* resubstitute */ const double sub = a / 4; - for (i = 0; i < num; ++i) { + for (int i = 0; i < num; ++i) { s[i] -= sub; } return num; } - - diff --git a/experimental/Intersection/QuarticRoot_Test.cpp b/experimental/Intersection/QuarticRoot_Test.cpp index 2fe3e728c1..0f310bb08e 100644 --- a/experimental/Intersection/QuarticRoot_Test.cpp +++ b/experimental/Intersection/QuarticRoot_Test.cpp @@ -2,12 +2,8 @@ #include <math.h> #include "CubicUtilities.h" #include "Intersection_Tests.h" - -namespace QuarticRootTest { - -#include "QuarticRoot.cpp" - -} +#include "QuadraticUtilities.h" +#include "QuarticRoot.h" double mulA[] = {-3, -1, 1, 3}; size_t mulACount = sizeof(mulA) / sizeof(mulA[0]); @@ -20,6 +16,7 @@ size_t rootDCount = sizeof(rootD) / sizeof(rootD[0]); double rootE[] = {-5, -1, 0, 1, 7}; size_t rootECount = sizeof(rootE) / sizeof(rootE[0]); + static void quadraticTest() { // (x - a)(x - b) == x^2 - (a + b)x + ab for (size_t aIndex = 0; aIndex < mulACount; ++aIndex) { @@ -31,7 +28,7 @@ static void quadraticTest() { const double b = A * (B + C); const double c = A * B * C; double roots[2]; - const int rootCount = QuarticRootTest::quadraticRootsX(A, b, c, roots); + const int rootCount = quadraticRootsX(A, b, c, roots); const int expected = 1 + (B != C); assert(rootCount == expected); assert(approximately_equal(roots[0], -B) @@ -60,7 +57,7 @@ static void cubicTest() { const double c = A * (B * C + C * D + B * D); const double d = A * B * C * D; double roots[3]; - const int rootCount = QuarticRootTest::cubicRootsX(A, b, c, d, roots); + const int rootCount = cubicRootsX(A, b, c, d, roots); const int expected = 1 + (B != C) + (B != D && C != D); assert(rootCount == expected); assert(approximately_equal(roots[0], -B) @@ -103,7 +100,7 @@ static void quarticTest() { const double d = A * (B * C * D + B * C * E + B * D * E + C * D * E); const double e = A * B * C * D * E; double roots[4]; - const int rootCount = QuarticRootTest::quarticRoots(A, b, c, d, e, roots); + const int rootCount = quarticRoots(A, b, c, d, e, roots); const int expected = 1 + (B != C) + (B != D && C != D) + (B != E && C != E && D != E); assert(rootCount == expected); assert(approximately_equal(roots[0], -B) diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index e29b0df7c0..5fd0fd5223 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -28,9 +28,10 @@ int gDebugMaxWindValue = SK_MaxS32; #define PIN_ADD_T 0 #define TRY_ROTATE 1 #define ONE_PASS_COINCIDENCE_CHECK 0 +#define APPROXIMATE_CUBICS 1 #define DEBUG_UNUSED 0 // set to expose unused functions -#define FORCE_RELEASE 1 // set force release to 1 for multiple thread -- no debugging +#define FORCE_RELEASE 0 // set force release to 1 for multiple thread -- no debugging #if FORCE_RELEASE || defined SK_RELEASE @@ -118,7 +119,7 @@ static int CubicLineIntersect(const SkPoint a[4], const SkPoint b[2], Intersections& intersections) { MAKE_CONST_CUBIC(aCubic, a); MAKE_CONST_LINE(bLine, b); - return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]); + return intersect(aCubic, bLine, intersections); } static int QuadIntersect(const SkPoint a[3], const SkPoint b[3], @@ -134,11 +135,23 @@ static int QuadIntersect(const SkPoint a[3], const SkPoint b[3], return intersections.fUsed ? intersections.fUsed : intersections.fCoincidentUsed; } -static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], +#if APPROXIMATE_CUBICS +static int CubicQuadIntersect(const SkPoint a[4], const SkPoint b[3], Intersections& intersections) { MAKE_CONST_CUBIC(aCubic, a); + MAKE_CONST_QUAD(bQuad, b); + return intersect(aCubic, bQuad, intersections); +} +#endif + +static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], Intersections& intersections) { + MAKE_CONST_CUBIC(aCubic, a); MAKE_CONST_CUBIC(bCubic, b); +#if APPROXIMATE_CUBICS + intersect2(aCubic, bCubic, intersections); +#else intersect(aCubic, bCubic, intersections); +#endif return intersections.fUsed; } @@ -1665,6 +1678,23 @@ public: other.addCancelOutsides(tStart, oStart, *this, endT); } } + + int addUnsortableT(double newT, Segment* other, bool start) { + int result = addT(newT, other); + Span* span = &fTs[result]; + if (start) { + if (result > 0) { + span[result - 1].fUnsortableEnd = true; + } + span[result].fUnsortableStart = true; + } else { + span[result].fUnsortableEnd = true; + if (result + 1 < fTs.count()) { + span[result + 1].fUnsortableStart = true; + } + } + return result; + } int bumpCoincidentThis(const Span* oTest, bool opp, int index, SkTDArray<double>& outsideTs) { @@ -2722,6 +2752,8 @@ public: int local = spanSign(start, end); int oppLocal = oppSign(start, end); (void) markAndChaseWinding(start, end, local, oppLocal); + // OPTIMIZATION: the reverse mark and chase could skip the first marking + (void) markAndChaseWinding(end, start, local, oppLocal); } void initWinding(int start, int end, int winding, int oppWinding) { @@ -4138,6 +4170,10 @@ public: return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]); } + int addUnsortableT(int segIndex, double newT, Contour* other, int otherIndex, bool start) { + return fSegments[segIndex].addUnsortableT(newT, &other->fSegments[otherIndex], start); + } + const Bounds& bounds() const { return fBounds; } @@ -4820,6 +4856,10 @@ public: return fContour->addT(fIndex, newT, other.fContour, other.fIndex); } + int addUnsortableT(double newT, const Work& other, bool start) { + return fContour->addUnsortableT(fIndex, newT, other.fContour, other.fIndex, start); + } + bool advance() { return ++fIndex < fLast; } @@ -4832,9 +4872,11 @@ public: return fContour->segments()[fIndex].bounds(); } +#if !APPROXIMATE_CUBICS const SkPoint* cubic() const { return fCubic; } +#endif void init(Contour* contour) { fContour = contour; @@ -4855,6 +4897,7 @@ public: return bounds().fLeft; } +#if !APPROXIMATE_CUBICS void promoteToCubic() { fCubic[0] = pts()[0]; fCubic[2] = pts()[1]; @@ -4864,6 +4907,7 @@ public: fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3; fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3; } +#endif const SkPoint* pts() const { return fContour->segments()[fIndex].pts(); @@ -4923,7 +4967,9 @@ public: protected: Contour* fContour; +#if !APPROXIMATE_CUBICS SkPoint fCubic[4]; +#endif int fIndex; int fLast; }; @@ -4990,6 +5036,7 @@ static void debugShowQuadLineIntersection(int pts, const Work& wt, SkDebugf("\n"); } +// FIXME: show more than two intersection points static void debugShowQuadIntersection(int pts, const Work& wt, const Work& wn, const double wtTs[2], const double wnTs[2]) { if (!pts) { @@ -5021,6 +5068,106 @@ static void debugShowQuadIntersection(int pts, const Work& wt, } SkDebugf("\n"); } + +static void debugShowCubicLineIntersection(int pts, const Work& wt, + const Work& wn, const double wtTs[2], const double wnTs[2]) { + if (!pts) { + SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" + " (%1.9g,%1.9g %1.9g,%1.9g)\n", + __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, + wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, + wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY); + return; + } + SkPoint wtOutPt, wnOutPt; + CubicXYAtT(wt.pts(), wtTs[0], &wtOutPt); + LineXYAtT(wn.pts(), wnTs[0], &wnOutPt); + SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", + __FUNCTION__, + wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, + wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, + wtOutPt.fX, wtOutPt.fY); + if (pts == 2) { + CubicXYAtT(wt.pts(), wtTs[1], &wtOutPt); + SkDebugf(" wtTs[1]=%1.9g (%1.9g,%1.9g)", wtTs[1], wtOutPt.fX, wtOutPt.fY); + } + SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", + wtTs[0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, + wnOutPt.fX, wnOutPt.fY); + if (pts == 2) { + LineXYAtT(wn.pts(), wnTs[1], &wnOutPt); + SkDebugf(" wnTs[1]=%1.9g (%1.9g,%1.9g)", wnTs[1], wnOutPt.fX, wnOutPt.fY); + } + SkDebugf("\n"); +} + +#if APPROXIMATE_CUBICS +// FIXME: show more than two intersection points +static void debugShowCubicQuadIntersection(int pts, const Work& wt, + const Work& wn, const double wtTs[2], const double wnTs[2]) { + if (!pts) { + SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" + " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n", + __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, + wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, + wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, + wn.pts()[2].fX, wn.pts()[2].fY ); + return; + } + SkPoint wtOutPt, wnOutPt; + CubicXYAtT(wt.pts(), wtTs[0], &wtOutPt); + CubicXYAtT(wn.pts(), wnTs[0], &wnOutPt); + SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", + __FUNCTION__, + wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, + wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, + wtOutPt.fX, wtOutPt.fY); + if (pts == 2) { + SkDebugf(" wtTs[1]=%1.9g", wtTs[1]); + } + SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", + wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, + wn.pts()[2].fX, wn.pts()[2].fY, + wnOutPt.fX, wnOutPt.fY); + if (pts == 2) { + SkDebugf(" wnTs[1]=%1.9g", wnTs[1]); + } + SkDebugf("\n"); +} + +// FIXME: show more than two intersection points +static void debugShowCubicIntersection(int pts, const Work& wt, + const Work& wn, const double wtTs[2], const double wnTs[2]) { + if (!pts) { + SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" + " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n", + __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, + wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, + wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, + wn.pts()[2].fX, wn.pts()[2].fY, wn.pts()[3].fX, wn.pts()[3].fY ); + return; + } + SkPoint wtOutPt, wnOutPt; + CubicXYAtT(wt.pts(), wtTs[0], &wtOutPt); + CubicXYAtT(wn.pts(), wnTs[0], &wnOutPt); + SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", + __FUNCTION__, + wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, + wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, + wtOutPt.fX, wtOutPt.fY); + if (pts == 2) { + SkDebugf(" wtTs[1]=%1.9g", wtTs[1]); + } + SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", + wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, + wn.pts()[2].fX, wn.pts()[2].fY, wn.pts()[3].fX, wn.pts()[3].fY, + wnOutPt.fX, wnOutPt.fY); + if (pts == 2) { + SkDebugf(" wnTs[1]=%1.9g", wnTs[1]); + } + SkDebugf("\n"); +} +#endif #else static void debugShowLineIntersection(int , const Work& , const Work& , const double [2], const double [2]) { @@ -5033,6 +5180,20 @@ static void debugShowQuadLineIntersection(int , const Work& , static void debugShowQuadIntersection(int , const Work& , const Work& , const double [2], const double [2]) { } + +static void debugShowCubicLineIntersection(int , const Work& , + const Work& , const double [2], const double [2]) { +} + +#if APPROXIMATE_CUBICS +static void debugShowCubicQuadIntersection(int , const Work& , + const Work& , const double [2], const double [2]) { +} + +static void debugShowCubicIntersection(int , const Work& , + const Work& , const double [2], const double [2]) { +} +#endif #endif static bool addIntersectTs(Contour* test, Contour* next) { @@ -5082,6 +5243,7 @@ static bool addIntersectTs(Contour* test, Contour* next) { case Work::kCubic_Segment: { pts = HCubicIntersect(wn.pts(), wt.left(), wt.right(), wt.y(), wt.xFlipped(), ts); + debugShowCubicLineIntersection(pts, wn, wt, ts.fT[0], ts.fT[1]); break; } default: @@ -5108,6 +5270,7 @@ static bool addIntersectTs(Contour* test, Contour* next) { case Work::kCubic_Segment: { pts = VCubicIntersect(wn.pts(), wt.top(), wt.bottom(), wt.x(), wt.yFlipped(), ts); + debugShowCubicLineIntersection(pts, wn, wt, ts.fT[0], ts.fT[1]); break; } default: @@ -5144,6 +5307,7 @@ static bool addIntersectTs(Contour* test, Contour* next) { case Work::kCubic_Segment: { swap = true; pts = CubicLineIntersect(wn.pts(), wt.pts(), ts); + debugShowCubicLineIntersection(pts, wn, wt, ts.fT[0], ts.fT[1]); break; } default: @@ -5173,8 +5337,14 @@ static bool addIntersectTs(Contour* test, Contour* next) { break; } case Work::kCubic_Segment: { + #if APPROXIMATE_CUBICS + swap = true; + pts = CubicQuadIntersect(wn.pts(), wt.pts(), ts); + debugShowCubicQuadIntersection(pts, wn, wt, ts.fT[0], ts.fT[1]); + #else wt.promoteToCubic(); pts = CubicIntersect(wt.cubic(), wn.pts(), ts); + #endif break; } default: @@ -5190,18 +5360,30 @@ static bool addIntersectTs(Contour* test, Contour* next) { case Work::kVerticalLine_Segment: pts = VCubicIntersect(wt.pts(), wn.top(), wn.bottom(), wn.x(), wn.yFlipped(), ts); + debugShowCubicLineIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]); break; case Work::kLine_Segment: { pts = CubicLineIntersect(wt.pts(), wn.pts(), ts); + debugShowCubicLineIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]); break; } case Work::kQuad_Segment: { + #if APPROXIMATE_CUBICS + pts = CubicQuadIntersect(wt.pts(), wn.pts(), ts); + debugShowCubicQuadIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]); + #else wn.promoteToCubic(); pts = CubicIntersect(wt.pts(), wn.cubic(), ts); + #endif break; } case Work::kCubic_Segment: { + #if APPROXIMATE_CUBICS + pts = CubicIntersect(wt.pts(), wn.pts(), ts); + debugShowCubicIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]); + #else pts = CubicIntersect(wt.pts(), wn.pts(), ts); + #endif break; } default: @@ -5217,6 +5399,19 @@ static bool addIntersectTs(Contour* test, Contour* next) { foundCommonContour = true; } // in addition to recording T values, record matching segment + if (ts.unsortable()) { + bool start = true; + for (int pt = 0; pt < ts.used(); ++pt) { + // FIXME: if unsortable, the other points to the original. This logic is + // untested downstream. + int testTAt = wt.addUnsortableT(ts.fT[swap][pt], wt, start); + wt.addOtherT(testTAt, ts.fT[swap][pt], testTAt); + testTAt = wn.addUnsortableT(ts.fT[!swap][pt], wn, start ^ ts.fFlip); + wn.addOtherT(testTAt, ts.fT[!swap][pt], testTAt); + start ^= true; + } + continue; + } if (pts == 2) { if (wn.segmentType() <= Work::kLine_Segment && wt.segmentType() <= Work::kLine_Segment) { @@ -6047,4 +6242,3 @@ void simplifyx(const SkPath& path, SkPath& result) { result = *assembled.nativePath(); } } - diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp index 2559e80a05..b6cc26e159 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -3510,12 +3510,40 @@ static void testLine85() { testSimplifyx(path); } -static void (*firstTest)() = testLine85; +static void testQuadralateral1() { + SkPath path; + path.moveTo(0, 0); + path.lineTo(0, 0); + path.lineTo(0, 0); + path.lineTo(3, 2); + path.close(); + path.moveTo(0, 0); + path.lineTo(2, 1); + path.lineTo(2, 2); + path.lineTo(2, 3); + path.close(); + testSimplifyx(path); +} + +static void testCubic1() { + SkPath path; + path.moveTo(0, 0); + path.cubicTo(0, 1, 1, 1, 1, 0); + path.close(); + path.moveTo(1, 0); + path.cubicTo(0, 0, 0, 1, 1, 1); + path.close(); + testSimplifyx(path); +} + +static void (*firstTest)() = 0; static struct { void (*fun)(); const char* str; } tests[] = { + TEST(testCubic1), + TEST(testQuadralateral1), TEST(testLine85), TEST(testLine84), TEST(testLine84x), @@ -3997,12 +4025,22 @@ static void testOp2u() { testShapeOp(path, pathB, kUnion_Op); } +static void testOp8d() { + SkPath path, pathB; + path.addRect(0, 0, 640, 480); + pathB.moveTo(577330, 1971.72f); + pathB.cubicTo(10.7082f, -116.596f, 262.057f, 45.6468f, 294.694f, 1.96237f); + pathB.close(); + testShapeOp(path, pathB, kDifference_Op); +} + static const size_t testCount = sizeof(tests) / sizeof(tests[0]); static struct { void (*fun)(); const char* str; } subTests[] = { + TEST(testOp8d), TEST(testDiff1), TEST(testIntersect1), TEST(testUnion1), @@ -4024,10 +4062,10 @@ static struct { static const size_t subTestCount = sizeof(subTests) / sizeof(subTests[0]); -static void (*firstBinaryTest)() = 0; +static void (*firstBinaryTest)() = testOp8d; static bool skipAll = false; -static bool runBinaryTestsFirst = false; +static bool runBinaryTestsFirst = true; static bool runReverse = false; static void (*stopTest)() = 0; diff --git a/experimental/Intersection/TSearch.h b/experimental/Intersection/TSearch.h index 010e69f5e7..6952425585 100644 --- a/experimental/Intersection/TSearch.h +++ b/experimental/Intersection/TSearch.h @@ -12,6 +12,35 @@ // FIXME: Move this templated version into SKTSearch.h template <typename T> +static T* QSort_Partition(T* left, T* right, T* pivot) +{ + T pivotValue = *pivot; + SkTSwap(*pivot, *right); + T* newPivot = left; + while (left < right) { + if (*left < pivotValue) { + SkTSwap(*left, *newPivot); + newPivot += 1; + } + left += 1; + } + SkTSwap(*newPivot, *right); + return newPivot; +} + +template <typename T> +void QSort(T* left, T* right) +{ + if (left >= right) { + return; + } + T* pivot = left + (right - left >> 1); + pivot = QSort_Partition(left, right, pivot); + QSort(left, pivot - 1); + QSort(pivot + 1, right); +} + +template <typename T> static T** QSort_Partition(T** left, T** right, T** pivot) { T* pivotValue = *pivot; diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm index 50c26e90c2..8c8a9919ea 100644 --- a/experimental/Intersection/op.htm +++ b/experimental/Intersection/op.htm @@ -3295,11 +3295,35 @@ path.addRect(4, 13, 13, 16, SkPath::kCCW_Direction); path.addRect(32, 0, 36, 41, SkPath::kCCW_Direction); </div> +<div id="testQuadralateral1"> + path.moveTo(0, 0); + path.lineTo(0, 0); + path.lineTo(0, 0); + path.lineTo(3, 2); + path.close(); + path.moveTo(0, 0); + path.lineTo(2, 1); + path.lineTo(2, 2); + path.lineTo(2, 3); + path.close(); +</div> + +<div id="testCubic1"> + path.moveTo(0, 0); + path.cubicTo(0, 1, 1, 1, 1, 0); + path.close(); + path.moveTo(1, 0); + path.cubicTo(0, 0, 0, 1, 1, 1); + path.close(); +</div> + </div> <script type="text/javascript"> var testDivs = [ + testCubic1, + testQuadralateral1, testLine85, testLine84x, testLine83, @@ -3763,9 +3787,8 @@ function draw(test, title, _at_x, _at_y, scale) { } ctx.closePath(); } - if (hasXor) { - ctx.fillType=xor; // how is this done? - } + // uncomment if ever part of the standard + // ctx.fillRule=hasXor ? evenodd : nonzero; ctx.stroke(); ctx.fillStyle="rgba(192,192,255, 0.3)"; ctx.fill(); diff --git a/experimental/Intersection/qc.htm b/experimental/Intersection/qc.htm new file mode 100644 index 0000000000..29fedab866 --- /dev/null +++ b/experimental/Intersection/qc.htm @@ -0,0 +1,2079 @@ +<html> +<head> +<div style="height:0"> + +<div id="cubic1"> +$1 = (Cubic &) @0x297c40: {{x = 60.776536520932126, y = 71.249307306133829}, {x = 87.107894191103014, y = 22.377669868235323}, {x = 1.4974754310666936, y = 68.069569937917208}, {x = 45.261946574441133, y = 17.536076632112298}} +$3 = {{{x = 60.776536520932126, y = 71.249307306133829}, {x = 66.996745328074098, y = 59.419614231505768}, {x = 65.760655441289899, y = 53.975522936482086}}, {{x = 65.760655441289899, y = 53.975522936482086}, {x = 64.524565554505699, y = 48.531431641458411}, {x = 59.040356119613065, y = 46.936502854722001}}, {{x = 59.040356119613065, y = 46.936502854722001}, {x = 53.556146684720431, y = 45.341574067985597}, {x = 47.031996847537108, y = 45.059368518219323}}, {{x = 47.031996847537108, y = 45.059368518219323}, {x = 40.29980253329046, y = 44.781843489000011}, {x = 35.915024002796116, y = 43.168182836391942}}, {{x = 35.915024002796116, y = 43.168182836391942}, {x = 31.530245472301775, y = 41.554522183783902}, {x = 32.992157437282373, y = 35.838141687728616}}, {{x = 32.992157437282373, y = 35.838141687728616}, {x = 34.454069402262967, y = 30.121761191673329}, {x = 45.261946574441133, y = 17.536076632112298}}} +</div> + +<div id="cubic2"> +$1 = {{x = 73.565270739405079, y = 11.505317181118446}, {x = 69.865863057722279, y = 35.56041113825534}, {x = 63.830000657509075, y = 90.821050755130614}, {x = 29.400041480269302, y = 26.497158886164968}} +</div> + +<div id="cubic3"> +$3 = {{x = 69.729201388419241, y = 38.687735162064307}, {x = 24.764868814854356, y = 23.150171257159752}, {x = 84.928319083959011, y = 90.258844099128083}, {x = 80.39277404565027, y = 61.35338524419506}} +</div> + +<div id="cubic1x0"> +{{14.5975863, 41.632436}, {16.3518929, 26.2639684}, {18.5165519, 7.68775139}, {8.03767257, 89.1628526}}, +{{14.5975863, 41.632436}, {8.03767257, 89.1628526}, {8.03767257, 89.1628526}}, +</div> + +<div id="cubic1x0x"> +{{14.5975863, 41.632436}, {16.3518929, 26.2639684}, {18.5165519, 7.68775139}, {8.03767257, 89.1628526}}, +{{14.5975863, 41.632436}, {8.03767257, 89.1628526}, {8.03767257, 89.1628526}}, +</div> + +<div id="cubic1x1"> +{{32.0437334, 59.0267425}, {62.4615541, 91.340573}, {61.0102145, 98.6747985}, {27.3387826, 82.9194526}}, +{{32.0437334, 59.0267425}, {75.9425223, 105.66184}, {27.3387826, 82.9194526}}, +</div> + +<div id="cubic1x1x"> +{{32.0437334, 59.0267425}, {62.4615541, 91.340573}, {61.0102145, 98.6747985}, {27.3387826, 82.9194526}}, +{{32.0437334, 59.0267425}, {77.7581975, 107.02498}, {27.3387826, 82.9194526}}, +</div> + +<div id="cubic1x2"> +{{57.8949944, 41.1707465}, {56.7368674, 76.5309905}, {56.356649, 86.19953}, {55.5002867, 93.318629}}, +{{57.8949944, 41.1707465}, {55.5002867, 93.318629}, {55.5002867, 93.318629}}, +</div> + +<div id="cubic1x2x"> +{{57.8949944, 41.1707465}, {56.7368674, 76.5309905}, {56.356649, 86.19953}, {55.5002867, 93.318629}}, +{{57.8949944, 41.1707465}, {55.5002867, 93.318629}, {55.5002867, 93.318629}}, +</div> + +<div id="cubic1x3"> +{{41.1844187, 86.52533}, {31.2211043, 33.1005529}, {20.992908, 27.8044979}, {10.1965708, 73.7658388}}, +{{41.1844187, 86.52533}, {26.1439273, 5.87597256}, {10.1965708, 73.7658388}}, +</div> + +<div id="cubic1x3x"> +{{41.1844187, 86.52533}, {31.2211043, 33.1005529}, {20.992908, 27.8044979}, {10.1965708, 73.7658388}}, +{{41.1844187, 86.52533}, {26.3152619, 5.60599593}, {10.1965708, 73.7658388}}, +</div> + +<div id="cubic1x4"> +{{51.1608132, 59.7881237}, {58.9955693, 38.5338731}, {38.8048957, 93.8817224}, {70.1083283, 10.6741861}}, +{{51.1608132, 59.7881237}, {70.1083283, 10.6741861}, {70.1083283, 10.6741861}}, +</div> + +<div id="cubic1x4x"> +{{51.1608132, 59.7881237}, {58.9955693, 38.5338731}, {38.8048957, 93.8817224}, {70.1083283, 10.6741861}}, +{{51.1608132, 59.7881237}, {70.1083283, 10.6741861}, {70.1083283, 10.6741861}}, +</div> + +<div id="cubic1x5"> +{{9.45225228, 64.0040808}, {16.5855418, 53.2003115}, {37.6356814, 42.8968969}, {68.1461999, 33.1817941}}, +{{9.45225228, 64.0040808}, {19.5957859, 48.641127}, {68.1461999, 33.1817941}}, +</div> + +<div id="cubic1x5x"> +{{9.45225228, 64.0040808}, {16.5855418, 53.2003115}, {37.6356814, 42.8968969}, {68.1461999, 33.1817941}}, +{{9.45225228, 64.0040808}, {21.2663043, 47.7764376}, {68.1461999, 33.1817941}}, +</div> + +<div id="cubic1x6"> +{{96.2293269, 26.2973682}, {79.8675829, 34.4649929}, {53.1353046, 45.0651411}, {9.82676512, 58.4413866}}, +{{96.2293269, 26.2973682}, {67.554114, 40.6117577}, {9.82676512, 58.4413866}}, +</div> + +<div id="cubic1x6x"> +{{96.2293269, 26.2973682}, {79.8675829, 34.4649929}, {53.1353046, 45.0651411}, {9.82676512, 58.4413866}}, +{{96.2293269, 26.2973682}, {73.2381426, 38.4629118}, {9.82676512, 58.4413866}}, +</div> + +<div id="cubic1x7"> +{{77.9926032, 21.6823036}, {14.4765247, 6.95017395}, {11.5735665, 16.9314125}, {66.2493838, 53.3932579}}, +{{77.9926032, 21.6823036}, {-12.9236155, 0.594894684}, {66.2493838, 53.3932579}}, +</div> + +<div id="cubic1x7x"> +{{77.9926032, 21.6823036}, {14.4765247, 6.95017395}, {11.5735665, 16.9314125}, {66.2493838, 53.3932579}}, +{{77.9926032, 21.6823036}, {-16.5229284, -0.857700571}, {66.2493838, 53.3932579}}, +</div> + +<div id="cubic1x8"> +{{56.479229, 46.4012343}, {65.5444116, 4.92526628}, {78.9504195, 19.6997536}, {93.7579262, 89.4649302}}, +{{56.479229, 46.4012343}, {70.7547833, -18.9137695}, {93.7579262, 89.4649302}}, +</div> + +<div id="cubic1x8x"> +{{56.479229, 46.4012343}, {65.5444116, 4.92526628}, {78.9504195, 19.6997536}, {93.7579262, 89.4649302}}, +{{56.479229, 46.4012343}, {70.8118345, -15.4977762}, {93.7579262, 89.4649302}}, +</div> + +<div id="cubic1x9"> +{{14.1826743, 68.2075081}, {63.5890486, 41.1398453}, {37.3805687, 55.2173676}, {38.296851, 55.1751163}}, +{{14.1826743, 68.2075081}, {38.296851, 55.1751163}, {38.296851, 55.1751163}}, +</div> + +<div id="cubic1x9x"> +{{14.1826743, 68.2075081}, {63.5890486, 41.1398453}, {37.3805687, 55.2173676}, {38.296851, 55.1751163}}, +{{14.1826743, 68.2075081}, {38.296851, 55.1751163}, {38.296851, 55.1751163}}, +</div> + +<div id="cubic2x0"> +{{27.9052884, 4.18132628}, {75.550717, 80.9000193}, {86.6244633, 97.3541595}, {31.358766, 46.7795742}}, +{{27.9052884, 4.18132628}, {66.5480157, 66.4038653}, {68.2236994, 73.2154296}}, +{{68.2236994, 73.2154296}, {70.5412458, 82.636132}, {31.358766, 46.7795742}}, +</div> + +<div id="cubic2x0x"> +{{27.9052884, 4.18132628}, {75.550717, 80.9000193}, {86.6244633, 97.3541595}, {31.358766, 46.7795742}}, +{{27.9052884, 4.18132628}, {64.5696024, 61.9317264}, {68.2236994, 73.2154296}}, +{{68.2236994, 73.2154296}, {71.8777964, 84.4991328}, {31.358766, 46.7795742}}, +</div> + +<div id="cubic2x1"> +{{55.6607299, 89.8878963}, {45.872586, 80.5522712}, {42.0218181, 60.6961261}, {19.7918636, 41.8513322}}, +{{55.6607299, 89.8878963}, {52.7119153, 87.0754092}, {42.3919757, 69.4355526}}, +{{42.3919757, 69.4355526}, {32.6126647, 52.7197915}, {19.7918636, 41.8513322}}, +</div> + +<div id="cubic2x1x"> +{{55.6607299, 89.8878963}, {45.872586, 80.5522712}, {42.0218181, 60.6961261}, {19.7918636, 41.8513322}}, +{{55.6607299, 89.8878963}, {49.0795145, 82.5258065}, {42.3919757, 69.4355526}}, +{{42.3919757, 69.4355526}, {35.7044369, 56.3452986}, {19.7918636, 41.8513322}}, +</div> + +<div id="cubic2x2"> +{{80.5982112, 14.1354079}, {73.8005055, 65.0951435}, {54.0762929, 60.254824}, {2.82780649, 26.9437232}}, +{{80.5982112, 14.1354079}, {75.7174786, 50.7243473}, {58.3820516, 52.1411292}}, +{{58.3820516, 52.1411292}, {43.4686812, 53.3599624}, {2.82780649, 26.9437232}}, +</div> + +<div id="cubic2x2x"> +{{80.5982112, 14.1354079}, {73.8005055, 65.0951435}, {54.0762929, 60.254824}, {2.82780649, 26.9437232}}, +{{80.5982112, 14.1354079}, {76.0811121, 51.5011698}, {58.3820516, 52.1411292}}, +{{58.3820516, 52.1411292}, {40.6829911, 52.7810886}, {2.82780649, 26.9437232}}, +</div> + +<div id="cubic2x3"> +{{1.6014867, 16.1869736}, {54.4660745, 11.3148647}, {68.9317074, 35.2054791}, {98.4868263, 68.0902175}}, +{{1.6014867, 16.1869736}, {36.7068582, 12.9515906}, {58.7852073, 27.9797778}}, +{{58.7852073, 27.9797778}, {68.1927213, 34.3832403}, {98.4868263, 68.0902175}}, +</div> + +<div id="cubic2x3x"> +{{1.6014867, 16.1869736}, {54.4660745, 11.3148647}, {68.9317074, 35.2054791}, {98.4868263, 68.0902175}}, +{{1.6014867, 16.1869736}, {39.5784138, 13.1506607}, {58.7852073, 27.9797778}}, +{{58.7852073, 27.9797778}, {77.9920009, 42.808895}, {98.4868263, 68.0902175}}, +</div> + +<div id="cubic2x4"> +{{23.0453529, 23.2462522}, {99.7603064, 71.4695575}, {88.8529841, 52.1034408}, {2.52897437, 4.4722111}}, +{{23.0453529, 23.2462522}, {83.1995453, 61.0594014}, {73.9267748, 49.8046823}}, +{{73.9267748, 49.8046823}, {64.9578598, 38.9187642}, {2.52897437, 4.4722111}}, +</div> + +<div id="cubic2x4x"> +{{23.0453529, 23.2462522}, {99.7603064, 71.4695575}, {88.8529841, 52.1034408}, {2.52897437, 4.4722111}}, +{{23.0453529, 23.2462522}, {80.2001434, 58.1848465}, {73.9267748, 49.8046823}}, +{{73.9267748, 49.8046823}, {67.6534063, 41.424518}, {2.52897437, 4.4722111}}, +</div> + +<div id="cubic2x5"> +{{64.4519328, 43.6345262}, {65.4821636, 58.7228333}, {54.6599207, 69.286817}, {3.532848, 76.5762786}}, +{{64.4519328, 43.6345262}, {65.2901892, 55.9112614}, {53.5513792, 63.0299695}}, +{{53.5513792, 63.0299695}, {39.721686, 71.4166414}, {3.532848, 76.5762786}}, +</div> + +<div id="cubic2x5x"> +{{64.4519328, 43.6345262}, {65.4821636, 58.7228333}, {54.6599207, 69.286817}, {3.532848, 76.5762786}}, +{{64.4519328, 43.6345262}, {66.113742, 54.9117003}, {53.5513792, 63.0299695}}, +{{53.5513792, 63.0299695}, {40.9890164, 71.1482387}, {3.532848, 76.5762786}}, +</div> + +<div id="cubic2x6"> +{{82.5366784, 93.9543251}, {90.3418213, 74.9907304}, {69.20575, 41.039441}, {49.884656, 11.4126389}}, +{{82.5366784, 93.9543251}, {87.7472455, 81.2945847}, {76.383006, 56.6821848}}, +{{76.383006, 56.6821848}, {69.0501277, 40.8008111}, {49.884656, 11.4126389}}, +</div> + +<div id="cubic2x6x"> +{{82.5366784, 93.9543251}, {90.3418213, 74.9907304}, {69.20575, 41.039441}, {49.884656, 11.4126389}}, +{{82.5366784, 93.9543251}, {87.4294046, 79.1281234}, {76.383006, 56.6821848}}, +{{76.383006, 56.6821848}, {65.3366074, 34.2362462}, {49.884656, 11.4126389}}, +</div> + +<div id="cubic2x7"> +{{81.6027334, 97.1400425}, {32.694003, 88.1076582}, {25.4108981, 80.9641684}, {64.7788314, 37.8185316}}, +{{81.6027334, 97.1400425}, {43.6639346, 90.1335672}, {40.0870335, 80.2717567}}, +{{40.0870335, 80.2717567}, {36.0922592, 69.2578356}, {64.7788314, 37.8185316}}, +</div> + +<div id="cubic2x7x"> +{{81.6027334, 97.1400425}, {32.694003, 88.1076582}, {25.4108981, 80.9641684}, {64.7788314, 37.8185316}}, +{{81.6027334, 97.1400425}, {44.7641414, 91.5498493}, {40.0870335, 80.2717567}}, +{{40.0870335, 80.2717567}, {35.4099255, 68.9936642}, {64.7788314, 37.8185316}}, +</div> + +<div id="cubic2x8"> +{{43.6332675, 44.3267048}, {98.9277035, 77.9134953}, {92.1152147, 80.4133992}, {7.99971512, 51.2120151}}, +{{43.6332675, 44.3267048}, {85.4039037, 69.6989069}, {78.0952172, 71.3149254}}, +{{78.0952172, 71.3149254}, {70.649222, 72.9613041}, {7.99971512, 51.2120151}}, +</div> + +<div id="cubic2x8x"> +{{43.6332675, 44.3267048}, {98.9277035, 77.9134953}, {92.1152147, 80.4133992}, {7.99971512, 51.2120151}}, +{{43.6332675, 44.3267048}, {85.5789722, 69.5359977}, {78.0952172, 71.3149254}}, +{{78.0952172, 71.3149254}, {70.6114621, 73.0938531}, {7.99971512, 51.2120151}}, +</div> + +<div id="cubic2x9"> +{{3.42763756, 8.30440876}, {72.1979502, 30.9497829}, {73.001545, 36.9676506}, {15.3033876, 4.03527813}}, +{{3.42763756, 8.30440876}, {62.7221525, 27.8294978}, {56.7911889, 27.0114984}}, +{{56.7911889, 27.0114984}, {55.1652933, 26.7872547}, {15.3033876, 4.03527813}}, +</div> + +<div id="cubic2x9x"> +{{3.42763756, 8.30440876}, {72.1979502, 30.9497829}, {73.001545, 36.9676506}, {15.3033876, 4.03527813}}, +{{3.42763756, 8.30440876}, {54.7095919, 25.9860248}, {56.7911889, 27.0114984}}, +{{56.7911889, 27.0114984}, {58.8727859, 28.036972}, {15.3033876, 4.03527813}}, +</div> + +<div id="cubic3x0"> +{{37.7493998, 54.1620116}, {0.928181503, 99.9465276}, {1.29019157, 84.2497321}, {85.2470221, 46.7010984}}, +{{37.7493998, 54.1620116}, {30.0262679, 63.7651662}, {19.9157535, 75.222785}}, +{{19.9157535, 75.222785}, {12.0739437, 84.1094218}, {23.0870945, 77.9306985}}, +{{23.0870945, 77.9306985}, {53.2236264, 61.0231583}, {85.2470221, 46.7010984}}, +</div> + +<div id="cubic3x0x"> +{{37.7493998, 54.1620116}, {0.928181503, 99.9465276}, {1.29019157, 84.2497321}, {85.2470221, 46.7010984}}, +{{37.7493998, 54.1620116}, {26.0576358, 68.4753229}, {19.9157535, 75.222785}}, +{{19.9157535, 75.222785}, {7.36020346, 87.8757618}, {23.0870945, 77.9306985}}, +{{23.0870945, 77.9306985}, {37.855802, 68.7339725}, {85.2470221, 46.7010984}}, +</div> + +<div id="cubic3x1"> +{{77.853445, 82.8493315}, {48.7140421, 36.904878}, {60.2845497, 2.42643608}, {81.1111786, 35.5792593}}, +{{77.853445, 82.8493315}, {64.326138, 61.5206609}, {61.1190571, 42.8070764}}, +{{61.1190571, 42.8070764}, {58.2548088, 26.0939491}, {64.5348786, 22.8899965}}, +{{64.5348786, 22.8899965}, {71.0512995, 19.5654629}, {81.1111786, 35.5792593}}, +</div> + +<div id="cubic3x1x"> +{{77.853445, 82.8493315}, {48.7140421, 36.904878}, {60.2845497, 2.42643608}, {81.1111786, 35.5792593}}, +{{77.853445, 82.8493315}, {63.5749823, 59.3570561}, {61.1190571, 42.8070764}}, +{{61.1190571, 42.8070764}, {58.6631319, 26.2570968}, {64.5348786, 22.8899965}}, +{{64.5348786, 22.8899965}, {70.4066254, 19.5228963}, {81.1111786, 35.5792593}}, +</div> + +<div id="cubic3x2"> +{{38.2012882, 49.0499648}, {82.7576585, 7.96646616}, {92.3967278, 11.8042378}, {93.8251679, 19.597347}}, +{{38.2012882, 49.0499648}, {58.8845939, 29.9787846}, {72.1076941, 21.4229661}}, +{{72.1076941, 21.4229661}, {83.1166319, 14.2997899}, {88.6707154, 14.6399404}}, +{{88.6707154, 14.6399404}, {92.9647013, 14.9029184}, {93.8251679, 19.597347}}, +</div> + +<div id="cubic3x2x"> +{{38.2012882, 49.0499648}, {82.7576585, 7.96646616}, {92.3967278, 11.8042378}, {93.8251679, 19.597347}}, +{{38.2012882, 49.0499648}, {60.2321893, 28.8875296}, {72.1076941, 21.4229661}}, +{{72.1076941, 21.4229661}, {83.983199, 13.9584026}, {88.6707154, 14.6399404}}, +{{88.6707154, 14.6399404}, {93.3582319, 15.3214782}, {93.8251679, 19.597347}}, +</div> + +<div id="cubic3x3"> +{{52.7120295, 31.0801866}, {64.6964272, 52.8517052}, {78.6098203, 95.2490945}, {51.5310243, 81.9254304}}, +{{52.7120295, 31.0801866}, {59.5211432, 43.4499986}, {63.7497522, 56.8993316}}, +{{63.7497522, 56.8993316}, {68.6258107, 72.4079153}, {66.5354307, 79.5030739}}, +{{66.5354307, 79.5030739}, {64.0124137, 88.0666872}, {51.5310243, 81.9254304}}, +</div> + +<div id="cubic3x3x"> +{{52.7120295, 31.0801866}, {64.6964272, 52.8517052}, {78.6098203, 95.2490945}, {51.5310243, 81.9254304}}, +{{52.7120295, 31.0801866}, {59.1016467, 42.6728619}, {63.7497522, 56.8993316}}, +{{63.7497522, 56.8993316}, {68.3978576, 71.1258013}, {66.5354307, 79.5030739}}, +{{66.5354307, 79.5030739}, {64.6730039, 87.8803465}, {51.5310243, 81.9254304}}, +</div> + +<div id="cubic3x4"> +{{20.7082833, 44.1170772}, {75.7169666, 75.0570675}, {84.1330966, 24.9551825}, {21.7528516, 0.176163297}}, +{{20.7082833, 44.1170772}, {46.6273271, 58.6954113}, {59.2896776, 51.9825439}}, +{{59.2896776, 51.9825439}, {71.1540672, 45.6927106}, {61.4307428, 29.4567029}}, +{{61.4307428, 29.4567029}, {50.807026, 11.71722}, {21.7528516, 0.176163297}}, +</div> + +<div id="cubic3x4x"> +{{20.7082833, 44.1170772}, {75.7169666, 75.0570675}, {84.1330966, 24.9551825}, {21.7528516, 0.176163297}}, +{{20.7082833, 44.1170772}, {48.4367344, 58.6022136}, {59.2896776, 51.9825439}}, +{{59.2896776, 51.9825439}, {70.1426209, 45.3628742}, {61.4307428, 29.4567029}}, +{{61.4307428, 29.4567029}, {52.7188646, 13.5505316}, {21.7528516, 0.176163297}}, +</div> + +<div id="cubic3x5"> +{{20.8291142, 74.9221559}, {16.6750469, 57.513008}, {21.1249099, 46.360262}, {76.9233116, 50.0985771}}, +{{20.8291142, 74.9221559}, {18.4755741, 65.0587801}, {21.1261573, 59.9182775}}, +{{21.1261573, 59.9182775}, {24.474036, 53.4254499}, {36.6579558, 51.0041468}}, +{{36.6579558, 51.0041468}, {50.2178533, 48.3093965}, {76.9233116, 50.0985771}}, +</div> + +<div id="cubic3x5x"> +{{20.8291142, 74.9221559}, {16.6750469, 57.513008}, {21.1249099, 46.360262}, {76.9233116, 50.0985771}}, +{{20.8291142, 74.9221559}, {18.3562971, 66.1376314}, {21.1261573, 59.9182775}}, +{{21.1261573, 59.9182775}, {23.8960175, 53.6989236}, {36.6579558, 51.0041468}}, +{{36.6579558, 51.0041468}, {49.4198942, 48.3093701}, {76.9233116, 50.0985771}}, +</div> + +<div id="cubic3x6"> +{{39.306348, 21.7912016}, {44.72463, 86.8568551}, {3.16400146, 77.3725818}, {0.981986477, 4.24671164}}, +{{39.306348, 21.7912016}, {41.8751537, 52.6388057}, {32.26342, 62.4108917}}, +{{32.26342, 62.4108917}, {23.2193358, 71.6058581}, {13.0917792, 55.754704}}, +{{13.0917792, 55.754704}, {2.00097021, 38.3959145}, {0.981986477, 4.24671164}}, +</div> + +<div id="cubic3x6x"> +{{39.306348, 21.7912016}, {44.72463, 86.8568551}, {3.16400146, 77.3725818}, {0.981986477, 4.24671164}}, +{{39.306348, 21.7912016}, {41.2158823, 54.2230253}, {32.26342, 62.4108917}}, +{{32.26342, 62.4108917}, {23.3109577, 70.5987581}, {13.0917792, 55.754704}}, +{{13.0917792, 55.754704}, {2.87260067, 40.9106498}, {0.981986477, 4.24671164}}, +</div> + +<div id="cubic3x7"> +{{85.4907277, 42.6604079}, {93.4752654, 38.7852218}, {63.2230996, 90.6357313}, {14.7351715, 54.0271501}}, +{{85.4907277, 42.6604079}, {92.9820656, 39.0245896}, {81.4704732, 52.0202764}}, +{{81.4704732, 52.0202764}, {71.0697229, 63.7619094}, {56.4037366, 66.489545}}, +{{56.4037366, 66.489545}, {36.2148038, 70.2443591}, {14.7351715, 54.0271501}}, +</div> + +<div id="cubic3x7x"> +{{85.4907277, 42.6604079}, {93.4752654, 38.7852218}, {63.2230996, 90.6357313}, {14.7351715, 54.0271501}}, +{{85.4907277, 42.6604079}, {89.2978026, 42.0578592}, {81.4704732, 52.0202764}}, +{{81.4704732, 52.0202764}, {73.6431437, 61.9826936}, {56.4037366, 66.489545}}, +{{56.4037366, 66.489545}, {39.1643295, 70.9963964}, {14.7351715, 54.0271501}}, +</div> + +<div id="cubic3x8"> +{{95.2957887, 36.3209844}, {46.7852652, 19.9519225}, {31.9607143, 63.7251956}, {29.3620354, 87.7284659}}, +{{95.2957887, 36.3209844}, {73.0036621, 28.7988805}, {57.2191042, 37.0396513}}, +{{57.2191042, 37.0396513}, {44.4309585, 43.7160611}, {36.8308235, 60.0949108}}, +{{36.8308235, 60.0949108}, {30.9912846, 72.6795466}, {29.3620354, 87.7284659}}, +</div> + +<div id="cubic3x8x"> +{{95.2957887, 36.3209844}, {46.7852652, 19.9519225}, {31.9607143, 63.7251956}, {29.3620354, 87.7284659}}, +{{95.2957887, 36.3209844}, {71.2392316, 28.8763825}, {57.2191042, 37.0396513}}, +{{57.2191042, 37.0396513}, {43.1989768, 45.20292}, {36.8308235, 60.0949108}}, +{{36.8308235, 60.0949108}, {30.4626702, 74.9869017}, {29.3620354, 87.7284659}}, +</div> + +<div id="cubic3x9"> +{{11.6274826, 23.1005334}, {50.665531, 35.5788199}, {73.2259434, 8.43082047}, {96.7997166, 12.8374226}}, +{{11.6274826, 23.1005334}, {26.8690196, 27.9724026}, {42.2684837, 25.6341105}}, +{{42.2684837, 25.6341105}, {51.3514943, 24.254924}, {67.0182186, 18.4582098}}, +{{67.0182186, 18.4582098}, {87.1065443, 11.0254957}, {96.7997166, 12.8374226}}, +</div> + +<div id="cubic3x9x"> +{{11.6274826, 23.1005334}, {50.665531, 35.5788199}, {73.2259434, 8.43082047}, {96.7997166, 12.8374226}}, +{{11.6274826, 23.1005334}, {28.7555518, 28.1569895}, {42.2684837, 25.6341105}}, +{{42.2684837, 25.6341105}, {55.7814156, 23.1112314}, {67.0182186, 18.4582098}}, +{{67.0182186, 18.4582098}, {82.5639521, 11.3566582}, {96.7997166, 12.8374226}}, +</div> + +<div id="cubic4x0"> +{{24.2578299, 1.34695745}, {38.313885, 41.465269}, {6.77689729, 99.312693}, {48.4308047, 76.5337766}}, +{{24.2578299, 1.34695745}, {27.9750096, 11.9564045}, {28.1705087, 26.7539994}}, +{{28.1705087, 26.7539994}, {28.2848367, 35.4076429}, {26.8433323, 51.6959666}}, +{{26.8433323, 51.6959666}, {24.9672902, 72.8943612}, {27.4957684, 77.9195086}}, +{{27.4957684, 77.9195086}, {31.4664535, 85.8109263}, {48.4308047, 76.5337766}}, +</div> + +<div id="cubic4x0x"> +{{24.2578299, 1.34695745}, {38.313885, 41.465269}, {6.77689729, 99.312693}, {48.4308047, 76.5337766}}, +{{24.2578299, 1.34695745}, {28.2364584, 13.5769276}, {28.1705087, 26.7539994}}, +{{28.1705087, 26.7539994}, {28.104559, 39.9310711}, {26.8433323, 51.6959666}}, +{{26.8433323, 51.6959666}, {24.5051265, 69.7176532}, {27.4957684, 77.9195086}}, +{{27.4957684, 77.9195086}, {30.4864104, 86.121364}, {48.4308047, 76.5337766}}, +</div> + +<div id="cubic4x1"> +{{3.18338154, 3.09354817}, {93.264044, 88.7879534}, {59.132973, 47.8778685}, {83.3354337, 18.6335197}}, +{{3.18338154, 3.09354817}, {35.8260971, 34.1468066}, {48.9325859, 44.6922254}}, +{{48.9325859, 44.6922254}, {62.4915199, 55.6016796}, {67.1257676, 54.3074276}}, +{{67.1257676, 54.3074276}, {70.2512267, 53.4345498}, {72.6465479, 43.2128608}}, +{{72.6465479, 43.2128608}, {76.4594277, 26.9419442}, {83.3354337, 18.6335197}}, +</div> + +<div id="cubic4x1x"> +{{3.18338154, 3.09354817}, {93.264044, 88.7879534}, {59.132973, 47.8778685}, {83.3354337, 18.6335197}}, +{{3.18338154, 3.09354817}, {34.807442, 33.2979688}, {48.9325859, 44.6922254}}, +{{48.9325859, 44.6922254}, {63.0577297, 56.086482}, {67.1257676, 54.3074276}}, +{{67.1257676, 54.3074276}, {71.1938054, 52.5283732}, {72.6465479, 43.2128608}}, +{{72.6465479, 43.2128608}, {74.0679283, 31.8888383}, {83.3354337, 18.6335197}}, +</div> + +<div id="cubic4x2"> +{{5.3607232, 97.6747591}, {19.6754743, 85.6972941}, {14.421376, 80.0662188}, {72.9397619, 98.5790647}}, +{{5.3607232, 97.6747591}, {7.15867444, 96.170374}, {9.99357731, 93.4972246}}, +{{9.99357731, 93.4972246}, {15.4658237, 88.3372129}, {19.1058065, 87.2914549}}, +{{19.1058065, 87.2914549}, {24.5745003, 85.7203128}, {35.9606711, 88.1040392}}, +{{35.9606711, 88.1040392}, {47.3960315, 90.4980635}, {72.9397619, 98.5790647}}, +</div> + +<div id="cubic4x2x"> +{{5.3607232, 97.6747591}, {19.6754743, 85.6972941}, {14.421376, 80.0662188}, {72.9397619, 98.5790647}}, +{{5.3607232, 97.6747591}, {8.01636596, 95.4093652}, {9.99357731, 93.4972246}}, +{{9.99357731, 93.4972246}, {14.161732, 88.9702622}, {19.1058065, 87.2914549}}, +{{19.1058065, 87.2914549}, {24.0498811, 85.6126476}, {35.9606711, 88.1040392}}, +{{35.9606711, 88.1040392}, {47.871461, 90.5954307}, {72.9397619, 98.5790647}}, +</div> + +<div id="cubic4x3"> +{{18.340571, 49.9760211}, {46.9862021, 97.0991299}, {45.0770262, 9.57918773}, {97.4081647, 39.0235061}}, +{{18.340571, 49.9760211}, {27.6759966, 65.333137}, {34.9254897, 64.1054159}}, +{{34.9254897, 64.1054159}, {39.46946, 63.3358824}, {47.9840785, 52.4199142}}, +{{47.9840785, 52.4199142}, {58.4594697, 38.9901831}, {66.2068641, 35.3036404}}, +{{66.2068641, 35.3036404}, {79.5296469, 28.9640886}, {97.4081647, 39.0235061}}, +</div> + +<div id="cubic4x3x"> +{{18.340571, 49.9760211}, {46.9862021, 97.0991299}, {45.0770262, 9.57918773}, {97.4081647, 39.0235061}}, +{{18.340571, 49.9760211}, {28.406995, 66.1423531}, {34.9254897, 64.1054159}}, +{{34.9254897, 64.1054159}, {41.4439844, 62.0684788}, {47.9840785, 52.4199142}}, +{{47.9840785, 52.4199142}, {54.9532374, 41.9238105}, {66.2068641, 35.3036404}}, +{{66.2068641, 35.3036404}, {77.4604907, 28.6834703}, {97.4081647, 39.0235061}}, +</div> + +<div id="cubic4x4"> +{{68.0670356, 2.66693188}, {23.1241074, 46.8739094}, {9.79601006, 41.5410025}, {79.6294187, 31.6402602}}, +{{68.0670356, 2.66693188}, {56.7853646, 13.7638629}, {41.0137122, 27.3042275}}, +{{41.0137122, 27.3042275}, {29.788878, 36.941033}, {31.0433353, 38.0354879}}, +{{31.0433353, 38.0354879}, {32.2977925, 39.1299429}, {51.0493703, 36.059867}}, +{{51.0493703, 36.059867}, {67.7999464, 33.3174024}, {79.6294187, 31.6402602}}, +</div> + +<div id="cubic4x4x"> +{{68.0670356, 2.66693188}, {23.1241074, 46.8739094}, {9.79601006, 41.5410025}, {79.6294187, 31.6402602}}, +{{68.0670356, 2.66693188}, {50.940695, 19.1344928}, {41.0137122, 27.3042275}}, +{{41.0137122, 27.3042275}, {29.4752637, 36.6674193}, {31.0433353, 38.0354879}}, +{{31.0433353, 38.0354879}, {32.6114068, 39.4035566}, {51.0493703, 36.059867}}, +{{51.0493703, 36.059867}, {61.9478496, 34.2106234}, {79.6294187, 31.6402602}}, +</div> + +<div id="cubic4x5"> +{{80.6109054, 27.4877124}, {85.9817399, 95.1019056}, {77.7276185, 68.083746}, {83.5185407, 96.1129614}}, +{{80.6109054, 27.4877124}, {82.5499811, 51.8990092}, {82.5259477, 65.0368853}}, +{{82.5259477, 65.0368853}, {82.5124299, 72.4264589}, {81.7002161, 78.1564815}}, +{{81.7002161, 78.1564815}, {81.2315331, 81.462956}, {81.4316783, 83.8990214}}, +{{81.4316783, 83.8990214}, {81.7199102, 87.4072321}, {83.5185407, 96.1129614}}, +</div> + +<div id="cubic4x5x"> +{{80.6109054, 27.4877124}, {85.9817399, 95.1019056}, {77.7276185, 68.083746}, {83.5185407, 96.1129614}}, +{{80.6109054, 27.4877124}, {82.6925268, 54.7439407}, {82.5259477, 65.0368853}}, +{{82.5259477, 65.0368853}, {82.3593687, 75.3298298}, {81.7002161, 78.1564815}}, +{{81.7002161, 78.1564815}, {81.2086421, 80.6624342}, {81.4316783, 83.8990214}}, +{{81.4316783, 83.8990214}, {81.6547145, 87.1356086}, {83.5185407, 96.1129614}}, +</div> + +<div id="cubic4x6"> +{{70.5424749, 7.37512261}, {53.6857094, 95.7185581}, {41.8065019, 41.8776796}, {38.1617001, 83.6927474}}, +{{70.5424749, 7.37512261}, {64.0240124, 41.5372735}, {57.0495799, 54.4661558}}, +{{57.0495799, 54.4661558}, {53.0372544, 61.9040203}, {46.633996, 64.0865108}}, +{{46.633996, 64.0865108}, {42.8562175, 65.3741311}, {41.4346736, 67.9484678}}, +{{41.4346736, 67.9484678}, {39.1777978, 72.0355437}, {38.1617001, 83.6927474}}, +</div> + +<div id="cubic4x6x"> +{{70.5424749, 7.37512261}, {53.6857094, 95.7185581}, {41.8065019, 41.8776796}, {38.1617001, 83.6927474}}, +{{70.5424749, 7.37512261}, {63.0887524, 44.8198844}, {57.0495799, 54.4661558}}, +{{57.0495799, 54.4661558}, {51.0104074, 64.1124273}, {46.633996, 64.0865108}}, +{{46.633996, 64.0865108}, {43.5741104, 64.6069899}, {41.4346736, 67.9484678}}, +{{41.4346736, 67.9484678}, {39.2952367, 71.2899457}, {38.1617001, 83.6927474}}, +</div> + +<div id="cubic4x7"> +{{24.0062249, 72.6211198}, {43.1612821, 11.6690897}, {22.3913226, 30.9587957}, {24.4801394, 37.7033828}}, +{{24.0062249, 72.6211198}, {30.5430063, 51.8208637}, {31.8675739, 40.5026282}}, +{{31.8675739, 40.5026282}, {32.9179067, 31.5276894}, {30.6430223, 29.7760199}}, +{{30.6430223, 29.7760199}, {28.7741669, 28.3369942}, {26.2185506, 31.7425273}}, +{{26.2185506, 31.7425273}, {23.6812077, 35.1237098}, {24.4801394, 37.7033828}}, +</div> + +<div id="cubic4x7x"> +{{24.0062249, 72.6211198}, {43.1612821, 11.6690897}, {22.3913226, 30.9587957}, {24.4801394, 37.7033828}}, +{{24.0062249, 72.6211198}, {30.9441221, 50.1265572}, {31.8675739, 40.5026282}}, +{{31.8675739, 40.5026282}, {32.7910257, 30.8786991}, {30.6430223, 29.7760199}}, +{{30.6430223, 29.7760199}, {28.4950189, 28.6733406}, {26.2185506, 31.7425273}}, +{{26.2185506, 31.7425273}, {23.9420823, 34.811714}, {24.4801394, 37.7033828}}, +</div> + +<div id="cubic4x8"> +{{83.4128604, 19.944285}, {3.59808416, 73.0005231}, {19.791118, 29.3197498}, {77.0346567, 21.4750355}}, +{{83.4128604, 19.944285}, {56.4409479, 37.8736494}, {40.6945347, 43.6697281}}, +{{40.6945347, 43.6697281}, {27.6832174, 48.4590486}, {28.8268904, 43.5475174}}, +{{28.8268904, 43.5475174}, {29.9619906, 38.6728026}, {42.6576802, 32.0063781}}, +{{42.6576802, 32.0063781}, {57.6563877, 24.1306537}, {77.0346567, 21.4750355}}, +</div> + +<div id="cubic4x8x"> +{{83.4128604, 19.944285}, {3.59808416, 73.0005231}, {19.791118, 29.3197498}, {77.0346567, 21.4750355}}, +{{83.4128604, 19.944285}, {53.6969963, 39.3225107}, {40.6945347, 43.6697281}}, +{{40.6945347, 43.6697281}, {27.6920731, 48.0169456}, {28.8268904, 43.5475174}}, +{{28.8268904, 43.5475174}, {29.9617077, 39.0780892}, {42.6576802, 32.0063781}}, +{{42.6576802, 32.0063781}, {55.3536527, 24.9346669}, {77.0346567, 21.4750355}}, +</div> + +<div id="cubic4x9"> +{{13.6133623, 99.7800201}, {2.79733483, 14.8064674}, {52.2975031, 64.1339272}, {98.9146078, 57.8132952}}, +{{13.6133623, 99.7800201}, {10.1036384, 72.2067072}, {14.9007617, 60.2808941}}, +{{14.9007617, 60.2808941}, {19.0431228, 49.9828423}, {30.5807774, 49.2954321}}, +{{30.5807774, 49.2954321}, {37.7022355, 48.8711377}, {56.117561, 53.190874}}, +{{56.117561, 53.190874}, {84.2814202, 59.7973522}, {98.9146078, 57.8132952}}, +</div> + +<div id="cubic4x9x"> +{{13.6133623, 99.7800201}, {2.79733483, 14.8064674}, {52.2975031, 64.1339272}, {98.9146078, 57.8132952}}, +{{13.6133623, 99.7800201}, {10.0919269, 71.197946}, {14.9007617, 60.2808941}}, +{{14.9007617, 60.2808941}, {19.7095965, 49.3638421}, {30.5807774, 49.2954321}}, +{{30.5807774, 49.2954321}, {41.4519583, 49.2270222}, {56.117561, 53.190874}}, +{{56.117561, 53.190874}, {76.476137, 59.3205959}, {98.9146078, 57.8132952}}, +</div> + +<div id="cubic5x0"> +{{73.5652707, 11.5053172}, {69.8658631, 35.5604111}, {63.8300007, 90.8210508}, {29.4000415, 26.4971589}}, +{{73.5652707, 11.5053172}, {73.3885843, 12.654206}, {73.0163837, 15.1491032}}, +{{73.0163837, 15.1491032}, {70.9175181, 29.2180034}, {69.2121151, 36.2586021}}, +{{69.2121151, 36.2586021}, {66.2435432, 48.5140774}, {62.0808557, 53.3239452}}, +{{62.0808557, 53.3239452}, {56.8541433, 59.3632637}, {49.5132747, 54.1388813}}, +{{49.5132747, 54.1388813}, {40.9233022, 48.0255311}, {29.4000415, 26.4971589}}, +</div> + +<div id="cubic5x0x"> +{{73.5652707, 11.5053172}, {69.8658631, 35.5604111}, {63.8300007, 90.8210508}, {29.4000415, 26.4971589}}, +{{73.5652707, 11.5053172}, {73.3009509, 13.2327574}, {73.0163837, 15.1491032}}, +{{73.0163837, 15.1491032}, {71.6823308, 25.1891102}, {69.2121151, 36.2586021}}, +{{69.2121151, 36.2586021}, {66.7418995, 47.328094}, {62.0808557, 53.3239452}}, +{{62.0808557, 53.3239452}, {57.4198119, 59.3197964}, {49.5132747, 54.1388813}}, +{{49.5132747, 54.1388813}, {41.6067374, 48.9579661}, {29.4000415, 26.4971589}}, +</div> + +<div id="cubic5x1"> +{{80.7539402, 31.4736433}, {77.5229567, 28.3334108}, {99.6348716, 63.2867312}, {60.0910899, 50.9480224}}, +{{80.7539402, 31.4736433}, {80.1293736, 30.8666193}, {81.0927918, 33.3061348}}, +{{81.0927918, 33.3061348}, {82.7770389, 37.5708941}, {83.4256875, 40.319949}}, +{{83.4256875, 40.319949}, {84.5951485, 45.2762733}, {83.5574674, 48.3997103}}, +{{83.5574674, 48.3997103}, {82.2131806, 52.4460356}, {77.2064841, 53.3431558}}, +{{77.2064841, 53.3431558}, {71.2104332, 54.4175525}, {60.0910899, 50.9480224}}, +</div> + +<div id="cubic5x1x"> +{{80.7539402, 31.4736433}, {77.5229567, 28.3334108}, {99.6348716, 63.2867312}, {60.0910899, 50.9480224}}, +{{80.7539402, 31.4736433}, {79.9741932, 30.7172975}, {81.0927918, 33.3061348}}, +{{81.0927918, 33.3061348}, {82.2743126, 36.0212723}, {83.4256875, 40.319949}}, +{{83.4256875, 40.319949}, {84.5770623, 44.6186258}, {83.5574674, 48.3997103}}, +{{83.5574674, 48.3997103}, {82.5378725, 52.1807949}, {77.2064841, 53.3431558}}, +{{77.2064841, 53.3431558}, {71.8750956, 54.5055166}, {60.0910899, 50.9480224}}, +</div> + +<div id="cubic5x2"> +{{30.9220007, 6.06626757}, {55.7590106, 41.691652}, {11.5944877, 68.5545306}, {95.99508, 89.3088364}}, +{{30.9220007, 6.06626757}, {36.6680413, 14.3081978}, {38.6632502, 23.8943374}}, +{{38.6632502, 23.8943374}, {39.8467707, 29.5806556}, {40.109652, 40.2122054}}, +{{40.109652, 40.2122054}, {40.4211241, 52.8088852}, {42.588681, 58.5795625}}, +{{42.588681, 58.5795625}, {46.141784, 68.0389732}, {57.1660752, 74.8906876}}, +{{57.1660752, 74.8906876}, {70.1317224, 82.9489754}, {95.99508, 89.3088364}}, +</div> + +<div id="cubic5x2x"> +{{30.9220007, 6.06626757}, {55.7590106, 41.691652}, {11.5944877, 68.5545306}, {95.99508, 89.3088364}}, +{{30.9220007, 6.06626757}, {37.1487855, 15.3683637}, {38.6632502, 23.8943374}}, +{{38.6632502, 23.8943374}, {40.1777149, 32.4203112}, {40.109652, 40.2122054}}, +{{40.109652, 40.2122054}, {39.8437309, 49.9303489}, {42.588681, 58.5795625}}, +{{42.588681, 58.5795625}, {45.3336311, 67.2287761}, {57.1660752, 74.8906876}}, +{{57.1660752, 74.8906876}, {68.9985192, 82.5525991}, {95.99508, 89.3088364}}, +</div> + +<div id="cubic5x3"> +{{74.7743754, 32.9274563}, {11.7577089, 11.8127863}, {37.4985242, 37.696964}, {72.8744837, 1.44809908}}, +{{74.7743754, 32.9274563}, {60.7273344, 28.2207866}, {49.5992486, 25.6169692}}, +{{49.5992486, 25.6169692}, {43.5981152, 24.2127874}, {37.944249, 23.3667683}}, +{{37.944249, 23.3667683}, {35.9715145, 23.0715771}, {37.4878767, 22.7373028}}, +{{37.4878767, 22.7373028}, {44.1459136, 21.2695724}, {50.3950023, 18.2059418}}, +{{50.3950023, 18.2059418}, {62.1391178, 12.4483612}, {72.8744837, 1.44809908}}, +</div> + +<div id="cubic5x3x"> +{{74.7743754, 32.9274563}, {11.7577089, 11.8127863}, {37.4985242, 37.696964}, {72.8744837, 1.44809908}}, +{{74.7743754, 32.9274563}, {58.4980331, 27.5812922}, {49.5992486, 25.6169692}}, +{{49.5992486, 25.6169692}, {40.7004642, 23.6526461}, {37.944249, 23.3667683}}, +{{37.944249, 23.3667683}, {35.0992403, 23.0813479}, {37.4878767, 22.7373028}}, +{{37.4878767, 22.7373028}, {40.7578786, 22.4379602}, {50.3950023, 18.2059418}}, +{{50.3950023, 18.2059418}, {60.0321261, 13.9739234}, {72.8744837, 1.44809908}}, +</div> + +<div id="cubic5x4"> +{{72.6117562, 85.7863012}, {10.3637705, 83.8910282}, {56.5110395, 81.0400843}, {40.6969416, 93.4977145}}, +{{72.6117562, 85.7863012}, {59.583082, 85.3896153}, {50.1257271, 84.8566602}}, +{{50.1257271, 84.8566602}, {45.0042708, 84.5680481}, {40.4221343, 84.1941021}}, +{{40.4221343, 84.1941021}, {38.6138335, 84.0465275}, {39.3498335, 84.2964765}}, +{{39.3498335, 84.2964765}, {42.6031074, 85.4013033}, {43.6650027, 86.8548971}}, +{{43.6650027, 86.8548971}, {45.661047, 89.587217}, {40.6969416, 93.4977145}}, +</div> + +<div id="cubic5x4x"> +{{72.6117562, 85.7863012}, {10.3637705, 83.8910282}, {56.5110395, 81.0400843}, {40.6969416, 93.4977145}}, +{{72.6117562, 85.7863012}, {57.6253009, 85.3070124}, {50.1257271, 84.8566602}}, +{{50.1257271, 84.8566602}, {42.6261532, 84.4063079}, {40.4221343, 84.1941021}}, +{{40.4221343, 84.1941021}, {37.9777583, 83.9471466}, {39.3498335, 84.2964765}}, +{{39.3498335, 84.2964765}, {41.4441267, 84.7344658}, {43.6650027, 86.8548971}}, +{{43.6650027, 86.8548971}, {45.8858786, 88.9753284}, {40.6969416, 93.4977145}}, +</div> + +<div id="cubic5x5"> +{{49.5466436, 30.4382438}, {75.5627334, 82.8610433}, {45.5550553, 43.8144668}, {89.743077, 11.8944428}}, +{{49.5466436, 30.4382438}, {54.1919031, 39.7985093}, {58.8653675, 50.331813}}, +{{58.8653675, 50.331813}, {61.2282341, 55.6573679}, {61.7133948, 56.0247083}}, +{{61.7133948, 56.0247083}, {62.1985554, 56.3920486}, {62.7466525, 53.2705356}}, +{{62.7466525, 53.2705356}, {64.4490529, 43.5750541}, {68.2227928, 36.1296005}}, +{{68.2227928, 36.1296005}, {75.1711506, 22.4207397}, {89.743077, 11.8944428}}, +</div> + +<div id="cubic5x5x"> +{{49.5466436, 30.4382438}, {75.5627334, 82.8610433}, {45.5550553, 43.8144668}, {89.743077, 11.8944428}}, +{{49.5466436, 30.4382438}, {56.3292139, 44.3383274}, {58.8653675, 50.331813}}, +{{58.8653675, 50.331813}, {61.106944, 55.5655329}, {61.7133948, 56.0247083}}, +{{61.7133948, 56.0247083}, {62.3198455, 56.4838837}, {62.7466525, 53.2705356}}, +{{62.7466525, 53.2705356}, {63.1064311, 47.7098594}, {68.2227928, 36.1296005}}, +{{68.2227928, 36.1296005}, {73.3391545, 24.5493417}, {89.743077, 11.8944428}}, +</div> + +<div id="cubic5x6"> +{{24.3042985, 82.344259}, {59.9615856, 74.3697725}, {32.7666043, 8.31767205}, {95.114078, 82.3081283}}, +{{24.3042985, 82.344259}, {33.0316107, 80.3924607}, {38.6135161, 73.199581}}, +{{38.6135161, 73.199581}, {41.8734961, 68.9987494}, {45.7986582, 59.6541823}}, +{{45.7986582, 59.6541823}, {49.7161349, 50.3279117}, {52.6598645, 48.50717}}, +{{52.6598645, 48.50717}, {57.3512738, 45.6054619}, {66.2796867, 52.394109}}, +{{66.2796867, 52.394109}, {76.3758191, 60.0706222}, {95.114078, 82.3081283}}, +</div> + +<div id="cubic5x6x"> +{{24.3042985, 82.344259}, {59.9615856, 74.3697725}, {32.7666043, 8.31767205}, {95.114078, 82.3081283}}, +{{24.3042985, 82.344259}, {33.965356, 79.8151924}, {38.6135161, 73.199581}}, +{{38.6135161, 73.199581}, {43.2616761, 66.5839696}, {45.7986582, 59.6541823}}, +{{45.7986582, 59.6541823}, {48.5966015, 51.6963295}, {52.6598645, 48.50717}}, +{{52.6598645, 48.50717}, {56.7231274, 45.3180106}, {66.2796867, 52.394109}}, +{{66.2796867, 52.394109}, {75.8362459, 59.4702074}, {95.114078, 82.3081283}}, +</div> + +<div id="cubic5x7"> +{{14.6365061, 95.7588134}, {18.3773411, 67.9719648}, {4.8126874, 86.837213}, {73.0391371, 68.7771361}}, +{{14.6365061, 95.7588134}, {15.2275148, 91.3688129}, {15.5044612, 85.7525859}}, +{{15.5044612, 85.7525859}, {15.7576453, 80.618239}, {16.904617, 79.6508905}}, +{{16.904617, 79.6508905}, {18.0515887, 78.683542}, {24.680235, 78.0137979}}, +{{24.680235, 78.0137979}, {33.9302732, 77.0791942}, {41.7459023, 75.745697}}, +{{41.7459023, 75.745697}, {55.7221394, 73.3610813}, {73.0391371, 68.7771361}}, +</div> + +<div id="cubic5x7x"> +{{14.6365061, 95.7588134}, {18.3773411, 67.9719648}, {4.8126874, 86.837213}, {73.0391371, 68.7771361}}, +{{14.6365061, 95.7588134}, {15.4253236, 89.2562084}, {15.5044612, 85.7525859}}, +{{15.5044612, 85.7525859}, {15.4709024, 80.8600761}, {16.904617, 79.6508905}}, +{{16.904617, 79.6508905}, {18.3383317, 78.4417048}, {24.680235, 78.0137979}}, +{{24.680235, 78.0137979}, {30.2055996, 77.5914828}, {41.7459023, 75.745697}}, +{{41.7459023, 75.745697}, {53.2862049, 73.8999113}, {73.0391371, 68.7771361}}, +</div> + +<div id="cubic5x8"> +{{11.3940197, 99.2884769}, {41.4314282, 38.0142946}, {6.25007991, 45.0930539}, {78.9565565, 22.8458219}}, +{{11.3940197, 99.2884769}, {17.9356966, 85.9439202}, {21.7417223, 74.0130457}}, +{{21.7417223, 74.0130457}, {23.9251358, 67.1686272}, {26.0700343, 57.3329391}}, +{{26.0700343, 57.3329391}, {28.2750992, 47.2213507}, {30.7090957, 43.764797}}, +{{30.7090957, 43.764797}, {34.2237869, 38.7735329}, {44.5059747, 34.4313542}}, +{{44.5059747, 34.4313542}, {53.4825656, 30.6405304}, {78.9565565, 22.8458219}}, +</div> + +<div id="cubic5x8x"> +{{11.3940197, 99.2884769}, {41.4314282, 38.0142946}, {6.25007991, 45.0930539}, {78.9565565, 22.8458219}}, +{{11.3940197, 99.2884769}, {18.6635437, 84.168545}, {21.7417223, 74.0130457}}, +{{21.7417223, 74.0130457}, {24.8199009, 63.8575464}, {26.0700343, 57.3329391}}, +{{26.0700343, 57.3329391}, {27.5370962, 48.6793447}, {30.7090957, 43.764797}}, +{{30.7090957, 43.764797}, {33.8810951, 38.8502494}, {44.5059747, 34.4313542}}, +{{44.5059747, 34.4313542}, {55.1308542, 30.012459}, {78.9565565, 22.8458219}}, +</div> + +<div id="cubic5x9"> +{{69.7292014, 38.6877352}, {24.7648688, 23.1501713}, {84.9283191, 90.2588441}, {80.392774, 61.3533852}}, +{{69.7292014, 38.6877352}, {57.2585085, 34.3784487}, {54.0073216, 37.8534623}}, +{{54.0073216, 37.8534623}, {51.2791269, 40.7694784}, {55.3644243, 48.2785885}}, +{{55.3644243, 48.2785885}, {59.0228346, 55.0030454}, {65.6488241, 61.3874162}}, +{{65.6488241, 61.3874162}, {72.4185069, 67.9102405}, {76.7088359, 68.6042477}}, +{{76.7088359, 68.6042477}, {81.6560742, 69.4045171}, {80.392774, 61.3533852}}, +</div> + +<div id="cubic5x9x"> +{{69.7292014, 38.6877352}, {24.7648688, 23.1501713}, {84.9283191, 90.2588441}, {80.392774, 61.3533852}}, +{{69.7292014, 38.6877352}, {56.5795552, 34.3837867}, {54.0073216, 37.8534623}}, +{{54.0073216, 37.8534623}, {51.4350879, 41.3231378}, {55.3644243, 48.2785885}}, +{{55.3644243, 48.2785885}, {59.2937606, 55.2340392}, {65.6488241, 61.3874162}}, +{{65.6488241, 61.3874162}, {72.0038877, 67.5407932}, {76.7088359, 68.6042477}}, +{{76.7088359, 68.6042477}, {81.413784, 69.6677022}, {80.392774, 61.3533852}}, +</div> + +<div id="cubic6x0"> +{{60.7765365, 71.2493073}, {87.1078942, 22.3776699}, {1.49747543, 68.0695699}, {45.2619466, 17.5360766}}, +{{60.7765365, 71.2493073}, {66.8034381, 60.063232}, {65.7606554, 53.9755229}}, +{{65.7606554, 53.9755229}, {64.9026034, 48.9662616}, {59.0403561, 46.9365029}}, +{{59.0403561, 46.9365029}, {55.5624487, 45.7323037}, {47.0319968, 45.0593685}}, +{{47.0319968, 45.0593685}, {38.6438055, 44.3976557}, {35.915024, 43.1681828}}, +{{35.915024, 43.1681828}, {31.4270492, 41.1460923}, {32.9921574, 35.8381417}}, +{{32.9921574, 35.8381417}, {34.8405988, 29.5692874}, {45.2619466, 17.5360766}}, +</div> + +<div id="cubic6x0x"> +{{60.7765365, 71.2493073}, {87.1078942, 22.3776699}, {1.49747543, 68.0695699}, {45.2619466, 17.5360766}}, +{{60.7765365, 71.2493073}, {66.9967453, 59.4196142}, {65.7606554, 53.9755229}}, +{{65.7606554, 53.9755229}, {64.5245656, 48.5314316}, {59.0403561, 46.9365029}}, +{{59.0403561, 46.9365029}, {53.5561467, 45.3415741}, {47.0319968, 45.0593685}}, +{{47.0319968, 45.0593685}, {40.2998025, 44.7818435}, {35.915024, 43.1681828}}, +{{35.915024, 43.1681828}, {31.5302455, 41.5545222}, {32.9921574, 35.8381417}}, +{{32.9921574, 35.8381417}, {34.4540694, 30.1217612}, {45.2619466, 17.5360766}}, +</div> + +<div id="cubic6x1"> +{{7.56463181, 38.7667716}, {53.1298274, 53.009038}, {22.9012888, 1.96013199}, {43.9383991, 72.6733402}}, +{{7.56463181, 38.7667716}, {18.0499753, 42.0441646}, {24.9041761, 41.2832621}}, +{{24.9041761, 41.2832621}, {30.0084481, 40.7166236}, {32.7855974, 37.9676099}}, +{{32.7855974, 37.9676099}, {34.25762, 36.5105005}, {35.0000192, 34.4010014}}, +{{35.0000192, 34.4010014}, {35.1477005, 33.9813707}, {35.2051475, 34.7029855}}, +{{35.2051475, 34.7029855}, {35.5299907, 38.7834725}, {36.7160087, 44.7150792}}, +{{36.7160087, 44.7150792}, {38.9607709, 55.9417619}, {43.9383991, 72.6733402}}, +</div> + +<div id="cubic6x1x"> +{{7.56463181, 38.7667716}, {53.1298274, 53.009038}, {22.9012888, 1.96013199}, {43.9383991, 72.6733402}}, +{{7.56463181, 38.7667716}, {19.0728251, 42.1807008}, {24.9041761, 41.2832621}}, +{{24.9041761, 41.2832621}, {30.7355271, 40.3858233}, {32.7855974, 37.9676099}}, +{{32.7855974, 37.9676099}, {34.8356678, 35.5493964}, {35.0000192, 34.4010014}}, +{{35.0000192, 34.4010014}, {35.1702591, 33.6960593}, {35.2051475, 34.7029855}}, +{{35.2051475, 34.7029855}, {35.1391248, 36.1152585}, {36.7160087, 44.7150792}}, +{{36.7160087, 44.7150792}, {38.2928925, 53.3148999}, {43.9383991, 72.6733402}}, +</div> + +<div id="cubic6x2"> +{{53.4808373, 52.4330519}, {42.3039286, 2.12741392}, {55.4457253, 76.3045082}, {49.8689114, 46.7937026}}, +{{53.4808373, 52.4330519}, {50.9719376, 41.1408598}, {49.8115514, 36.9274013}}, +{{49.8115514, 36.9274013}, {48.82027, 33.3279765}, {48.8115145, 34.8928161}}, +{{48.8115145, 34.8928161}, {48.8045445, 36.1385203}, {49.4292469, 40.7546742}}, +{{49.4292469, 40.7546742}, {49.7879548, 43.4052983}, {50.613269, 48.9383534}}, +{{50.613269, 48.9383534}, {51.3518777, 53.8901197}, {51.31236, 53.9808933}}, +{{51.31236, 53.9808933}, {51.2529165, 54.1174374}, {49.8689114, 46.7937026}}, +</div> + +<div id="cubic6x2x"> +{{53.4808373, 52.4330519}, {42.3039286, 2.12741392}, {55.4457253, 76.3045082}, {49.8689114, 46.7937026}}, +{{53.4808373, 52.4330519}, {50.8474472, 40.6156325}, {49.8115514, 36.9274013}}, +{{49.8115514, 36.9274013}, {48.7756556, 33.2391701}, {48.8115145, 34.8928161}}, +{{48.8115145, 34.8928161}, {48.8473733, 36.5464621}, {49.4292469, 40.7546742}}, +{{49.4292469, 40.7546742}, {50.0111204, 44.9628863}, {50.613269, 48.9383534}}, +{{50.613269, 48.9383534}, {51.3082301, 53.5085713}, {51.31236, 53.9808933}}, +{{51.31236, 53.9808933}, {51.31649, 54.4532153}, {49.8689114, 46.7937026}}, +</div> + +<div id="cubic6x3"> +{{30.270176, 50.8484091}, {9.21238377, 32.534054}, {99.8452993, 99.9447358}, {71.1751053, 39.994736}}, +{{30.270176, 50.8484091}, {26.1998702, 47.3083881}, {27.3542845, 47.6109361}}, +{{27.3542845, 47.6109361}, {28.1421178, 47.8174109}, {33.7377536, 50.9254737}}, +{{33.7377536, 50.9254737}, {43.6710144, 56.4428448}, {49.5826034, 59.2306974}}, +{{49.5826034, 59.2306974}, {60.0794163, 64.1809007}, {66.5061178, 65.1608314}}, +{{66.5061178, 65.1608314}, {74.7232814, 66.4137682}, {76.404788, 61.2406021}}, +{{76.404788, 61.2406021}, {78.4000331, 55.1022173}, {71.1751053, 39.994736}}, +</div> + +<div id="cubic6x3x"> +{{30.270176, 50.8484091}, {9.21238377, 32.534054}, {99.8452993, 99.9447358}, {71.1751053, 39.994736}}, +{{30.270176, 50.8484091}, {26.0151068, 47.1560011}, {27.3542845, 47.6109361}}, +{{27.3542845, 47.6109361}, {28.6934622, 48.0658712}, {33.7377536, 50.9254737}}, +{{33.7377536, 50.9254737}, {40.3775737, 54.7374488}, {49.5826034, 59.2306974}}, +{{49.5826034, 59.2306974}, {58.787633, 63.723946}, {66.5061178, 65.1608314}}, +{{66.5061178, 65.1608314}, {74.2246025, 66.5977168}, {76.404788, 61.2406021}}, +{{76.404788, 61.2406021}, {78.5849735, 55.8834875}, {71.1751053, 39.994736}}, +</div> + +<div id="cubic6x4"> +{{52.3256249, 36.7777584}, {23.7859194, 69.9470399}, {99.9000587, 20.2858463}, {44.2180221, 72.2977287}}, +{{52.3256249, 36.7777584}, {46.323817, 43.7531512}, {45.7451821, 46.7544892}}, +{{45.7451821, 46.7544892}, {45.2655359, 49.2423797}, {48.551811, 49.2476269}}, +{{48.551811, 49.2476269}, {50.5144448, 49.2507606}, {55.9087216, 48.0313516}}, +{{55.9087216, 48.0313516}, {62.3329105, 46.5791247}, {63.9943433, 47.0044226}}, +{{63.9943433, 47.0044226}, {66.7468982, 47.7090289}, {62.987381, 52.8381772}}, +{{62.987381, 52.8381772}, {58.5075376, 58.9500739}, {44.2180221, 72.2977287}}, +</div> + +<div id="cubic6x4x"> +{{52.3256249, 36.7777584}, {23.7859194, 69.9470399}, {99.9000587, 20.2858463}, {44.2180221, 72.2977287}}, +{{52.3256249, 36.7777584}, {46.0840368, 44.1087946}, {45.7451821, 46.7544892}}, +{{45.7451821, 46.7544892}, {45.4063273, 49.4001838}, {48.551811, 49.2476269}}, +{{48.551811, 49.2476269}, {51.6972946, 49.09507}, {55.9087216, 48.0313516}}, +{{55.9087216, 48.0313516}, {61.1409519, 46.6483554}, {63.9943433, 47.0044226}}, +{{63.9943433, 47.0044226}, {66.8477347, 47.3604898}, {62.987381, 52.8381772}}, +{{62.987381, 52.8381772}, {59.1270273, 58.3158645}, {44.2180221, 72.2977287}}, +</div> + +<div id="cubic6x5"> +{{42.9059103, 19.6341859}, {91.762872, 58.5903164}, {27.4474096, 8.61261101}, {52.1532298, 39.3337672}}, +{{42.9059103, 19.6341859}, {54.1145994, 28.5714415}, {58.004639, 31.7917065}}, +{{58.004639, 31.7917065}, {62.019725, 35.1154878}, {61.7728162, 35.2682181}}, +{{61.7728162, 35.2682181}, {61.6064162, 35.3711481}, {58.4041375, 33.5820691}}, +{{58.4041375, 33.5820691}, {53.244257, 30.6992989}, {50.8183004, 29.6863137}}, +{{50.8183004, 29.6863137}, {46.5331956, 27.8970204}, {46.2915313, 29.5538521}}, +{{46.2915313, 29.5538521}, {45.9839754, 31.662432}, {52.1532298, 39.3337672}}, +</div> + +<div id="cubic6x5x"> +{{42.9059103, 19.6341859}, {91.762872, 58.5903164}, {27.4474096, 8.61261101}, {52.1532298, 39.3337672}}, +{{42.9059103, 19.6341859}, {53.8121244, 28.322992}, {58.004639, 31.7917065}}, +{{58.004639, 31.7917065}, {62.1971535, 35.260421}, {61.7728162, 35.2682181}}, +{{61.7728162, 35.2682181}, {61.3484789, 35.2760153}, {58.4041375, 33.5820691}}, +{{58.4041375, 33.5820691}, {54.7626269, 31.4620033}, {50.8183004, 29.6863137}}, +{{50.8183004, 29.6863137}, {46.8739739, 27.9106241}, {46.2915313, 29.5538521}}, +{{46.2915313, 29.5538521}, {45.7090887, 31.1970802}, {52.1532298, 39.3337672}}, +</div> + +<div id="cubic6x6"> +{{73.4375576, 65.030414}, {66.1679208, 84.2450892}, {7.2134248, 36.0306381}, {66.9352454, 80.6694031}}, +{{73.4375576, 65.030414}, {71.5866063, 69.9227391}, {65.0188473, 69.7835224}}, +{{65.0188473, 69.7835224}, {60.0105733, 69.677362}, {52.4355896, 66.6514651}}, +{{52.4355896, 66.6514651}, {48.2960051, 64.9978699}, {42.4281173, 61.975806}}, +{{42.4281173, 61.975806}, {40.1794784, 60.817718}, {40.5562709, 61.1722188}}, +{{40.5562709, 61.1722188}, {40.9330633, 61.5267196}, {45.4424567, 64.8118124}}, +{{45.4424567, 64.8118124}, {56.3732534, 72.774897}, {66.9352454, 80.6694031}}, +</div> + +<div id="cubic6x6x"> +{{73.4375576, 65.030414}, {66.1679208, 84.2450892}, {7.2134248, 36.0306381}, {66.9352454, 80.6694031}}, +{{73.4375576, 65.030414}, {71.1118808, 70.1709551}, {65.0188473, 69.7835224}}, +{{65.0188473, 69.7835224}, {58.9258137, 69.3960897}, {52.4355896, 66.6514651}}, +{{52.4355896, 66.6514651}, {45.9453656, 63.9068405}, {42.4281173, 61.975806}}, +{{42.4281173, 61.975806}, {40.0852803, 60.7290928}, {40.5562709, 61.1722188}}, +{{40.5562709, 61.1722188}, {41.0272614, 61.6153448}, {45.4424567, 64.8118124}}, +{{45.4424567, 64.8118124}, {51.3278432, 69.0492921}, {66.9352454, 80.6694031}}, +</div> + +<div id="cubic6x7"> +{{46.6695473, 75.0819435}, {2.22400357, 78.828021}, {62.548768, 57.1436195}, {12.8128845, 46.150303}}, +{{46.6695473, 75.0819435}, {36.8374139, 75.9106415}, {32.735691, 75.1220326}}, +{{32.735691, 75.1220326}, {29.1601585, 74.4345905}, {29.1402184, 72.2922743}}, +{{29.1402184, 72.2922743}, {29.1278273, 70.9609985}, {31.0504514, 67.4052326}}, +{{31.0504514, 67.4052326}, {33.5289159, 62.8214769}, {33.7777617, 60.3248048}}, +{{33.7777617, 60.3248048}, {34.2044612, 56.0437252}, {30.1210496, 52.8325143}}, +{{30.1210496, 52.8325143}, {25.0685705, 48.8592251}, {12.8128845, 46.150303}}, +</div> + +<div id="cubic6x7x"> +{{46.6695473, 75.0819435}, {2.22400357, 78.828021}, {62.548768, 57.1436195}, {12.8128845, 46.150303}}, +{{46.6695473, 75.0819435}, {36.5139384, 75.9210204}, {32.735691, 75.1220326}}, +{{32.735691, 75.1220326}, {28.9574435, 74.3230448}, {29.1402184, 72.2922743}}, +{{29.1402184, 72.2922743}, {29.3229933, 70.2615038}, {31.0504514, 67.4052326}}, +{{31.0504514, 67.4052326}, {33.1016834, 64.1207271}, {33.7777617, 60.3248048}}, +{{33.7777617, 60.3248048}, {34.45384, 56.5288825}, {30.1210496, 52.8325143}}, +{{30.1210496, 52.8325143}, {25.7882591, 49.1361461}, {12.8128845, 46.150303}}, +</div> + +<div id="cubic6x8"> +{{55.3467924, 13.540705}, {78.628494, 9.09824134}, {14.1422475, 88.7534345}, {78.9736115, 9.48816133}}, +{{55.3467924, 13.540705}, {60.6017653, 12.5379851}, {60.6776079, 17.0952733}}, +{{60.6776079, 17.0952733}, {60.7373059, 20.6824519}, {57.5541656, 27.8149349}}, +{{57.5541656, 27.8149349}, {55.7485732, 31.8607373}, {51.7778474, 39.2052874}}, +{{51.7778474, 39.2052874}, {48.7947857, 44.7229805}, {49.1759091, 44.7804774}}, +{{49.1759091, 44.7804774}, {49.7203899, 44.8626187}, {56.152876, 37.2125188}}, +{{56.152876, 37.2125188}, {61.4648441, 30.8950413}, {78.9736115, 9.48816133}}, +</div> + +<div id="cubic6x8x"> +{{55.3467924, 13.540705}, {78.628494, 9.09824134}, {14.1422475, 88.7534345}, {78.9736115, 9.48816133}}, +{{55.3467924, 13.540705}, {60.8509374, 12.7149155}, {60.6776079, 17.0952733}}, +{{60.6776079, 17.0952733}, {60.5042785, 21.475631}, {57.5541656, 27.8149349}}, +{{57.5541656, 27.8149349}, {54.6040527, 34.1542387}, {51.7778474, 39.2052874}}, +{{51.7778474, 39.2052874}, {48.8652599, 44.4020133}, {49.1759091, 44.7804774}}, +{{49.1759091, 44.7804774}, {49.4865584, 45.1589416}, {56.152876, 37.2125188}}, +{{56.152876, 37.2125188}, {62.8191937, 29.2660961}, {78.9736115, 9.48816133}}, +</div> + +<div id="cubic6x9"> +{{6.436938, 85.6170305}, {65.4323691, 21.8280372}, {63.8217439, 52.0501321}, {6.57091737, 37.4082543}}, +{{6.436938, 85.6170305}, {18.3889022, 72.6939321}, {29.5730232, 62.1640306}}, +{{29.5730232, 62.1640306}, {35.8331919, 56.2700528}, {44.0352491, 49.2100734}}, +{{44.0352491, 49.2100734}, {50.0664784, 44.0186496}, {50.0976641, 43.1465107}}, +{{50.0976641, 43.1465107}, {50.1288498, 42.2743718}, {44.2847347, 42.2329622}}, +{{44.2847347, 42.2329622}, {36.0580615, 42.1746705}, {29.7656368, 41.5603994}}, +{{29.7656368, 41.5603994}, {18.5096561, 40.4615824}, {6.57091737, 37.4082543}}, +</div> + +<div id="cubic6x9x"> +{{6.436938, 85.6170305}, {65.4323691, 21.8280372}, {63.8217439, 52.0501321}, {6.57091737, 37.4082543}}, +{{6.436938, 85.6170305}, {20.1874324, 70.8746109}, {29.5730232, 62.1640306}}, +{{29.5730232, 62.1640306}, {38.958614, 53.4534502}, {44.0352491, 49.2100734}}, +{{44.0352491, 49.2100734}, {50.058682, 44.2366844}, {50.0976641, 43.1465107}}, +{{50.0976641, 43.1465107}, {50.1366462, 42.0563371}, {44.2847347, 42.2329622}}, +{{44.2847347, 42.2329622}, {39.2093652, 42.3394209}, {29.7656368, 41.5603994}}, +{{29.7656368, 41.5603994}, {20.3219083, 40.7813779}, {6.57091737, 37.4082543}}, +</div> + +<div id="cubic7x0"> +{{47.0675449, 64.2273128}, {68.4467872, 85.1524572}, {57.3478562, 45.4193099}, {62.340955, 64.4298956}}, +{{47.0675449, 64.2273128}, {52.2209452, 69.2712543}, {55.5069225, 70.2618397}}, +{{55.5069225, 70.2618397}, {58.2344663, 71.0840808}, {59.6132451, 69.0985913}}, +{{59.6132451, 69.0985913}, {60.6680756, 67.5795987}, {60.901578, 64.4621115}}, +{{60.901578, 64.4621115}, {61.029698, 62.7515845}, {60.8869865, 60.0769443}}, +{{60.8869865, 60.0769443}, {60.8258684, 58.931493}, {60.9363129, 59.2030029}}, +{{60.9363129, 59.2030029}, {61.0467573, 59.4745129}, {61.7705423, 62.2490239}}, +{{61.7705423, 62.2490239}, {62.1209644, 63.5923097}, {62.340955, 64.4298956}}, +</div> + +<div id="cubic7x0x"> +{{47.0675449, 64.2273128}, {68.4467872, 85.1524572}, {57.3478562, 45.4193099}, {62.340955, 64.4298956}}, +{{47.0675449, 64.2273128}, {52.5598806, 69.5095881}, {55.5069225, 70.2618397}}, +{{55.5069225, 70.2618397}, {58.4539644, 71.0140913}, {59.6132451, 69.0985913}}, +{{59.6132451, 69.0985913}, {60.7725259, 67.1830912}, {60.901578, 64.4621115}}, +{{60.901578, 64.4621115}, {61.0306302, 61.7411317}, {60.8869865, 60.0769443}}, +{{60.8869865, 60.0769443}, {60.7982573, 58.8636155}, {60.9363129, 59.2030029}}, +{{60.9363129, 59.2030029}, {61.0743684, 59.5423904}, {61.7705423, 62.2490239}}, +{{61.7705423, 62.2490239}, {62.0120077, 63.1760698}, {62.340955, 64.4298956}}, +</div> + +<div id="cubic7x1"> +{{44.6639438, 66.9040647}, {56.6149349, 27.2102873}, {23.2993796, 92.6723405}, {44.026369, 51.1832799}}, +{{44.6639438, 66.9040647}, {47.1627908, 58.6044453}, {47.3201686, 55.4528932}}, +{{47.3201686, 55.4528932}, {47.4533435, 52.7860125}, {45.9070214, 53.8259442}}, +{{45.9070214, 53.8259442}, {44.6909451, 54.6437792}, {42.4058247, 57.7914576}}, +{{42.4058247, 57.7914576}, {41.1108979, 59.5751769}, {38.7979012, 63.1176732}}, +{{38.7979012, 63.1176732}, {37.2505608, 65.4875199}, {37.097116, 65.5770977}}, +{{37.097116, 65.5770977}, {36.8720355, 65.7084948}, {38.3585854, 62.6270533}}, +{{38.3585854, 62.6270533}, {39.7438195, 59.7556272}, {44.026369, 51.1832799}}, +</div> + +<div id="cubic7x1x"> +{{44.6639438, 66.9040647}, {56.6149349, 27.2102873}, {23.2993796, 92.6723405}, {44.026369, 51.1832799}}, +{{44.6639438, 66.9040647}, {47.2570645, 58.1934532}, {47.3201686, 55.4528932}}, +{{47.3201686, 55.4528932}, {47.3832726, 52.7123331}, {45.9070214, 53.8259442}}, +{{45.9070214, 53.8259442}, {44.4307701, 54.9395554}, {42.4058247, 57.7914576}}, +{{42.4058247, 57.7914576}, {40.3808794, 60.6433599}, {38.7979012, 63.1176732}}, +{{38.7979012, 63.1176732}, {37.3874524, 65.3142201}, {37.097116, 65.5770977}}, +{{37.097116, 65.5770977}, {36.8067796, 65.8399752}, {38.3585854, 62.6270533}}, +{{38.3585854, 62.6270533}, {39.9103912, 59.4141313}, {44.026369, 51.1832799}}, +</div> + +<div id="cubic7x2"> +{{8.53545089, 55.3230609}, {14.6846658, 5.17757498}, {19.5026836, 81.6040195}, {18.7564744, 40.0648544}}, +{{8.53545089, 55.3230609}, {9.80938657, 44.9343975}, {11.1496907, 40.6303968}}, +{{11.1496907, 40.6303968}, {12.2999484, 36.9366756}, {13.510145, 37.7040519}}, +{{13.510145, 37.7040519}, {14.4789672, 38.3183745}, {15.5359245, 41.871143}}, +{{15.5359245, 41.871143}, {16.1464176, 43.9232035}, {17.1461401, 48.4587871}}, +{{17.1461401, 48.4587871}, {17.9290951, 52.0109309}, {18.2017805, 52.6665884}}, +{{18.2017805, 52.6665884}, {18.6299694, 53.6961462}, {18.7604053, 51.1306715}}, +{{18.7604053, 51.1306715}, {18.904388, 48.2987505}, {18.7564744, 40.0648544}}, +</div> + +<div id="cubic7x2x"> +{{8.53545089, 55.3230609}, {14.6846658, 5.17757498}, {19.5026836, 81.6040195}, {18.7564744, 40.0648544}}, +{{8.53545089, 55.3230609}, {9.89590602, 44.4510387}, {11.1496907, 40.6303968}}, +{{11.1496907, 40.6303968}, {12.4034754, 36.8097549}, {13.510145, 37.7040519}}, +{{13.510145, 37.7040519}, {14.6168146, 38.5983488}, {15.5359245, 41.871143}}, +{{15.5359245, 41.871143}, {16.4550345, 45.1439372}, {17.1461401, 48.4587871}}, +{{17.1461401, 48.4587871}, {17.7900216, 51.5253445}, {18.2017805, 52.6665884}}, +{{18.2017805, 52.6665884}, {18.6135393, 53.8078322}, {18.7604053, 51.1306715}}, +{{18.7604053, 51.1306715}, {18.9072713, 48.4535108}, {18.7564744, 40.0648544}}, +</div> + +<div id="cubic7x3"> +{{77.2429303, 21.9290386}, {61.3518447, 40.4530391}, {94.2286334, 0.642292155}, {95.0042533, 36.4855481}}, +{{77.2429303, 21.9290386}, {76.5648343, 22.7194849}, {75.4687566, 23.992131}}, +{{75.4687566, 23.992131}, {73.1344126, 26.702517}, {72.9524614, 27.0039848}}, +{{72.9524614, 27.0039848}, {72.7705102, 27.3054527}, {74.013147, 26.4038735}}, +{{74.013147, 26.4038735}, {76.9396956, 24.2805538}, {79.071521, 23.1293275}}, +{{79.071521, 23.1293275}, {82.9580525, 21.0305265}, {85.9547875, 20.9037075}}, +{{85.9547875, 20.9037075}, {89.8728448, 20.737899}, {92.1150103, 23.9485892}}, +{{92.1150103, 23.9485892}, {94.8166786, 27.8172686}, {95.0042533, 36.4855481}}, +</div> + +<div id="cubic7x3x"> +{{77.2429303, 21.9290386}, {61.3518447, 40.4530391}, {94.2286334, 0.642292155}, {95.0042533, 36.4855481}}, +{{77.2429303, 21.9290386}, {76.2273572, 23.1121054}, {75.4687566, 23.992131}}, +{{75.4687566, 23.992131}, {73.1799004, 26.6271501}, {72.9524614, 27.0039848}}, +{{72.9524614, 27.0039848}, {72.7250224, 27.3808196}, {74.013147, 26.4038735}}, +{{74.013147, 26.4038735}, {75.7676189, 25.0320659}, {79.071521, 23.1293275}}, +{{79.071521, 23.1293275}, {82.3754232, 21.226589}, {85.9547875, 20.9037075}}, +{{85.9547875, 20.9037075}, {89.5341519, 20.580826}, {92.1150103, 23.9485892}}, +{{92.1150103, 23.9485892}, {94.6958688, 27.3163524}, {95.0042533, 36.4855481}}, +</div> + +<div id="cubic7x4"> +{{85.1880251, 55.1384624}, {12.1381459, 5.8187271}, {95.3464197, 87.2766355}, {58.4136199, 57.7104629}}, +{{85.1880251, 55.1384624}, {69.4954757, 44.5436142}, {61.7319269, 40.861468}}, +{{61.7319269, 40.861468}, {55.009991, 37.6733448}, {54.1223283, 39.6260005}}, +{{54.1223283, 39.6260005}, {53.4043154, 41.2054652}, {56.5289517, 46.3315706}}, +{{56.5289517, 46.3315706}, {58.3527212, 49.323546}, {63.1215192, 55.8776895}}, +{{63.1215192, 55.8776895}, {66.7797089, 60.9054346}, {67.68997, 62.4640064}}, +{{67.68997, 62.4640064}, {69.1578236, 64.9773019}, {67.3518779, 64.1520255}}, +{{67.3518779, 64.1520255}, {65.2740366, 63.2024988}, {58.4136199, 57.7104629}}, +</div> + +<div id="cubic7x4x"> +{{85.1880251, 55.1384624}, {12.1381459, 5.8187271}, {95.3464197, 87.2766355}, {58.4136199, 57.7104629}}, +{{85.1880251, 55.1384624}, {68.7695663, 44.1020224}, {61.7319269, 40.861468}}, +{{61.7319269, 40.861468}, {54.6942874, 37.6209137}, {54.1223283, 39.6260005}}, +{{54.1223283, 39.6260005}, {53.5503693, 41.6310872}, {56.5289517, 46.3315706}}, +{{56.5289517, 46.3315706}, {59.5075341, 51.032054}, {63.1215192, 55.8776895}}, +{{63.1215192, 55.8776895}, {66.1706775, 59.9915119}, {67.68997, 62.4640064}}, +{{67.68997, 62.4640064}, {69.2092626, 64.9365008}, {67.3518779, 64.1520255}}, +{{67.3518779, 64.1520255}, {65.4944933, 63.3675501}, {58.4136199, 57.7104629}}, +</div> + +<div id="cubic7x5"> +{{8.65591127, 79.9006976}, {91.0247206, 52.4786449}, {8.58452539, 80.1182901}, {48.1023732, 56.5861463}}, +{{8.65591127, 79.9006976}, {10.1949106, 79.3883372}, {13.1021747, 78.4205896}}, +{{13.1021747, 78.4205896}, {33.3914306, 71.6668594}, {38.6134953, 69.8848279}}, +{{38.6134953, 69.8848279}, {45.9243859, 67.3899838}, {46.7629899, 66.8658296}}, +{{46.7629899, 66.8658296}, {47.3619928, 66.4914338}, {44.5359397, 66.7758818}}, +{{44.5359397, 66.7758818}, {40.3498242, 67.197223}, {38.6707421, 67.0021236}}, +{{38.6707421, 67.0021236}, {35.6941333, 66.6562593}, {37.1605001, 64.6054153}}, +{{37.1605001, 64.6054153}, {39.032712, 61.9869609}, {48.1023732, 56.5861463}}, +</div> + +<div id="cubic7x5x"> +{{8.65591127, 79.9006976}, {91.0247206, 52.4786449}, {8.58452539, 80.1182901}, {48.1023732, 56.5861463}}, +{{8.65591127, 79.9006976}, {10.9639426, 79.1323302}, {13.1021747, 78.4205896}}, +{{13.1021747, 78.4205896}, {31.0714516, 72.4500538}, {38.6134953, 69.8848279}}, +{{38.6134953, 69.8848279}, {46.155539, 67.319602}, {46.7629899, 66.8658296}}, +{{46.7629899, 66.8658296}, {47.3704409, 66.4120572}, {44.5359397, 66.7758818}}, +{{44.5359397, 66.7758818}, {41.5267469, 67.1697889}, {38.6707421, 67.0021236}}, +{{38.6707421, 67.0021236}, {35.8147372, 66.8344583}, {37.1605001, 64.6054153}}, +{{37.1605001, 64.6054153}, {38.5062629, 62.3763723}, {48.1023732, 56.5861463}}, +</div> + +<div id="cubic7x6"> +{{42.8441148, 81.0382013}, {9.0486696, 80.9900212}, {99.2855478, 92.2020003}, {39.0193165, 97.6524087}}, +{{42.8441148, 81.0382013}, {36.5292256, 81.0291985}, {35.3205259, 81.5652507}}, +{{35.3205259, 81.5652507}, {34.274399, 82.0292026}, {36.9288084, 83.0293311}}, +{{36.9288084, 83.0293311}, {38.5699459, 83.647679}, {43.916545, 85.1977854}}, +{{43.916545, 85.1977854}, {50.735588, 87.1747884}, {53.7318941, 88.2602772}}, +{{53.7318941, 88.2602772}, {58.8545207, 90.11608}, {59.9920782, 91.5927712}}, +{{59.9920782, 91.5927712}, {61.3953813, 93.4144333}, {56.9901885, 94.8414282}}, +{{56.9901885, 94.8414282}, {51.9120881, 96.4864013}, {39.0193165, 97.6524087}}, +</div> + +<div id="cubic7x6x"> +{{42.8441148, 81.0382013}, {9.0486696, 80.9900212}, {99.2855478, 92.2020003}, {39.0193165, 97.6524087}}, +{{42.8441148, 81.0382013}, {36.3303003, 81.0383861}, {35.3205259, 81.5652507}}, +{{35.3205259, 81.5652507}, {34.3107514, 82.0921153}, {36.9288084, 83.0293311}}, +{{36.9288084, 83.0293311}, {39.5468653, 83.9665469}, {43.916545, 85.1977854}}, +{{43.916545, 85.1977854}, {48.9996472, 86.6173008}, {53.7318941, 88.2602772}}, +{{53.7318941, 88.2602772}, {58.4641409, 89.9032535}, {59.9920782, 91.5927712}}, +{{59.9920782, 91.5927712}, {61.5200154, 93.2822889}, {56.9901885, 94.8414282}}, +{{56.9901885, 94.8414282}, {52.4603617, 96.4005675}, {39.0193165, 97.6524087}}, +</div> + +<div id="cubic7x7"> +{{70.2955832, 57.867012}, {70.8709129, 27.4331047}, {68.1912432, 90.2241446}, {97.1991291, 25.763215}}, +{{70.2955832, 57.867012}, {70.3286385, 56.1184463}, {70.3691418, 53.5027125}}, +{{70.3691418, 53.5027125}, {70.4294268, 49.6094598}, {70.5008735, 49.1586526}}, +{{70.5008735, 49.1586526}, {70.5723202, 48.7078455}, {70.9407155, 49.8962556}}, +{{70.9407155, 49.8962556}, {71.8329974, 52.7746761}, {72.7964345, 54.1820074}}, +{{72.7964345, 54.1820074}, {74.5546706, 56.7503333}, {77.0780289, 56.0896348}}, +{{77.0780289, 56.0896348}, {80.3799099, 55.2250934}, {84.85557, 48.8673125}}, +{{84.85557, 48.8673125}, {90.2513448, 41.2024868}, {97.1991291, 25.763215}}, +</div> + +<div id="cubic7x7x"> +{{70.2955832, 57.867012}, {70.8709129, 27.4331047}, {68.1912432, 90.2241446}, {97.1991291, 25.763215}}, +{{70.2955832, 57.867012}, {70.3435094, 55.2546173}, {70.3691418, 53.5027125}}, +{{70.3691418, 53.5027125}, {70.4115651, 49.7221615}, {70.5008735, 49.1586526}}, +{{70.5008735, 49.1586526}, {70.5901819, 48.5951437}, {70.9407155, 49.8962556}}, +{{70.9407155, 49.8962556}, {71.3958651, 51.7896844}, {72.7964345, 54.1820074}}, +{{72.7964345, 54.1820074}, {74.1970039, 56.5743304}, {77.0780289, 56.0896348}}, +{{77.0780289, 56.0896348}, {79.9590538, 55.6049393}, {84.85557, 48.8673125}}, +{{84.85557, 48.8673125}, {89.7520861, 42.1296858}, {97.1991291, 25.763215}}, +</div> + +<div id="cubic7x8"> +{{50.528201, 27.4745214}, {64.2810473, 71.5620589}, {43.5236709, 2.33669765}, {72.8774712, 51.6581711}}, +{{50.528201, 27.4745214}, {53.3761101, 36.6040713}, {54.38742, 39.6099548}}, +{{54.38742, 39.6099548}, {55.5064406, 42.9359834}, {55.7720854, 42.9677817}}, +{{55.7720854, 42.9677817}, {55.9546136, 42.9896307}, {55.8827854, 40.8375726}}, +{{55.8827854, 40.8375726}, {55.7725733, 37.5354848}, {55.9802468, 35.9707481}}, +{{55.9802468, 35.9707481}, {56.3474228, 33.2042239}, {57.7009449, 33.0167369}}, +{{57.7009449, 33.0167369}, {59.424989, 32.7779259}, {62.7612346, 36.6782932}}, +{{62.7612346, 36.6782932}, {66.7088662, 41.293425}, {72.8774712, 51.6581711}}, +</div> + +<div id="cubic7x8x"> +{{50.528201, 27.4745214}, {64.2810473, 71.5620589}, {43.5236709, 2.33669765}, {72.8774712, 51.6581711}}, +{{50.528201, 27.4745214}, {53.2265224, 36.1478361}, {54.38742, 39.6099548}}, +{{54.38742, 39.6099548}, {55.5483175, 43.0720735}, {55.7720854, 42.9677817}}, +{{55.7720854, 42.9677817}, {55.9958532, 42.8634898}, {55.8827854, 40.8375726}}, +{{55.8827854, 40.8375726}, {55.7402514, 38.5138013}, {55.9802468, 35.9707481}}, +{{55.9802468, 35.9707481}, {56.2202423, 33.4276949}, {57.7009449, 33.0167369}}, +{{57.7009449, 33.0167369}, {59.1816474, 32.6057789}, {62.7612346, 36.6782932}}, +{{62.7612346, 36.6782932}, {66.3408218, 40.7508075}, {72.8774712, 51.6581711}}, +</div> + +<div id="cubic7x9"> +{{30.3413925, 47.7835835}, {98.6874047, 39.210338}, {8.15117029, 96.7190508}, {57.0872154, 64.8290379}}, +{{30.3413925, 47.7835835}, {46.0782555, 45.8095694}, {52.5540659, 48.2453346}}, +{{52.5540659, 48.2453346}, {57.9511897, 50.2753703}, {56.8130484, 55.3244869}}, +{{56.8130484, 55.3244869}, {55.9369414, 59.2111449}, {51.1961195, 64.811489}}, +{{51.1961195, 64.811489}, {48.5753558, 67.9074035}, {43.7810591, 72.4967897}}, +{{43.7810591, 72.4967897}, {41.2648644, 74.905441}, {42.230691, 74.4021224}}, +{{42.230691, 74.4021224}, {43.1965176, 73.8988039}, {51.5076718, 68.470241}}, +{{51.5076718, 68.470241}, {54.9756852, 66.2050527}, {57.0872154, 64.8290379}}, +</div> + +<div id="cubic7x9x"> +{{30.3413925, 47.7835835}, {98.6874047, 39.210338}, {8.15117029, 96.7190508}, {57.0872154, 64.8290379}}, +{{30.3413925, 47.7835835}, {46.9458744, 45.8339148}, {52.5540659, 48.2453346}}, +{{52.5540659, 48.2453346}, {58.1622574, 50.6567543}, {56.8130484, 55.3244869}}, +{{56.8130484, 55.3244869}, {55.4638393, 59.9922194}, {51.1961195, 64.811489}}, +{{51.1961195, 64.811489}, {46.9283998, 69.6307587}, {43.7810591, 72.4967897}}, +{{43.7810591, 72.4967897}, {41.0234077, 75.0312707}, {42.230691, 74.4021224}}, +{{42.230691, 74.4021224}, {43.4379742, 73.7729742}, {51.5076718, 68.470241}}, +{{51.5076718, 68.470241}, {53.9259122, 66.8899375}, {57.0872154, 64.8290379}}, +</div> + +<div id="cubic8x0"> +{{42.5967063, 22.8420382}, {6.13525533, 15.2363991}, {78.1588409, 15.6382141}, {31.4640028, 15.4944166}}, +{{42.5967063, 22.8420382}, {34.7914244, 21.2139034}, {32.6593413, 19.878761}}, +{{32.6593413, 19.878761}, {30.8695713, 18.7579803}, {33.1023831, 17.8591237}}, +{{33.1023831, 17.8591237}, {34.8391625, 17.1599535}, {39.0195021, 16.5984277}}, +{{39.0195021, 16.5984277}, {41.3590736, 16.2841638}, {45.5043686, 15.9119743}}, +{{45.5043686, 15.9119743}, {47.7538437, 15.7100029}, {47.8024311, 15.6545014}}, +{{47.8024311, 15.6545014}, {47.8704535, 15.5767993}, {44.9932779, 15.5487509}}, +{{44.9932779, 15.5487509}, {42.9381525, 15.5287163}, {34.6690635, 15.5040796}}, +{{34.6690635, 15.5040796}, {32.6017407, 15.4979203}, {31.4640028, 15.4944166}}, +</div> + +<div id="cubic8x0x"> +{{42.5967063, 22.8420382}, {6.13525533, 15.2363991}, {78.1588409, 15.6382141}, {31.4640028, 15.4944166}}, +{{42.5967063, 22.8420382}, {34.4196308, 21.1014023}, {32.6593413, 19.878761}}, +{{32.6593413, 19.878761}, {30.8990517, 18.6561197}, {33.1023831, 17.8591237}}, +{{33.1023831, 17.8591237}, {35.3057145, 17.0621277}, {39.0195021, 16.5984277}}, +{{39.0195021, 16.5984277}, {42.7332897, 16.1347277}, {45.5043686, 15.9119743}}, +{{45.5043686, 15.9119743}, {47.6292231, 15.7339768}, {47.8024311, 15.6545014}}, +{{47.8024311, 15.6545014}, {47.9756391, 15.575026}, {44.9932779, 15.5487509}}, +{{44.9932779, 15.5487509}, {42.0109167, 15.5224759}, {34.6690635, 15.5040796}}, +{{34.6690635, 15.5040796}, {33.169788, 15.4996412}, {31.4640028, 15.4944166}}, +</div> + +<div id="cubic8x1"> +{{29.0323957, 47.4745379}, {4.55778772, 2.73824763}, {21.7278637, 80.2053625}, {11.5269861, 34.0549996}}, +{{29.0323957, 47.4745379}, {23.6693619, 37.6716337}, {20.3221199, 34.4936205}}, +{{20.3221199, 34.4936205}, {17.5126817, 31.826221}, {16.162445, 33.8631071}}, +{{16.162445, 33.8631071}, {15.1123784, 35.4471745}, {14.9546458, 39.8886357}}, +{{14.9546458, 39.8886357}, {14.8663892, 42.3737787}, {15.0999972, 46.8758445}}, +{{15.0999972, 46.8758445}, {15.2259779, 49.3037298}, {15.1224749, 49.3309043}}, +{{15.1224749, 49.3309043}, {14.9775707, 49.3689487}, {14.2215808, 46.1220869}}, +{{14.2215808, 46.1220869}, {13.6815881, 43.8028999}, {11.62512, 34.4989774}}, +{{11.62512, 34.4989774}, {11.559983, 34.2042829}, {11.5269861, 34.0549996}}, +</div> + +<div id="cubic8x1x"> +{{29.0323957, 47.4745379}, {4.55778772, 2.73824763}, {21.7278637, 80.2053625}, {11.5269861, 34.0549996}}, +{{29.0323957, 47.4745379}, {23.339767, 37.184683}, {20.3221199, 34.4936205}}, +{{20.3221199, 34.4936205}, {17.3044729, 31.802558}, {16.162445, 33.8631071}}, +{{16.162445, 33.8631071}, {15.0204171, 35.9236561}, {14.9546458, 39.8886357}}, +{{14.9546458, 39.8886357}, {14.8888745, 43.8536153}, {15.0999972, 46.8758445}}, +{{15.0999972, 46.8758445}, {15.2455546, 49.1755419}, {15.1224749, 49.3309043}}, +{{15.1224749, 49.3309043}, {14.9993952, 49.4862668}, {14.2215808, 46.1220869}}, +{{14.2215808, 46.1220869}, {13.4437665, 42.757907}, {11.62512, 34.4989774}}, +{{11.62512, 34.4989774}, {11.5764809, 34.2789225}, {11.5269861, 34.0549996}}, +</div> + +<div id="cubic8x2"> +{{30.5187597, 28.7944151}, {47.7341773, 68.3182353}, {24.579915, 14.6321317}, {22.237118, 39.2417454}}, +{{30.5187597, 28.7944151}, {30.823715, 29.4945431}, {31.3959629, 30.8080078}}, +{{31.3959629, 30.8080078}, {34.9281707, 38.9153861}, {35.7821411, 40.9504208}}, +{{35.7821411, 40.9504208}, {36.9776996, 43.7994693}, {36.8148424, 43.845334}}, +{{36.8148424, 43.845334}, {36.6985159, 43.8780945}, {35.3792396, 41.9741019}}, +{{35.3792396, 41.9741019}, {33.3589087, 39.0583404}, {32.0725075, 37.4554574}}, +{{32.0725075, 37.4554574}, {29.7893226, 34.6105606}, {28.0338583, 33.4024856}}, +{{28.0338583, 33.4024856}, {25.7901854, 31.8584352}, {24.3823693, 32.9522328}}, +{{24.3823693, 32.9522328}, {22.7123482, 34.2497498}, {22.237118, 39.2417454}}, +</div> + +<div id="cubic8x2x"> +{{30.5187597, 28.7944151}, {47.7341773, 68.3182353}, {24.579915, 14.6321317}, {22.237118, 39.2417454}}, +{{30.5187597, 28.7944151}, {30.9761076, 29.8443688}, {31.3959629, 30.8080078}}, +{{31.3959629, 30.8080078}, {34.5380678, 38.0012585}, {35.7821411, 40.9504208}}, +{{35.7821411, 40.9504208}, {37.0262144, 43.899583}, {36.8148424, 43.845334}}, +{{36.8148424, 43.845334}, {36.6034705, 43.791085}, {35.3792396, 41.9741019}}, +{{35.3792396, 41.9741019}, {34.0487375, 39.9904922}, {32.0725075, 37.4554574}}, +{{32.0725075, 37.4554574}, {30.0962775, 34.9204225}, {28.0338583, 33.4024856}}, +{{28.0338583, 33.4024856}, {25.9714391, 31.8845487}, {24.3823693, 32.9522328}}, +{{24.3823693, 32.9522328}, {22.7932996, 34.019917}, {22.237118, 39.2417454}}, +</div> + +<div id="cubic8x3"> +{{44.0194731, 35.2849254}, {33.7413378, 90.6639866}, {89.6236054, 3.93610117}, {54.0523993, 58.6752083}}, +{{44.0194731, 35.2849254}, {41.8034025, 47.2252151}, {43.4093427, 51.8147312}}, +{{43.4093427, 51.8147312}, {44.7573046, 55.6669869}, {48.7793294, 54.2868164}}, +{{48.7793294, 54.2868164}, {51.9073817, 53.2134153}, {56.6514498, 48.9586591}}, +{{56.6514498, 48.9586591}, {59.3060696, 46.5778416}, {63.5477208, 42.0877376}}, +{{63.5477208, 42.0877376}, {65.8388976, 39.6623562}, {66.0159848, 39.6831127}}, +{{66.0159848, 39.6831127}, {66.2639069, 39.7121719}, {64.0479481, 43.2239426}}, +{{64.0479481, 43.2239426}, {62.4651204, 45.7323502}, {55.9567221, 55.7452241}}, +{{55.9567221, 55.7452241}, {54.718939, 57.649497}, {54.0523993, 58.6752083}}, +</div> + +<div id="cubic8x3x"> +{{44.0194731, 35.2849254}, {33.7413378, 90.6639866}, {89.6236054, 3.93610117}, {54.0523993, 58.6752083}}, +{{44.0194731, 35.2849254}, {41.7846308, 47.8464432}, {43.4093427, 51.8147312}}, +{{43.4093427, 51.8147312}, {45.0340547, 55.7830192}, {48.7793294, 54.2868164}}, +{{48.7793294, 54.2868164}, {52.524604, 52.7906136}, {56.6514498, 48.9586591}}, +{{56.6514498, 48.9586591}, {60.7782955, 45.1267046}, {63.5477208, 42.0877376}}, +{{63.5477208, 42.0877376}, {65.6800669, 39.7784361}, {66.0159848, 39.6831127}}, +{{66.0159848, 39.6831127}, {66.3519027, 39.5877893}, {64.0479481, 43.2239426}}, +{{64.0479481, 43.2239426}, {61.7439935, 46.8600958}, {55.9567221, 55.7452241}}, +{{55.9567221, 55.7452241}, {55.0519496, 57.1371078}, {54.0523993, 58.6752083}}, +</div> + +<div id="cubic8x4"> +{{34.4823321, 44.5556425}, {46.6831036, 2.92242272}, {17.1586486, 85.4072306}, {39.3243103, 23.6824388}}, +{{34.4823321, 44.5556425}, {36.9549821, 36.1181121}, {37.4421857, 33.458373}}, +{{37.4421857, 33.458373}, {37.852416, 31.2188464}, {36.8498458, 33.1020754}}, +{{36.8498458, 33.1020754}, {36.0666826, 34.5731701}, {34.4114682, 38.5859621}}, +{{34.4114682, 38.5859621}, {33.4805756, 40.8427565}, {31.8332086, 45.009246}}, +{{31.8332086, 45.009246}, {30.8106719, 47.5954265}, {30.8033416, 47.5462886}}, +{{30.8033416, 47.5462886}, {30.793079, 47.4774956}, {32.1835801, 43.5816708}}, +{{32.1835801, 43.5816708}, {33.1767952, 40.7989388}, {37.1569859, 29.7171487}}, +{{37.1569859, 29.7171487}, {38.5382511, 25.8713805}, {39.3243103, 23.6824388}}, +</div> + +<div id="cubic8x4x"> +{{34.4823321, 44.5556425}, {46.6831036, 2.92242272}, {17.1586486, 85.4072306}, {39.3243103, 23.6824388}}, +{{34.4823321, 44.5556425}, {37.0635768, 35.7091664}, {37.4421857, 33.458373}}, +{{37.4421857, 33.458373}, {37.8207947, 31.2075797}, {36.8498458, 33.1020754}}, +{{36.8498458, 33.1020754}, {35.878897, 34.996571}, {34.4114682, 38.5859621}}, +{{34.4114682, 38.5859621}, {32.9440394, 42.1753532}, {31.8332086, 45.009246}}, +{{31.8332086, 45.009246}, {30.8636314, 47.4784019}, {30.8033416, 47.5462886}}, +{{30.8033416, 47.5462886}, {30.7430517, 47.6141753}, {32.1835801, 43.5816708}}, +{{32.1835801, 43.5816708}, {33.6241085, 39.5491663}, {37.1569859, 29.7171487}}, +{{37.1569859, 29.7171487}, {38.146263, 26.9628595}, {39.3243103, 23.6824388}}, +</div> + +<div id="cubic8x5"> +{{67.1009526, 65.7102964}, {92.9511368, 29.7558215}, {6.09136899, 77.6386629}, {73.0077305, 40.9268787}}, +{{67.1009526, 65.7102964}, {72.234988, 58.569475}, {72.0584002, 54.9887776}}, +{{72.0584002, 54.9887776}, {71.9092626, 51.9646911}, {67.9699024, 51.5063347}}, +{{67.9699024, 51.5063347}, {64.8799872, 51.1468138}, {59.401457, 52.3770387}}, +{{59.401457, 52.3770387}, {56.3059837, 53.072139}, {50.919062, 54.7149606}}, +{{50.919062, 54.7149606}, {47.1095083, 55.8767404}, {47.0889098, 55.6405516}}, +{{47.0889098, 55.6405516}, {47.0600718, 55.3098873}, {52.2780952, 52.3607383}}, +{{52.2780952, 52.3607383}, {56.0052548, 50.2542034}, {70.9344915, 42.0642523}}, +{{70.9344915, 42.0642523}, {72.2995322, 41.3154119}, {73.0077305, 40.9268787}}, +</div> + +<div id="cubic8x5x"> +{{67.1009526, 65.7102964}, {92.9511368, 29.7558215}, {6.09136899, 77.6386629}, {73.0077305, 40.9268787}}, +{{67.1009526, 65.7102964}, {72.4119125, 58.1790269}, {72.0584002, 54.9887776}}, +{{72.0584002, 54.9887776}, {71.7048879, 51.7985283}, {67.9699024, 51.5063347}}, +{{67.9699024, 51.5063347}, {64.2349168, 51.2141411}, {59.401457, 52.3770387}}, +{{59.401457, 52.3770387}, {54.5679971, 53.5399363}, {50.919062, 54.7149606}}, +{{50.919062, 54.7149606}, {47.3051356, 55.8776986}, {47.0889098, 55.6405516}}, +{{47.0889098, 55.6405516}, {46.8726839, 55.4034046}, {52.2780952, 52.3607383}}, +{{52.2780952, 52.3607383}, {57.6835065, 49.3180721}, {70.9344915, 42.0642523}}, +{{70.9344915, 42.0642523}, {71.9455119, 41.5096286}, {73.0077305, 40.9268787}}, +</div> + +<div id="cubic8x6"> +{{34.6917773, 64.7007906}, {26.1879157, 40.299837}, {19.3601908, 86.7271998}, {24.0468774, 55.867852}}, +{{34.6917773, 64.7007906}, {32.8936408, 59.5412235}, {30.9809892, 57.9762826}}, +{{30.9809892, 57.9762826}, {29.3733084, 56.6608702}, {27.7048898, 57.9022642}}, +{{27.7048898, 57.9022642}, {26.4047253, 58.8696572}, {25.0679408, 61.4005651}}, +{{25.0679408, 61.4005651}, {24.3182009, 62.820033}, {23.2746043, 65.3930147}}, +{{23.2746043, 65.3930147}, {22.674283, 66.8731035}, {22.5736375, 66.8767729}}, +{{22.5736375, 66.8767729}, {22.4327337, 66.88191}, {22.7095685, 64.8303341}}, +{{22.7095685, 64.8303341}, {22.9073076, 63.3649228}, {23.7989097, 57.4996081}}, +{{23.7989097, 57.4996081}, {23.9603141, 56.4378254}, {24.0468774, 55.867852}}, +</div> + +<div id="cubic8x6x"> +{{34.6917773, 64.7007906}, {26.1879157, 40.299837}, {19.3601908, 86.7271998}, {24.0468774, 55.867852}}, +{{34.6917773, 64.7007906}, {32.7532689, 59.2911428}, {30.9809892, 57.9762826}}, +{{30.9809892, 57.9762826}, {29.2087096, 56.6614223}, {27.7048898, 57.9022642}}, +{{27.7048898, 57.9022642}, {26.2010699, 59.1431061}, {25.0679408, 61.4005651}}, +{{25.0679408, 61.4005651}, {23.9348117, 63.658024}, {23.2746043, 65.3930147}}, +{{23.2746043, 65.3930147}, {22.7294605, 66.7981817}, {22.5736375, 66.8767729}}, +{{22.5736375, 66.8767729}, {22.4178145, 66.955364}, {22.7095685, 64.8303341}}, +{{22.7095685, 64.8303341}, {23.0013225, 62.7053042}, {23.7989097, 57.4996081}}, +{{23.7989097, 57.4996081}, {23.9170479, 56.7225788}, {24.0468774, 55.867852}}, +</div> + +<div id="cubic8x7"> +{{33.7213174, 54.1809799}, {19.7290722, 86.516309}, {79.6055485, 30.4535282}, {32.4492169, 73.9888241}}, +{{33.7213174, 54.1809799}, {30.929259, 60.6332771}, {31.7178101, 63.1685506}}, +{{31.7178101, 63.1685506}, {32.3822203, 65.3046982}, {35.5832592, 64.6365068}}, +{{35.5832592, 64.6365068}, {38.0860576, 64.1140676}, {42.1661464, 61.8599641}}, +{{42.1661464, 61.8599641}, {44.4631798, 60.5909351}, {48.3149537, 58.1140379}}, +{{48.3149537, 58.1140379}, {50.7761073, 56.5313841}, {50.8756876, 56.6229029}}, +{{50.8756876, 56.6229029}, {51.0150999, 56.7510292}, {48.1271345, 59.4792497}}, +{{48.1271345, 59.4792497}, {46.064302, 61.4279786}, {37.7133917, 69.1313755}}, +{{37.7133917, 69.1313755}, {34.3790695, 72.2071608}, {32.4492169, 73.9888241}}, +</div> + +<div id="cubic8x7x"> +{{33.7213174, 54.1809799}, {19.7290722, 86.516309}, {79.6055485, 30.4535282}, {32.4492169, 73.9888241}}, +{{33.7213174, 54.1809799}, {30.8583849, 60.9640583}, {31.7178101, 63.1685506}}, +{{31.7178101, 63.1685506}, {32.5772353, 65.3730429}, {35.5832592, 64.6365068}}, +{{35.5832592, 64.6365068}, {38.589283, 63.8999708}, {42.1661464, 61.8599641}}, +{{42.1661464, 61.8599641}, {45.7430098, 59.8199575}, {48.3149537, 58.1140379}}, +{{48.3149537, 58.1140379}, {50.6281545, 56.5876371}, {50.8756876, 56.6229029}}, +{{50.8756876, 56.6229029}, {51.1232206, 56.6581687}, {48.1271345, 59.4792497}}, +{{48.1271345, 59.4792497}, {45.1310483, 62.3003307}, {37.7133917, 69.1313755}}, +{{37.7133917, 69.1313755}, {35.340896, 71.3195506}, {32.4492169, 73.9888241}}, +</div> + +<div id="cubic8x8"> +{{53.9853472, 31.729689}, {80.8833995, 7.2950833}, {8.46509939, 72.9253675}, {56.6511208, 35.3872682}}, +{{53.9853472, 31.729689}, {54.6892116, 31.0902877}, {55.8968586, 29.9930402}}, +{{55.8968586, 29.9930402}, {59.7242319, 26.5155538}, {60.0744106, 26.2078693}}, +{{60.0744106, 26.2078693}, {60.4245892, 25.9001849}, {58.6982878, 27.5315648}}, +{{58.6982878, 27.5315648}, {54.8548255, 31.1636922}, {52.2592609, 33.6639071}}, +{{52.2592609, 33.6639071}, {47.5369986, 38.2126941}, {44.5524326, 41.278553}}, +{{44.5524326, 41.278553}, {40.6568202, 45.2802731}, {39.8604011, 46.6125979}}, +{{39.8604011, 46.6125979}, {38.901811, 48.2162178}, {42.4657645, 45.9031378}}, +{{42.4657645, 45.9031378}, {46.5800498, 43.232881}, {56.6511208, 35.3872682}}, +</div> + +<div id="cubic8x8x"> +{{53.9853472, 31.729689}, {80.8833995, 7.2950833}, {8.46509939, 72.9253675}, {56.6511208, 35.3872682}}, +{{53.9853472, 31.729689}, {55.0401587, 30.7714526}, {55.8968586, 29.9930402}}, +{{55.8968586, 29.9930402}, {59.6366873, 26.5924749}, {60.0744106, 26.2078693}}, +{{60.0744106, 26.2078693}, {60.5121339, 25.8232638}, {58.6982878, 27.5315648}}, +{{58.6982878, 27.5315648}, {56.3310494, 29.756797}, {52.2592609, 33.6639071}}, +{{52.2592609, 33.6639071}, {48.1874723, 37.5710172}, {44.5524326, 41.278553}}, +{{44.5524326, 41.278553}, {40.9173929, 44.9860887}, {39.8604011, 46.6125979}}, +{{39.8604011, 46.6125979}, {38.8034093, 48.2391072}, {42.4657645, 45.9031378}}, +{{42.4657645, 45.9031378}, {46.1281196, 43.5671684}, {56.6511208, 35.3872682}}, +</div> + +<div id="cubic8x9"> +{{73.1810322, 53.6088109}, {3.28446082, 1.93300047}, {87.9389074, 89.2160727}, {54.5340817, 54.3107021}}, +{{73.1810322, 53.6088109}, {58.5574459, 42.7973267}, {51.3867695, 38.9320081}}, +{{51.3867695, 38.9320081}, {45.1924119, 35.5929695}, {44.6615376, 37.4897176}}, +{{44.6615376, 37.4897176}, {44.2222697, 39.0591673}, {47.6643015, 44.1654891}}, +{{47.6643015, 44.1654891}, {50.2846557, 48.0528359}, {55.0540263, 53.8428721}}, +{{55.0540263, 53.8428721}, {57.6549797, 57.0004406}, {61.4896769, 61.4054165}}, +{{61.4896769, 61.4054165}, {62.8763033, 62.9982556}, {62.6160157, 62.7489128}}, +{{62.6160157, 62.7489128}, {62.3557281, 62.49957}, {59.4073763, 59.4106743}}, +{{59.4073763, 59.4106743}, {56.5808171, 56.449377}, {54.5340817, 54.3107021}}, +</div> + +<div id="cubic8x9x"> +{{73.1810322, 53.6088109}, {3.28446082, 1.93300047}, {87.9389074, 89.2160727}, {54.5340817, 54.3107021}}, +{{73.1810322, 53.6088109}, {57.8490138, 42.3222252}, {51.3867695, 38.9320081}}, +{{51.3867695, 38.9320081}, {44.9245252, 35.5417911}, {44.6615376, 37.4897176}}, +{{44.6615376, 37.4897176}, {44.3985499, 39.4376442}, {47.6643015, 44.1654891}}, +{{47.6643015, 44.1654891}, {50.9300531, 48.893334}, {55.0540263, 53.8428721}}, +{{55.0540263, 53.8428721}, {59.1779995, 58.7924103}, {61.4896769, 61.4054165}}, +{{61.4896769, 61.4054165}, {62.9413752, 63.0605913}, {62.6160157, 62.7489128}}, +{{62.6160157, 62.7489128}, {62.2906562, 62.4372343}, {59.4073763, 59.4106743}}, +{{59.4073763, 59.4106743}, {57.5885087, 57.5036974}, {54.5340817, 54.3107021}}, +</div> + +<div id="cubic4"> +{{24.2578299, 1.34695745}, {6.77689729, 99.312693}, {3.18338154, 3.09354817}, {59.132973, 47.8778685}}, +{{38.313885, 41.465269}, {48.4308047, 76.5337766}, {93.264044, 88.7879534}, {83.3354337, 18.6335197}} +</div> + +<div id="cubic5"> +{{24.0062249, 72.6211198}, {22.3913226, 30.9587957}, {80.7539402, 31.4736433}, {99.6348716, 63.2867312}}, +{{43.1612821, 11.6690897}, {24.4801394, 37.7033828}, {77.5229567, 28.3334108}, {60.0910899, 50.9480224}} +$6 = {{x = 24.006224853920855, y = 72.621119847810419}, {x = 24.119692298829129, y = 51.890688643515688}, {x = 38.700154924642845, y = 44.614929583485953}} +(gdb) p q2 +$7 = {{x = 24.006224853920855, y = 72.621119847810419}, {x = 29.758671200376888, y = 31.764642512385173}, {x = 71.277052443896736, y = 42.309313461363033}} +</div> + +<div id="quad1"> +{{x = 34.879150914024962, y = 83.862726601601125}, {x = 35.095810134304429, y = 83.693473210169543}, {x = 35.359284111931586, y = 83.488069234177502}} +{{x = 54.503204203015471, y = 76.094098492518242}, {x = 51.366889541918894, y = 71.609856061299155}, {x = 46.53086955445437, y = 69.949863036494207}} +</div> + +<div id="cubic6"> +{{x = 54.080923997834752, y = 38.089631608729078}, {x = 10.447347774378651, y = 88.574043981998258}, {x = 33.294667831293616, y = 83.482240551841556}, {x = 25.649263209500006, y = 87.166762066617025}} +</div> + +<div id="quad2"> +{{x = 25.367434474345036, y = 50.4712103169743}, {x = 17.865013304933097, y = 37.356741010559439}, {x = 16.818988838905465, y = 37.682915484123129}} +{{x = 16.818988838905465, y = 37.682915484123129}, {x = 15.772964372877833, y = 38.009089957686811}, {x = 20.624104547604965, y = 41.825131596683121}} +</div> + +<div id="cubic7"> +{{x = 25.367434474345036, y = 50.4712103169743}, {x = 5.2367042308844178, y = 13.28800847441331}, {x = 21.031375239152169, y = 74.32364443052731}, {x = 60.821163496384933, y = 21.294883741668837}} +</div> + +<div id="quad3"> +{{x = 36.148792695174222, y = 70.336952793070424}, {x = 36.141613037691357, y = 70.711654739870085}, {x = 36.154708826402597, y = 71.088492662905836}} +{{x = 35.216235592661825, y = 70.580199617313212}, {x = 36.244476835123969, y = 71.010897787304074}, {x = 37.230244263238326, y = 71.423156953613102}} +</div> + +<div id="quad4"> +{{x = 369.84860200000003, y = 145.68026699999999}, {x = 382.36041299999999, y = 121.298294}, {x = 406.20770299999998, y = 121.298294}} +{{x = 369.850525, y = 145.67596399999999}, {x = 382.36291499999999, y = 121.29286999999999}, {x = 406.21127300000001, y = 121.29286999999999}} +</div> + +<div id="quad5"> +{{x = 67.25299631583178, y = 21.109080184767524}, {x = 43.617595267398613, y = 33.658034168577529}, {x = 33.38371819435676, y = 44.214192553988745}} +{{x = 40.476838859398541, y = 39.543209911285999}, {x = 36.701186108431131, y = 34.8817994016458}, {x = 30.102144288878023, y = 26.739063172945315}} +</div> + +<div id="quad6"> +{{x = 59.981867574297752, y = 19.243986850744687}, {x = 59.992798861020468, y = 19.257454808070786}, {x = 60.003741189575571, y = 19.270930807443623}} +{{x = 47.800898294803176, y = 89.697640756935641}, {x = 38.74069898238357, y = 58.416865487251982}, {x = 37.639862598936119, y = 44.208141075385868}} +</div> + +<div id="cubic8"> +{{x = 53.674595921148828, y = 8.9336467482771944}, {x = 48.248201817389678, y = 7.5279448682106773}, {x = 89.942031162763953, y = 55.717752573880254}, {x = 81.402728418541486, y = 35.656530426655216}} +{{x = 47.800898294803176, y = 89.697640756935641}, {x = 22.169400016856102, y = 1.1060833004797266}, {x = 48.267509205391399, y = 32.027215013293187}, {x = 79.306880794142785, y = 10.745507157754854}} +</div> + +<div id="quad7"> +{{x = 33.567436351153468, y = 62.336347586395924}, {x = 35.200980274619084, y = 65.038561460144479}, {x = 36.479571811084995, y = 67.632178905412445}} +{{x = 41.349524945572696, y = 67.886658677862641}, {x = 39.125562529359087, y = 67.429772735149214}, {x = 35.600314083992416, y = 66.705372160552685}} +</div> + +<div id="quad8"> +{{x = 36.148792695174222, y = 70.336952793070424}, {x = 36.141613037691357, y = 70.711654739870085}, {x = 36.154708826402597, y = 71.088492662905836}} +{{x = 35.216235592661825, y = 70.580199617313212}, {x = 36.244476835123969, y = 71.010897787304074}, {x = 37.230244263238326, y = 71.423156953613102}} +</div> + +<div id="quad9"> +{{353.2948,194.351074}, {353.2948,173.767563}, {364.167572,160.819855}}, +{{360.416077,166.795715}, {370.126831,147.872162}, {388.635406,147.872162}}, +</div> + +<div id="quad10"> + {{8, 8}, {10, 10}, {8, -10}}, + {{8, 8}, {12, 12}, {14, 4}}, +</div> + +<div id="quad11"> +{{x = 50.934805397717923, y = 51.52391952648901}, {x = 56.803308902971423, y = 44.246234610627596}, {x = 69.776888596721406, y = 40.166645096692555}} +{{x = 50.230212796400401, y = 38.386469101526998}, {x = 49.855620812184917, y = 38.818990392153609}, {x = 56.356567496227363, y = 47.229909093319407}} +</div> + +<div id="cubic9"> +{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945}, {18.5656052, 32.1268808}}, +{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981}, {56.4860195, 60.529264}}, +</div> + +<div id="cubic10"> +{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826}, {75.3863417, 18.24489}}, +{{61.3365082, 82.6931328}, {44.6393809, 54.0748258}, {16.8156155, 20.0497047}, {41.866885, 56.7355037}}, +</div> + +<div id="cubic11"> +{{40.3684631, 72.7588382}, {85.2198593, 90.174892}, {31.9101421, 13.7580149}, {72.0483425, 16.4930846}}, +{{57.7943379, 49.4368549}, {69.4103137, 79.1415428}, {30.9563231, 82.9221187}, {99.2731298, 83.4922981}}, +</div> + +<div id="cubic12"> +{{98.3415562, 26.5353662}, {15.3721551, 59.8107939}, {77.1895742, 25.1742572}, {11.7326863, 91.2589209}}, +{{79.899867, 77.0640431}, {40.0129651, 97.9042774}, {3.74105489, 75.9095456}, {88.6837571, 7.90615282}}, +</div> + +<div id="cubic13"> +{{95.6513419, 12.1029701}, {63.4801516, 10.9081754}, {41.0209588, 39.2537121}, {65.9441362, 23.0970739}}, +{{14.6179238, 83.4452002}, {33.7032426, 50.3981092}, {37.1399002, 10.3032037}, {92.5218685, 15.0431467}}, +</div> + +<div id="cubic14"> +{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826}, {75.3863417, 18.24489}}, +{{61.3365082, 82.6931328}, {44.6393809, 54.0748258}, {16.8156155, 20.0497047}, {41.866885, 56.7355037}}, +{{67.4265481,37.9937726}, {51.1295132,57.5422812}, {44.5947482,65.6442673}}, +{{44.5947482,65.6442673}, {35.2387481,77.3910511}, {43.2346162,66.2224493}}, +{{43.2346162,66.2224493}, {51.8234203,54.2750917}, {75.3863417,18.24489}}, +{{61.3365082,82.6931328}, {54.8250789,71.6639328}, {47.7274442,61.4049645}}, +{{47.7274442,61.4049645}, {40.6298095,51.1459962}, {35.9460478,45.2252785}}, +{{35.9460478,45.2252785}, {31.2622861,39.3045608}, {31.9924758,41.2901124}}, +{{31.9924758,41.2901124}, {32.7226655,43.275664}, {41.866885,56.7355037}}, +</div> + +<div id="quad12"> +{{x = 67.426548091427676, y = 37.993772624988935}, {x = 51.129513170665042, y = 57.542281234563646}, {x = 44.594748190899182, y = 65.644267382683879}} +{{x = 61.336508189019057, y = 82.693132843213675}, {x = 54.825078921449354, y = 71.663932799212432}, {x = 47.727444217558926, y = 61.4049645128392}} +</div> + +<div id="quad13"> +{{x = 53.774852327053594, y = 53.318060789841951}, {x = 45.787877803416805, y = 51.393492026284981}, {x = 46.703936967162392, y = 53.06860709822206}} +{{x = 46.703936967162392, y = 53.06860709822206}, {x = 47.619996130907957, y = 54.74372217015916}, {x = 53.020051653535361, y = 48.633140968832024}} +</div> + +<div id="cubic15"> +{{40.3684631, 72.7588382}, {85.2198593, 90.174892}, {31.9101421, 13.7580149}, {72.0483425, 16.4930846}}, +{{57.7943379, 49.4368549}, {69.4103137, 79.1415428}, {30.9563231, 82.9221187}, {99.2731298, 83.4922981}}, +</div> + +<div id="cubic16"> +{{98.3415562, 26.5353662}, {15.3721551, 59.8107939}, {77.1895742, 25.1742572}, {11.7326863, 91.2589209}}, +{{79.899867, 77.0640431}, {40.0129651, 97.9042774}, {3.74105489, 75.9095456}, {88.6837571, 7.90615282}}, +</div> + +<div id="cubic17"> +{{95.6513419, 12.1029701}, {63.4801516, 10.9081754}, {41.0209588, 39.2537121}, {65.9441362, 23.0970739}}, +{{14.6179238, 83.4452002}, {33.7032426, 50.3981092}, {37.1399002, 10.3032037}, {92.5218685, 15.0431467}}, +{{95.6513419,12.1029701}, {79.216947,12.1911515}, {68.1126831,18.0126375}}, +{{68.1126831,18.0126375}, {57.0084192,23.8341235}, {55.4198832,27.1619689}}, +{{55.4198832,27.1619689}, {53.8313472,30.4898143}, {65.9441362,23.0970739}}, +{{14.6179238,83.4452002}, {20.3825754,73.0912112}, {25.0377248,62.5209893}}, +{{25.0377248,62.5209893}, {33.2090045,41.6303758}, {46.9147771,27.3313746}}, +{{46.9147771,27.3313746}, {60.6205496,13.0323735}, {92.5218685,15.0431467}}, +</div> + +<div id="cubic18"> +{{55.7513494, 12.929877}, {46.4296358, 42.8887602}, {16.8160022, 26.5487217}, {4.93643419, 66.6494508}}, +{{12.4426199, 23.1121812}, {31.3921366, 7.64067448}, {4.36561578, 72.9044408}, {77.3190123, 0.63959742}}, + +{{55.7513494,12.929877}, {52.399261,23.0070161}, {46.4958203,27.5595279}}, +{{46.4958203,27.5595279}, {40.5923795,32.1120397}, {33.5495747,34.9548738}}, +{{33.5495747,34.9548738}, {25.3214643,38.1279717}, {17.6150117,44.5570525}}, +{{17.6150117,44.5570525}, {9.90855921,50.9861334}, {4.93643419,66.6494508}}, + +{{12.4426199,23.1121812}, {17.0040168,19.5021098}, {18.7553606,21.0894159}}, +{{18.7553606,21.0894159}, {20.5067044,22.676722}, {21.4650431,26.4450934}}, +{{21.4650431,26.4450934}, {22.5692754,31.7464864}, {26.4671516,34.648351}}, +{{26.4671516,34.648351}, {30.3650278,37.5502156}, {41.873704,30.8489321}}, +{{41.873704,30.8489321}, {53.3823801,24.1476487}, {77.3190123,0.63959742}}, +</div> + +</div> + +<script type="text/javascript"> + +var testDivs = [ + cubic18, + cubic17, + cubic16, + cubic15, + quad13, + quad12, + cubic14, + cubic13, + cubic12, + cubic11, + cubic10, + cubic9, + quad11, + quad10, + quad9, + quad8, + quad7, + cubic8, + quad6, + quad5, + quad4, + quad3, + cubic7, + quad2, + cubic6, + quad1, + cubic5, + cubic4, + cubic1x0, + cubic1x0x, + cubic1x1, + cubic1x1x, + cubic1x2, + cubic1x2x, + cubic1x3, + cubic1x3x, + cubic1x4, + cubic1x4x, + cubic1x5, + cubic1x5x, + cubic1x6, + cubic1x6x, + cubic1x7, + cubic1x7x, + cubic1x8, + cubic1x8x, + cubic1x9, + cubic1x9x, + cubic2x0, + cubic2x0x, + cubic2x1, + cubic2x1x, + cubic2x2, + cubic2x2x, + cubic2x3, + cubic2x3x, + cubic2x4, + cubic2x4x, + cubic2x5, + cubic2x5x, + cubic2x6, + cubic2x6x, + cubic2x7, + cubic2x7x, + cubic2x8, + cubic2x8x, + cubic2x9, + cubic2x9x, + cubic3x0, + cubic3x0x, + cubic3x1, + cubic3x1x, + cubic3x2, + cubic3x2x, + cubic3x3, + cubic3x3x, + cubic3x4, + cubic3x4x, + cubic3x5, + cubic3x5x, + cubic3x6, + cubic3x6x, + cubic3x7, + cubic3x7x, + cubic3x8, + cubic3x8x, + cubic3x9, + cubic3x9x, + cubic4x0, + cubic4x0x, + cubic4x1, + cubic4x1x, + cubic4x2, + cubic4x2x, + cubic4x3, + cubic4x3x, + cubic4x4, + cubic4x4x, + cubic4x5, + cubic4x5x, + cubic4x6, + cubic4x6x, + cubic4x7, + cubic4x7x, + cubic4x8, + cubic4x8x, + cubic4x9, + cubic4x9x, + cubic5x0, + cubic5x0x, + cubic5x1, + cubic5x1x, + cubic5x2, + cubic5x2x, + cubic5x3, + cubic5x3x, + cubic5x4, + cubic5x4x, + cubic5x5, + cubic5x5x, + cubic5x6, + cubic5x6x, + cubic5x7, + cubic5x7x, + cubic5x8, + cubic5x8x, + cubic5x9, + cubic5x9x, + cubic6x0, + cubic6x0x, + cubic6x1, + cubic6x1x, + cubic6x2, + cubic6x2x, + cubic6x3, + cubic6x3x, + cubic6x4, + cubic6x4x, + cubic6x5, + cubic6x5x, + cubic6x6, + cubic6x6x, + cubic6x7, + cubic6x7x, + cubic6x8, + cubic6x8x, + cubic6x9, + cubic6x9x, + cubic7x0, + cubic7x0x, + cubic7x1, + cubic7x1x, + cubic7x2, + cubic7x2x, + cubic7x3, + cubic7x3x, + cubic7x4, + cubic7x4x, + cubic7x5, + cubic7x5x, + cubic7x6, + cubic7x6x, + cubic7x7, + cubic7x7x, + cubic7x8, + cubic7x8x, + cubic7x9, + cubic7x9x, + cubic8x0, + cubic8x0x, + cubic8x1, + cubic8x1x, + cubic8x2, + cubic8x2x, + cubic8x3, + cubic8x3x, + cubic8x4, + cubic8x4x, + cubic8x5, + cubic8x5x, + cubic8x6, + cubic8x6x, + cubic8x7, + cubic8x7x, + cubic8x8, + cubic8x8x, + cubic8x9, + cubic8x9x, + cubic3, + cubic2, + cubic1, +]; + +var scale, columns, rows, xStart, yStart; + +var ticks = 10; +var at_x = 13 + 0.5; +var at_y = 23 + 0.5; +var init_decimal_places = 1; // make this 3 to show more precision +var decimal_places; +var tests = []; +var testTitles = []; +var testIndex = 0; +var ctx; +var minScale = 1; +var subscale = 1; +var curveT = -1; +var drawCubics = true; +var drawQuads = true; +var drawControlLines = true; + +function parse(test, title) { + var curveStrs = test.split("{{"); + if (curveStrs.length == 1) + curveStrs = test.split("=("); + var pattern = /[a-z$=]?-?\d+\.*\d*/g; + var curves = []; + for (var c in curveStrs) { + var curveStr = curveStrs[c]; + var points = curveStr.match(pattern); + var pts = []; + for (var wd in points) { + var num = parseFloat(points[wd]); + if (isNaN(num)) continue; + pts.push(num); + } + if (pts.length > 2) + curves.push(pts); + } + if (curves.length >= 1) { + tests.push(curves); + testTitles.push(title); + } +} + +function init(test) { + var canvas = document.getElementById('canvas'); + if (!canvas.getContext) return; + canvas.width = window.innerWidth - at_x; + canvas.height = window.innerHeight - at_y; + ctx = canvas.getContext('2d'); + var xmin = Infinity; + var xmax = -Infinity; + var ymin = Infinity; + var ymax = -Infinity; + for (var curves in test) { + var curve = test[curves]; + var last = curve.length; + for (var idx = 0; idx < last; idx += 2) { + xmin = Math.min(xmin, curve[idx]); + xmax = Math.max(xmax, curve[idx]); + ymin = Math.min(ymin, curve[idx + 1]); + ymax = Math.max(ymax, curve[idx + 1]); + } + } + var testW = xmax - xmin; + var testH = ymax - ymin; + subscale = 1; + while (testW * subscale < 0.1 && testH * subscale < 0.1) { + subscale *= 10; + } + while (testW * subscale > 10 && testH * subscale > 10) { + subscale /= 10; + } + xStart = Math.floor(xmin * subscale) / subscale; + yStart = Math.floor(ymin * subscale) / subscale; + var xEnd = Math.ceil(xmin * subscale) / subscale; + var yEnd = Math.ceil(ymin * subscale) / subscale; + var cCelsW = Math.floor(ctx.canvas.width / 10); + var cCelsH = Math.floor(ctx.canvas.height / 10); + testW = xEnd - xStart; + testH = yEnd - yStart; + var scaleWH = 1; + while (cCelsW > testW * scaleWH * 10 && cCelsH > testH * scaleWH * 10) { + scaleWH *= 10; + } + while (cCelsW * 10 < testW * scaleWH && cCelsH * 10 < testH * scaleWH) { + scaleWH /= 10; + } + + columns = Math.ceil(xmax * subscale) - Math.floor(xmin * subscale) + 1; + rows = Math.ceil(ymax * subscale) - Math.floor(ymin * subscale) + 1; + + var hscale = ctx.canvas.width / columns / ticks; + var vscale = ctx.canvas.height / rows / ticks; + minScale = Math.floor(Math.min(hscale, vscale)); + scale = minScale * subscale; +} + +function drawPoint(px, py, xoffset, yoffset, unit) { + var label = px.toFixed(decimal_places) + ", " + py.toFixed(decimal_places); + var _px = px * unit + xoffset; + var _py = py * unit + yoffset; + ctx.beginPath(); + ctx.arc(_px, _py, 3, 0, Math.PI*2, true); + ctx.closePath(); + ctx.fill(); + ctx.fillText(label, _px + 5, _py); +} + +function draw(test, title, scale) { + ctx.fillStyle = "rgba(0,0,0, 0.1)"; + ctx.font = "normal 50px Arial"; + ctx.fillText(title, 50, 50); + ctx.font = "normal 10px Arial"; + + var unit = scale * ticks; + ctx.lineWidth = 1; + var i; + for (i = 0; i <= rows * ticks; ++i) { + ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black"; + ctx.beginPath(); + ctx.moveTo(at_x + 0, at_y + i * minScale); + ctx.lineTo(at_x + ticks * columns * minScale, at_y + i * minScale); + ctx.stroke(); + } + for (i = 0; i <= columns * ticks; ++i) { + ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black"; + ctx.beginPath(); + ctx.moveTo(at_x + i * minScale, at_y + 0); + ctx.lineTo(at_x + i * minScale, at_y + ticks * rows * minScale); + ctx.stroke(); + } + + var xoffset = xStart * -unit + at_x; + var yoffset = yStart * -unit + at_y; + + ctx.fillStyle = "rgb(40,80,60)" + for (i = 0; i <= columns; i += 1) + { + num = xStart + i / subscale; + ctx.fillText(num.toFixed(decimal_places), xoffset + num * unit - 5, 10); + } + for (i = 0; i <= rows; i += 1) + { + num = yStart + i / subscale; + ctx.fillText(num.toFixed(decimal_places), 0, yoffset + num * unit + 0); + } + var curves, pts; + for (curves in test) { + var curve = test[curves]; + if (curve.length == 6 && !drawQuads) { + continue; + } + if (curve.length == 8 && !drawCubics) { + continue; + } + ctx.beginPath(); + ctx.moveTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit); + switch (curve.length) { + case 6: + ctx.quadraticCurveTo( + xoffset + curve[2] * unit, yoffset + curve[3] * unit, + xoffset + curve[4] * unit, yoffset + curve[5] * unit); + break; + case 8: + ctx.bezierCurveTo( + xoffset + curve[2] * unit, yoffset + curve[3] * unit, + xoffset + curve[4] * unit, yoffset + curve[5] * unit, + xoffset + curve[6] * unit, yoffset + curve[7] * unit); + break; + } + if (curves == 2) ctx.strokeStyle = curves ? "red" : "blue"; + ctx.stroke(); + if (drawControlLines) { + ctx.strokeStyle = "rgba(0,0,0, 0.3)"; + ctx.beginPath(); + ctx.moveTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit); + ctx.lineTo(xoffset + curve[2] * unit, yoffset + curve[3] * unit); + ctx.lineTo(xoffset + curve[4] * unit, yoffset + curve[5] * unit); + if (curve.length == 8) + ctx.lineTo(xoffset + curve[6] * unit, yoffset + curve[7] * unit); + ctx.stroke(); + } + if (curveT >= 0 && curveT <= 1) { + var x, y; + var t = curveT; + switch (curve.length) { + case 6: + var one_t = 1 - t; + var a = one_t * one_t; + var b = 2 * one_t * t; + var c = t * t; + x = a * curve[0] + b * curve[2] + c * curve[4]; + y = a * curve[1] + b * curve[3] + c * curve[5]; + break; + case 8: + var one_t = 1 - t; + var one_t2 = one_t * one_t; + var a = one_t2 * one_t; + var b = 3 * one_t2 * t; + var t2 = t * t; + var c = 3 * one_t * t2; + var d = t2 * t; + x = a * curve[0] + b * curve[2] + c * curve[4] + d * curve[6]; + y = a * curve[1] + b * curve[3] + c * curve[5] + d * curve[7]; + break; + } + drawPoint(x, y, xoffset, yoffset, unit); + var num = curveT.toFixed(3); + ctx.beginPath(); + ctx.rect(200,10,200,10); + ctx.fillStyle="white"; + ctx.fill(); + ctx.fillStyle="black"; + ctx.fillText(num, 230, 18); + if (curve.length == 8) { + var one_t = 1 - t; + var a = curve[0]; + var b = curve[2]; + var c = curve[4]; + var d = curve[6]; + var dx = (b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t; + a = curve[1]; + b = curve[3]; + c = curve[5]; + d = curve[7]; + var dy = (b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t; + ctx.beginPath(); + ctx.moveTo(xoffset + (x - dx) * unit, yoffset + (y - dy) * unit); + ctx.lineTo(xoffset + (x + dx) * unit, yoffset + (y + dy) * unit); + ctx.stroke(); + } + } + } +} + +function drawTop() { + init(tests[testIndex]); + redraw(); +} + +function redraw() { + ctx.beginPath(); + ctx.rect(0, 0, ctx.canvas.width, ctx.canvas.height); + ctx.fillStyle="white"; + ctx.fill(); + draw(tests[testIndex], testTitles[testIndex], scale); +} + +function doKeyPress(evt) { + var char = String.fromCharCode(evt.charCode); + switch (char) { + case 'c': + drawCubics ^= true; + redraw(); + break; + case 'l': + drawControlLines ^= true; + redraw(); + break; + case 'N': + testIndex += 9; + case 'n': + if (++testIndex >= tests.length) + testIndex = 0; + mouseX = Infinity; + drawTop(); + break; + case 'P': + testIndex -= 9; + case 'p': + if (--testIndex < 0) + testIndex = tests.length - 1; + mouseX = Infinity; + drawTop(); + break; + case 'q': + drawQuads ^= true; + redraw(); + break; + case 'x': + drawCubics ^= true; + drawQuads ^= true; + redraw(); + break; + } +} + +function handleMouseClick() { + var e = window.event; + var tgt = e.target || e.srcElement; + var min = tgt.offsetTop + Math.ceil(at_y); + var max = min + ticks * rows * minScale; + curveT = (e.clientY - min) / (max - min); + redraw(); +} + +function calcXY() { + var e = window.event; + var tgt = e.target || e.srcElement; + var left = tgt.offsetLeft; + var top = tgt.offsetTop; + var unit = scale * ticks; + mouseX = (e.clientX - left - Math.ceil(at_x) + 1) / unit + xStart; + mouseY = (e.clientY - top - Math.ceil(at_y)) / unit + yStart; +} + +function handleMouseOver() { + calcXY(); + var num = mouseX.toFixed(3) + ", " + mouseY.toFixed(3); + ctx.beginPath(); + ctx.rect(30,10,200,10); + ctx.fillStyle="white"; + ctx.fill(); + ctx.fillStyle="black"; + ctx.fillText(num, 30, 18); +} + +function start() { + for (i = 0; i < testDivs.length; ++i) { + var title = testDivs[i].id.toString(); + var str = testDivs[i].firstChild.data; + parse(str, title); + } + drawTop(); + window.addEventListener('keypress', doKeyPress, true); + window.onresize = function() { + drawTop(); + } +} + +</script> +</head> + +<body onLoad="start();"> +<canvas id="canvas" width="750" height="500" + onmousemove="handleMouseOver()" + onclick="handleMouseClick()" + ></canvas > +</body> +</html> |