Skip to content

Commit 36d8060

Browse files
2735979427359794
committed
Why are there conflicts
1 parent d12b352 commit 36d8060

1 file changed

Lines changed: 49 additions & 80 deletions

File tree

‎src/geom/hull.js‎

Lines changed: 49 additions & 80 deletions
Original file line numberDiff line numberDiff line change
@@ -3,10 +3,12 @@ import "geom";
33
import "point";
44

55
/**
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.
6+
* Computes the 2D convex hull of a set of points using the monotone chain
7+
* algorithm:
8+
* http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain)
9+
*
10+
* The runtime of this algorithm is O(n log n), where n is the number of input
11+
* points. However in practice it outperforms other O(n log n) hulls.
1012
*
1113
* @param vertices [[x1, y1], [x2, y2], …]
1214
* @returns polygon [[x1, y1], [x2, y2], …]
@@ -18,85 +20,37 @@ d3.geom.hull = function(vertices) {
1820
if (arguments.length) return hull(vertices);
1921

2022
function hull(data) {
23+
// Hull of < 3 points is not well-defined
2124
if (data.length < 3) return [];
2225

2326
var fx = d3_functor(x),
2427
fy = d3_functor(y),
25-
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;
28+
n = data.length;
3229

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)]);
30+
for (i = 0, points = []; i < n; ++i) {
31+
points.push([+fx.call(this, d = data[i], i), +fy.call(this, d, i), i]);
3632
}
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;
43-
}
34+
// sort ascending by x-coord first, y-coord second
35+
points.sort(function(a, b) {
36+
return (a[0] < b[0] || (a[0] === b[0] && a[1] < b[1])) ? -1 : 1;
37+
});
4438

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; });
39+
// we flip bottommost points across y axis so we can use the upper hull routine on both
40+
var flipped_points = [];
41+
for (var i = 0; i < n; i++) flipped_points.push([points[i][0], -points[i][1]]);
5342

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-
}
43+
var uhull = d3_geom_hull_find_upper_hull(points);
44+
var lhull = d3_geom_hull_find_upper_hull(flipped_points);
7745

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-
}
96-
97-
// construct the hull
98-
var poly = [];
99-
for (i = sp - 1; i >= 0; --i) poly.push(data[stack[i]]);
46+
// construct the poly, removing possible duplicate endpoints
47+
var skip_l = (lhull[0] === uhull[0]),
48+
skip_r = (lhull[lhull.length - 1] === uhull[uhull.length - 1]),
49+
poly = [];
50+
for (var i=uhull.length - 1; i >= 0; i--)
51+
poly.push(data[points[uhull[i]][2]]);
52+
for (var i = +skip_l; i < lhull.length - skip_r; i++)
53+
poly.push(data[points[lhull[i]][2]]);
10054
return poly;
10155
}
10256

@@ -111,11 +65,26 @@ d3.geom.hull = function(vertices) {
11165
return hull;
11266
};
11367

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;
68+
// finds the 'upper convex hull' (see wiki link above)
69+
// assumes points arg has >=3 elements, is sorted by x, unique in y
70+
// returns array of indices into points in left to right order
71+
function d3_geom_hull_find_upper_hull(points) {
72+
var n = points.length,
73+
hull = [0, 1],
74+
hs = 2; // hull size
75+
76+
for (var i = 2; i < n; i++) {
77+
while (hs > 1 && !d3_geom_hull_CW(points[hull[hs-2]], points[hull[hs-1]], points[i])) {
78+
hs --;
79+
}
80+
hull[hs++] = i;
81+
}
82+
// we slice to make sure that the points we 'popped' from hull don't stay behind
83+
return hull.slice(0, hs);
84+
}
85+
86+
// are three points a, b, c in clockwise order?
87+
// i.e. is the sign of (b-a)x(c-a) positive?
88+
function d3_geom_hull_CW(a, b, c) {
89+
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]) > 0;
12190
}

0 commit comments

Comments
 (0)