Skip to content

Commit d0a047a

Browse files
mbostockmbostock
committed
Merge branch 'better-hull2' of https://github.com/DanGoldbach/d3 into 3.4
2 parents aee1214 + 19789b6 commit d0a047a

6 files changed

Lines changed: 135 additions & 175 deletions

File tree

‎d3.js‎

Lines changed: 31 additions & 76 deletions
Original file line numberDiff line numberDiff line change
@@ -1179,6 +1179,12 @@ d3 = function() {
11791179
function d3_sgn(x) {
11801180
return x > 0 ? 1 : x < 0 ? -1 : 0;
11811181
}
1182+
function d3_isCCWTurn(a, b, c) {
1183+
return d3_cross2d(a, b, c) > 0;
1184+
}
1185+
function d3_cross2d(o, a, b) {
1186+
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
1187+
}
11821188
function d3_acos(x) {
11831189
return x > 1 ? 0 : x < -1 ? π : Math.acos(x);
11841190
}
@@ -3117,18 +3123,15 @@ d3 = function() {
31173123
for (var j = 1, v = polygon[i], m = v.length, a = v[0], b; j < m; ++j) {
31183124
b = v[j];
31193125
if (a[1] <= y) {
3120-
if (b[1] > y && isLeft(a, b, p) > 0) ++wn;
3126+
if (b[1] > y && d3_isCCWTurn(a, b, p)) ++wn;
31213127
} else {
3122-
if (b[1] <= y && isLeft(a, b, p) < 0) --wn;
3128+
if (b[1] <= y && !d3_isCCWTurn(a, b, p)) --wn;
31233129
}
31243130
a = b;
31253131
}
31263132
}
31273133
return wn !== 0;
31283134
}
3129-
function isLeft(a, b, c) {
3130-
return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]);
3131-
}
31323135
function interpolate(from, to, direction, listener) {
31333136
var a = 0, a1 = 0;
31343137
if (from == null || (a = corner(from, direction)) !== (a1 = corner(to, direction)) || comparePoints(from, to) < 0 ^ direction > 0) {
@@ -4197,65 +4200,17 @@ d3 = function() {
41974200
if (arguments.length) return hull(vertices);
41984201
function hull(data) {
41994202
if (data.length < 3) return [];
4200-
var fx = d3_functor(x), fy = d3_functor(y), n = data.length, vertices, plen = n - 1, points = [], stack = [], d, i, j, h = 0, x1, y1, x2, y2, u, v, a, sp;
4201-
if (fx === d3_geom_pointX && y === d3_geom_pointY) vertices = data; else for (i = 0,
4202-
vertices = []; i < n; ++i) {
4203-
vertices.push([ +fx.call(this, d = data[i], i), +fy.call(this, d, i) ]);
4204-
}
4205-
for (i = 1; i < n; ++i) {
4206-
if (vertices[i][1] < vertices[h][1] || vertices[i][1] == vertices[h][1] && vertices[i][0] < vertices[h][0]) h = i;
4207-
}
4208-
for (i = 0; i < n; ++i) {
4209-
if (i === h) continue;
4210-
y1 = vertices[i][1] - vertices[h][1];
4211-
x1 = vertices[i][0] - vertices[h][0];
4212-
points.push({
4213-
angle: Math.atan2(y1, x1),
4214-
index: i
4215-
});
4216-
}
4217-
points.sort(function(a, b) {
4218-
return a.angle - b.angle;
4219-
});
4220-
a = points[0].angle;
4221-
v = points[0].index;
4222-
u = 0;
4223-
for (i = 1; i < plen; ++i) {
4224-
j = points[i].index;
4225-
if (a == points[i].angle) {
4226-
x1 = vertices[v][0] - vertices[h][0];
4227-
y1 = vertices[v][1] - vertices[h][1];
4228-
x2 = vertices[j][0] - vertices[h][0];
4229-
y2 = vertices[j][1] - vertices[h][1];
4230-
if (x1 * x1 + y1 * y1 >= x2 * x2 + y2 * y2) {
4231-
points[i].index = -1;
4232-
continue;
4233-
} else {
4234-
points[u].index = -1;
4235-
}
4236-
}
4237-
a = points[i].angle;
4238-
u = i;
4239-
v = j;
4240-
}
4241-
stack.push(h);
4242-
for (i = 0, j = 0; i < 2; ++j) {
4243-
if (points[j].index > -1) {
4244-
stack.push(points[j].index);
4245-
i++;
4246-
}
4247-
}
4248-
sp = stack.length;
4249-
for (;j < plen; ++j) {
4250-
if (points[j].index < 0) continue;
4251-
while (!d3_geom_hullCCW(stack[sp - 2], stack[sp - 1], points[j].index, vertices)) {
4252-
--sp;
4253-
}
4254-
stack[sp++] = points[j].index;
4255-
}
4256-
var poly = [];
4257-
for (i = sp - 1; i >= 0; --i) poly.push(data[stack[i]]);
4258-
return poly;
4203+
var fx = d3_functor(x), fy = d3_functor(y), i, n = data.length, points = [], flippedPoints = [];
4204+
for (i = 0; i < n; i++) {
4205+
points.push([ +fx.call(this, data[i], i), +fy.call(this, data[i], i), i ]);
4206+
}
4207+
points.sort(d3_geom_hullOrder);
4208+
for (i = 0; i < n; i++) flippedPoints.push([ points[i][0], -points[i][1] ]);
4209+
var upper = d3_geom_hullUpper(points), lower = d3_geom_hullUpper(flippedPoints);
4210+
var skipLeft = lower[0] === upper[0], skipRight = lower[lower.length - 1] === upper[upper.length - 1], polygon = [];
4211+
for (i = upper.length - 1; i >= 0; --i) polygon.push(data[points[upper[i]][2]]);
4212+
for (i = +skipLeft; i < lower.length - skipRight; ++i) polygon.push(data[points[lower[i]][2]]);
4213+
return polygon;
42594214
}
42604215
hull.x = function(_) {
42614216
return arguments.length ? (x = _, hull) : x;
@@ -4265,18 +4220,18 @@ d3 = function() {
42654220
};
42664221
return hull;
42674222
};
4268-
function d3_geom_hullCCW(i1, i2, i3, v) {
4269-
var t, a, b, c, d, e, f;
4270-
t = v[i1];
4271-
a = t[0];
4272-
b = t[1];
4273-
t = v[i2];
4274-
c = t[0];
4275-
d = t[1];
4276-
t = v[i3];
4277-
e = t[0];
4278-
f = t[1];
4279-
return (f - b) * (c - a) - (d - b) * (e - a) > 0;
4223+
function d3_geom_hullUpper(points) {
4224+
var n = points.length, hull = [ 0, 1 ], hs = 2;
4225+
for (var i = 2; i < n; i++) {
4226+
while (hs > 1 && !d3_isCCWTurn(points[hull[hs - 2]], points[hull[hs - 1]], points[i])) {
4227+
hs--;
4228+
}
4229+
hull[hs++] = i;
4230+
}
4231+
return hull.slice(0, hs);
4232+
}
4233+
function d3_geom_hullOrder(a, b) {
4234+
return a[0] - b[0] || a[1] - b[1];
42804235
}
42814236
d3.geom.polygon = function(coordinates) {
42824237
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: 52 additions & 83 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,18 @@
11
import "../core/functor";
2+
import "../math/trigonometry";
23
import "geom";
34
import "point";
45

56
/**
6-
* Computes the 2D convex hull of a set of points using Graham's scanning
7-
* algorithm. The algorithm has been implemented as described in Cormen,
8-
* Leiserson, and Rivest's Introduction to Algorithms. The running time of
9-
* this algorithm is O(n log n), where n is the number of input points.
7+
* Computes the 2D convex hull of a set of points using the monotone chain
8+
* algorithm:
9+
* http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain)
1010
*
11-
* @param vertices [[x1, y1], [x2, y2], …]
12-
* @returns polygon [[x1, y1], [x2, y2], …]
11+
* The runtime of this algorithm is O(n log n), where n is the number of input
12+
* points. However in practice it outperforms other O(n log n) hulls.
13+
*
14+
* @param vertices [[x1, y1], [x2, y2], ...]
15+
* @returns polygon [[x1, y1], [x2, y2], ...]
1316
*/
1417
d3.geom.hull = function(vertices) {
1518
var x = d3_geom_pointX,
@@ -18,86 +21,40 @@ d3.geom.hull = function(vertices) {
1821
if (arguments.length) return hull(vertices);
1922

2023
function hull(data) {
24+
// Hull of < 3 points is not well-defined
2125
if (data.length < 3) return [];
2226

2327
var fx = d3_functor(x),
2428
fy = d3_functor(y),
29+
i,
2530
n = data.length,
26-
vertices, // TODO use parallel arrays
27-
plen = n - 1,
28-
points = [],
29-
stack = [],
30-
d,
31-
i, j, h = 0, x1, y1, x2, y2, u, v, a, sp;
32-
33-
if (fx === d3_geom_pointX && y === d3_geom_pointY) vertices = data;
34-
else for (i = 0, vertices = []; i < n; ++i) {
35-
vertices.push([+fx.call(this, d = data[i], i), +fy.call(this, d, i)]);
36-
}
31+
points = [], // of the form [[x0, y0, 0], ..., [xn, yn, n]]
32+
flippedPoints = [];
3733

38-
// find the starting ref point: leftmost point with the minimum y coord
39-
for (i = 1; i < n; ++i) {
40-
if (vertices[i][1] < vertices[h][1]
41-
|| vertices[i][1] == vertices[h][1]
42-
&& vertices[i][0] < vertices[h][0]) h = i;
34+
for (i = 0 ; i < n; i++) {
35+
points.push([+fx.call(this, data[i], i), +fy.call(this, data[i], i), i]);
4336
}
4437

45-
// calculate polar angles from ref point and sort
46-
for (i = 0; i < n; ++i) {
47-
if (i === h) continue;
48-
y1 = vertices[i][1] - vertices[h][1];
49-
x1 = vertices[i][0] - vertices[h][0];
50-
points.push({angle: Math.atan2(y1, x1), index: i});
51-
}
52-
points.sort(function(a, b) { return a.angle - b.angle; });
53-
54-
// toss out duplicate angles
55-
a = points[0].angle;
56-
v = points[0].index;
57-
u = 0;
58-
for (i = 1; i < plen; ++i) {
59-
j = points[i].index;
60-
if (a == points[i].angle) {
61-
// keep angle for point most distant from the reference
62-
x1 = vertices[v][0] - vertices[h][0];
63-
y1 = vertices[v][1] - vertices[h][1];
64-
x2 = vertices[j][0] - vertices[h][0];
65-
y2 = vertices[j][1] - vertices[h][1];
66-
if (x1 * x1 + y1 * y1 >= x2 * x2 + y2 * y2) {
67-
points[i].index = -1;
68-
continue;
69-
} else {
70-
points[u].index = -1;
71-
}
72-
}
73-
a = points[i].angle;
74-
u = i;
75-
v = j;
76-
}
38+
// sort ascending by x-coord first, y-coord second
39+
points.sort(d3_geom_hullOrder);
7740

78-
// initialize the stack
79-
stack.push(h);
80-
for (i = 0, j = 0; i < 2; ++j) {
81-
if (points[j].index > -1) {
82-
stack.push(points[j].index);
83-
i++;
84-
}
85-
}
86-
sp = stack.length;
87-
88-
// do graham's scan
89-
for (; j < plen; ++j) {
90-
if (points[j].index < 0) continue; // skip tossed out points
91-
while (!d3_geom_hullCCW(stack[sp - 2], stack[sp - 1], points[j].index, vertices)) {
92-
--sp;
93-
}
94-
stack[sp++] = points[j].index;
95-
}
41+
// we flip bottommost points across y axis so we can use the upper hull routine on both
42+
for (i = 0; i < n; i++) flippedPoints.push([points[i][0], -points[i][1]]);
43+
44+
var upper = d3_geom_hullUpper(points),
45+
lower = d3_geom_hullUpper(flippedPoints);
9646

97-
// construct the hull
98-
var poly = [];
99-
for (i = sp - 1; i >= 0; --i) poly.push(data[stack[i]]);
100-
return poly;
47+
// construct the polygon, removing possible duplicate endpoints
48+
var skipLeft = lower[0] === upper[0],
49+
skipRight = lower[lower.length - 1] === upper[upper.length - 1],
50+
polygon = [];
51+
52+
for (i = upper.length - 1; i >= 0; --i)
53+
polygon.push(data[points[upper[i]][2]]); // add upper hull in r->l order
54+
for (i = +skipLeft; i < lower.length - skipRight; ++i)
55+
polygon.push(data[points[lower[i]][2]]); // add lower hull in l->r order
56+
57+
return polygon;
10158
}
10259

10360
hull.x = function(_) {
@@ -111,11 +68,23 @@ d3.geom.hull = function(vertices) {
11168
return hull;
11269
};
11370

114-
// are three points in counter-clockwise order?
115-
function d3_geom_hullCCW(i1, i2, i3, v) {
116-
var t, a, b, c, d, e, f;
117-
t = v[i1]; a = t[0]; b = t[1];
118-
t = v[i2]; c = t[0]; d = t[1];
119-
t = v[i3]; e = t[0]; f = t[1];
120-
return (f - b) * (c - a) - (d - b) * (e - a) > 0;
71+
// finds the 'upper convex hull' (see wiki link above)
72+
// assumes points arg has >=3 elements, is sorted by x, unique in y
73+
// returns array of indices into points in left to right order
74+
function d3_geom_hullUpper(points) {
75+
var n = points.length,
76+
hull = [0, 1],
77+
hs = 2; // hull size
78+
79+
for (var i = 2; i < n; i++) {
80+
while (hs > 1 && !d3_isCCWTurn(points[hull[hs-2]], points[hull[hs-1]], points[i])) {
81+
hs --;
82+
}
83+
hull[hs++] = i;
84+
}
85+
// we slice to make sure that the points we 'popped' from hull don't stay behind
86+
return hull.slice(0, hs);
12187
}
88+
89+
// comparator for ascending sort by x-coord first, y-coord second
90+
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)