Skip to content

Commit bfce5d5

Browse files
2735979427359794
committed
Refactor isLeft out of clip-extent into trigonometry
1 parent e4af090 commit bfce5d5

5 files changed

Lines changed: 49 additions & 42 deletions

File tree

‎d3.js‎

Lines changed: 21 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1176,6 +1176,12 @@ d3 = function() {
11761176
function d3_sgn(x) {
11771177
return x > 0 ? 1 : x < 0 ? -1 : 0;
11781178
}
1179+
function d3_isCCWTurn(a, b, c) {
1180+
return d3_cross2d(a, b, c) > 0;
1181+
}
1182+
function d3_cross2d(o, a, b) {
1183+
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
1184+
}
11791185
function d3_acos(x) {
11801186
return x > 1 ? 0 : x < -1 ? π : Math.acos(x);
11811187
}
@@ -3114,18 +3120,15 @@ d3 = function() {
31143120
for (var j = 1, v = polygon[i], m = v.length, a = v[0], b; j < m; ++j) {
31153121
b = v[j];
31163122
if (a[1] <= y) {
3117-
if (b[1] > y && isLeft(a, b, p) > 0) ++wn;
3123+
if (b[1] > y && d3_isCCWTurn(a, b, p)) ++wn;
31183124
} else {
3119-
if (b[1] <= y && isLeft(a, b, p) < 0) --wn;
3125+
if (b[1] <= y && !d3_isCCWTurn(a, b, p)) --wn;
31203126
}
31213127
a = b;
31223128
}
31233129
}
31243130
return wn !== 0;
31253131
}
3126-
function isLeft(a, b, c) {
3127-
return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]);
3128-
}
31293132
function interpolate(from, to, direction, listener) {
31303133
var a = 0, a1 = 0;
31313134
if (from == null || (a = corner(from, direction)) !== (a1 = corner(to, direction)) || comparePoints(from, to) < 0 ^ direction > 0) {
@@ -4187,20 +4190,17 @@ d3 = function() {
41874190
if (arguments.length) return hull(vertices);
41884191
function hull(data) {
41894192
if (data.length < 3) return [];
4190-
var fx = d3_functor(x), fy = d3_functor(y), n = data.length, points = [], flipped_points = [];
4191-
for (var i = 0; i < n; i++) {
4193+
var fx = d3_functor(x), fy = d3_functor(y), i, n = data.length, points = [], flippedPoints = [];
4194+
for (i = 0; i < n; i++) {
41924195
points.push([ +fx.call(this, data[i], i), +fy.call(this, data[i], i), i ]);
41934196
}
4194-
points.sort(function(a, b) {
4195-
return a[0] - b[0] || a[1] - b[1];
4196-
});
4197-
for (var i = 0; i < n; i++) flipped_points.push([ points[i][0], -points[i][1] ]);
4198-
var uhull = d3_geom_hull_find_upper_hull(points);
4199-
var lhull = d3_geom_hull_find_upper_hull(flipped_points);
4200-
var skip_l = lhull[0] === uhull[0], skip_r = lhull[lhull.length - 1] === uhull[uhull.length - 1], poly = [];
4201-
for (var i = uhull.length - 1; i >= 0; i--) poly.push(data[points[uhull[i]][2]]);
4202-
for (var i = +skip_l; i < lhull.length - skip_r; i++) poly.push(data[points[lhull[i]][2]]);
4203-
return poly;
4197+
points.sort(d3_geom_hullOrder);
4198+
for (i = 0; i < n; i++) flippedPoints.push([ points[i][0], -points[i][1] ]);
4199+
var upper = d3_geom_hullUpper(points), lower = d3_geom_hullUpper(flippedPoints);
4200+
var skipLeft = lower[0] === upper[0], skipRight = lower[lower.length - 1] === upper[upper.length - 1], polygon = [];
4201+
for (i = upper.length - 1; i >= 0; --i) polygon.push(data[points[upper[i]][2]]);
4202+
for (i = +skipLeft; i < lower.length - skipRight; ++i) polygon.push(data[points[lower[i]][2]]);
4203+
return polygon;
42044204
}
42054205
hull.x = function(_) {
42064206
return arguments.length ? (x = _, hull) : x;
@@ -4210,18 +4210,18 @@ d3 = function() {
42104210
};
42114211
return hull;
42124212
};
4213-
function d3_geom_hull_find_upper_hull(points) {
4213+
function d3_geom_hullUpper(points) {
42144214
var n = points.length, hull = [ 0, 1 ], hs = 2;
42154215
for (var i = 2; i < n; i++) {
4216-
while (hs > 1 && !d3_geom_hull_CW(points[hull[hs - 2]], points[hull[hs - 1]], points[i])) {
4216+
while (hs > 1 && d3_isCCWTurn(points[hull[hs - 2]], points[hull[hs - 1]], points[i])) {
42174217
hs--;
42184218
}
42194219
hull[hs++] = i;
42204220
}
42214221
return hull.slice(0, hs);
42224222
}
4223-
function d3_geom_hull_CW(a, b, c) {
4224-
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]) > 0;
4223+
function d3_geom_hullOrder(a, b) {
4224+
return a[0] - b[0] || a[1] - b[1];
42254225
}
42264226
d3.geom.polygon = function(coordinates) {
42274227
d3_subclass(coordinates, d3_geom_polygonPrototype);

‎d3.min.js‎

Lines changed: 5 additions & 5 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/geo/clip-extent.js‎

Lines changed: 2 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -79,20 +79,16 @@ function d3_geo_clipExtent(x0, y0, x1, y1) {
7979
for (var j = 1, v = polygon[i], m = v.length, a = v[0], b; j < m; ++j) {
8080
b = v[j];
8181
if (a[1] <= y) {
82-
if (b[1] > y && isLeft(a, b, p) > 0) ++wn;
82+
if (b[1] > y && d3_isCCWTurn(a, b, p)) ++wn;
8383
} else {
84-
if (b[1] <= y && isLeft(a, b, p) < 0) --wn;
84+
if (b[1] <= y && !d3_isCCWTurn(a, b, p)) --wn;
8585
}
8686
a = b;
8787
}
8888
}
8989
return wn !== 0;
9090
}
9191

92-
function isLeft(a, b, c) {
93-
return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]);
94-
}
95-
9692
function interpolate(from, to, direction, listener) {
9793
var a = 0, a1 = 0;
9894
if (from == null ||

‎src/geom/hull.js‎

Lines changed: 5 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
import "../core/functor";
2+
import "../math/trigonometry";
23
import "geom";
34
import "point";
45

@@ -10,8 +11,8 @@ import "point";
1011
* The runtime of this algorithm is O(n log n), where n is the number of input
1112
* points. However in practice it outperforms other O(n log n) hulls.
1213
*
13-
* @param vertices [[x1, y1], [x2, y2], …]
14-
* @returns polygon [[x1, y1], [x2, y2], …]
14+
* @param vertices [[x1, y1], [x2, y2], ...]
15+
* @returns polygon [[x1, y1], [x2, y2], ...]
1516
*/
1617
d3.geom.hull = function(vertices) {
1718
var x = d3_geom_pointX,
@@ -45,7 +46,7 @@ d3.geom.hull = function(vertices) {
4546

4647
// construct the polygon, removing possible duplicate endpoints
4748
var skipLeft = lower[0] === upper[0],
48-
skipRight = lower[lower.length - 1] === upper[upper.length - 1]),
49+
skipRight = lower[lower.length - 1] === upper[upper.length - 1],
4950
polygon = [];
5051

5152
for (i = upper.length - 1; i >= 0; --i)
@@ -76,7 +77,7 @@ function d3_geom_hullUpper(points) {
7677
hs = 2; // hull size
7778

7879
for (var i = 2; i < n; i++) {
79-
while (hs > 1 && !d3_geom_hull_CW(points[hull[hs-2]], points[hull[hs-1]], points[i])) {
80+
while (hs > 1 && !d3_isCCWTurn(points[hull[hs-2]], points[hull[hs-1]], points[i])) {
8081
hs --;
8182
}
8283
hull[hs++] = i;
@@ -85,11 +86,5 @@ function d3_geom_hullUpper(points) {
8586
return hull.slice(0, hs);
8687
}
8788

88-
// are three points a, b, c in clockwise order?
89-
// i.e. is the sign of (b-a)x(c-a) positive?
90-
function d3_geom_hull_CW(a, b, c) {
91-
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]) > 0;
92-
}
93-
9489
// comparator for ascending sort by x-coord first, y-coord second
9590
function d3_geom_hullOrder(a, b) { return a[0] - b[0] || a[1] - b[1]; }

‎src/math/trigonometry.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,22 @@ function d3_sgn(x) {
1010
return x > 0 ? 1 : x < 0 ? -1 : 0;
1111
}
1212

13+
// returns true iff the [x,y] points a, b, c form a counter-clockwise turn in
14+
// the traditional Cartesian coordinate system (i.e. x value grows from left
15+
// to right, y value grows from bottom to top)
16+
function d3_isCCWTurn(a, b, c) {
17+
return d3_cross2d(a, b, c) > 0;
18+
}
19+
20+
// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross
21+
// product, in traditional Cartesian coordinate system (x value grows from
22+
// left to right, y value grows from bottom to top). Returns a positive value
23+
// if OAB makes a counter-clockwise turn, negative for clockwise turn, and
24+
// zero if the points are collinear.
25+
function d3_cross2d(o, a, b) {
26+
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
27+
}
28+
1329
function d3_acos(x) {
1430
return x > 1 ? 0 : x < -1 ? π : Math.acos(x);
1531
}

0 commit comments

Comments
 (0)