Skip to content

Commit caa5023

Browse files
lehnilehni
committed
Simplify winding algorithm by reusing orientation check.
1 parent 7c4518e commit caa5023

1 file changed

Lines changed: 48 additions & 37 deletions

File tree

‎src/path/Curve.js‎

Lines changed: 48 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -689,15 +689,19 @@ statics: {
689689
},
690690

691691
_getWinding: function(v, x, y, roots1, roots2) {
692-
var tolerance = /*#=*/ Numerical.TOLERANCE,
693-
abs = Math.abs;
694-
695692
// Implementation of the crossing number algorithm:
696693
// http://en.wikipedia.org/wiki/Point_in_polygon
697694
// Solve the y-axis cubic polynomial for y and count all solutions
698695
// to the right of x as crossings.
699-
if (Curve.isLinear(v)) {
700-
// Special case for handling lines.
696+
var tolerance = /*#=*/ Numerical.TOLERANCE,
697+
abs = Math.abs;
698+
699+
// Looks at the curve's start and end y coordinates to determine
700+
// orientation. This only makes sense for curves with clear orientation,
701+
// which is why we need to split them at y extrema, see below.
702+
// Returns 0 if the curve is outside the boundaries and is not to be
703+
// considered.
704+
function getOrientation(v) {
701705
var y0 = v[1],
702706
y1 = v[7],
703707
dir = 1;
@@ -708,7 +712,15 @@ statics: {
708712
dir = -1;
709713
}
710714
if (y < y0 || y > y1)
711-
return 0;
715+
dir = 0;
716+
return dir;
717+
}
718+
719+
if (Curve.isLinear(v)) {
720+
// Special simplified case for handling lines.
721+
var dir = getOrientation(v);
722+
if (!dir)
723+
return 0;
712724
var cross = (v[6] - v[0]) * (y - v[1]) - (v[7] - v[1]) * (x - v[0]);
713725
return (cross < -tolerance ? -1 : 1) == dir ? 0 : dir;
714726
}
@@ -719,18 +731,18 @@ statics: {
719731
y1 = v[3],
720732
y2 = v[5],
721733
y3 = v[7];
722-
// Split the curve at Y extremas, to get mono bezier curves
734+
// Split the curve at y extrema, to get bezier curves with clear
735+
// orientation: Calculate the derivative and find its roots.
723736
var a = 3 * (y1 - y2) - y0 + y3,
724737
b = 2 * (y0 + y2) - 4 * y1,
725-
c = y1 - y0,
726-
// Keep then range to 0 .. 1 (excluding) in the search for y extrema
727-
count = Numerical.solveQuadratic(a, b, c, roots1, tolerance,
728-
1 - tolerance);
729-
730-
var winding = 0,
731-
left,
732-
right = v;
733-
var t1 = roots1[0];
738+
c = y1 - y0;
739+
// Keep then range to 0 .. 1 (excluding) in the search for y extrema
740+
var count = Numerical.solveQuadratic(a, b, c, roots1, tolerance,
741+
1 - tolerance),
742+
left, // The part of the curve that's chopped off.
743+
right = v, // The part that's left to be chopped.
744+
t1 = roots1[0], // The first root
745+
winding = 0;
734746
for (var i = 0; i <= count; i++) {
735747
if (i === count) {
736748
left = right;
@@ -749,36 +761,32 @@ statics: {
749761
left[3] = left[1]; // curve2.handle1.y = curve2.point1.y;
750762
if (i < count)
751763
left[5] = right[1]; // curve1.handle2.y = curve2.point1.y;
752-
var dir = 1;
753-
if (left[1] > left[7]) {
754-
left = [
755-
left[6], left[7],
756-
left[4], left[5],
757-
left[2], left[3],
758-
left[0], left[1]
759-
];
760-
dir = -1;
761-
}
762-
if (y < left[1] || y > left[7])
764+
var dir = getOrientation(left);
765+
if (!dir)
763766
continue;
764767
// Adjust start and end range depending on if curve was flipped.
765768
// In normal orientation we exclude the end point since it's also
766769
// the start point of the next curve. If flipped, we have to exclude
767770
// the end point instead.
768-
var min = -tolerance * dir,
769-
t2,
771+
var t2,
770772
px;
771-
if (Curve.solveCubic(left, 1, y, roots2, min, 1 + min) === 1) {
773+
// Since we've split at y extrema, there can only be 0, 1, or
774+
// infinite solutions now.
775+
if (Curve.solveCubic(left, 1, y, roots2, -tolerance, 1 + -tolerance)
776+
=== 1) {
772777
t2 = roots2[0];
773778
px = Curve.evaluate(left, t2, 0).x;
774779
} else {
775780
var mid = (left[1] + left[7]) / 2;
776-
px = y < mid ? left[0] : left[6];
777-
t2 = y < mid ? 0 : 1;
778-
// Filter out end points based on direction.
779-
if (dir < 0 && abs(t2) < tolerance && y == left[1] ||
780-
dir > 0 && abs(t2 - 1) < tolerance && y == left[7])
781+
// Pick t2 based on the direction of the curve. If y < mid,
782+
// choose the beginning (which is the end of a curve with
783+
// negative orientation, as we're not actually flipping curves).
784+
t2 = y < mid && dir > 0 ? 0 : 1;
785+
// Filter out the end point, as it'll be the start point of the
786+
// next curve.
787+
if (t2 === 1 && y == left[7])
781788
continue;
789+
px = t2 === 0 ? left[0] : left[6];
782790
}
783791
// See if we're touching a horizontal stationary point by looking at
784792
// the tanget's y coordinate.
@@ -797,8 +805,11 @@ statics: {
797805
|| abs(t2 - 1) < tolerance && x != left[6]))
798806
continue;
799807
// If this is a horizontal stationary point, and we're at the
800-
// end of the curve, flip the orientation of dir.
801-
winding += flat && abs(t2 - 1) < tolerance ? -dir : dir;
808+
// end of the curve (or at the beginning of a curve with
809+
// negative direction, as we're not actually flipping them),
810+
// flip dir, as the curve is about to change orientation.
811+
winding += flat && abs(t2 - (dir > 0 ? 1 : 0)) < tolerance
812+
? -dir : dir;
802813
}
803814
}
804815
return winding;

0 commit comments

Comments
 (0)