Skip to content

Commit fd40dc2

Browse files
jasondaviesjasondavies
committed
Refactor d3.geom.hull.
1 parent cf56155 commit fd40dc2

4 files changed

Lines changed: 305 additions & 199 deletions

File tree

‎d3.js‎

Lines changed: 148 additions & 133 deletions
Original file line numberDiff line numberDiff line change
@@ -3660,139 +3660,6 @@ d3 = function() {
36603660
return d3_geo_projection(d3_geo_transverseMercator);
36613661
}).raw = d3_geo_transverseMercator;
36623662
d3.geom = {};
3663-
d3.geom.hull = function(vertices) {
3664-
if (vertices.length < 3) return [];
3665-
var len = vertices.length, plen = len - 1, points = [], stack = [], i, j, h = 0, x1, y1, x2, y2, u, v, a, sp;
3666-
for (i = 1; i < len; ++i) {
3667-
if (vertices[i][1] < vertices[h][1]) {
3668-
h = i;
3669-
} else if (vertices[i][1] == vertices[h][1]) {
3670-
h = vertices[i][0] < vertices[h][0] ? i : h;
3671-
}
3672-
}
3673-
for (i = 0; i < len; ++i) {
3674-
if (i === h) continue;
3675-
y1 = vertices[i][1] - vertices[h][1];
3676-
x1 = vertices[i][0] - vertices[h][0];
3677-
points.push({
3678-
angle: Math.atan2(y1, x1),
3679-
index: i
3680-
});
3681-
}
3682-
points.sort(function(a, b) {
3683-
return a.angle - b.angle;
3684-
});
3685-
a = points[0].angle;
3686-
v = points[0].index;
3687-
u = 0;
3688-
for (i = 1; i < plen; ++i) {
3689-
j = points[i].index;
3690-
if (a == points[i].angle) {
3691-
x1 = vertices[v][0] - vertices[h][0];
3692-
y1 = vertices[v][1] - vertices[h][1];
3693-
x2 = vertices[j][0] - vertices[h][0];
3694-
y2 = vertices[j][1] - vertices[h][1];
3695-
if (x1 * x1 + y1 * y1 >= x2 * x2 + y2 * y2) {
3696-
points[i].index = -1;
3697-
} else {
3698-
points[u].index = -1;
3699-
a = points[i].angle;
3700-
u = i;
3701-
v = j;
3702-
}
3703-
} else {
3704-
a = points[i].angle;
3705-
u = i;
3706-
v = j;
3707-
}
3708-
}
3709-
stack.push(h);
3710-
for (i = 0, j = 0; i < 2; ++j) {
3711-
if (points[j].index !== -1) {
3712-
stack.push(points[j].index);
3713-
i++;
3714-
}
3715-
}
3716-
sp = stack.length;
3717-
for (;j < plen; ++j) {
3718-
if (points[j].index === -1) continue;
3719-
while (!d3_geom_hullCCW(stack[sp - 2], stack[sp - 1], points[j].index, vertices)) {
3720-
--sp;
3721-
}
3722-
stack[sp++] = points[j].index;
3723-
}
3724-
var poly = [];
3725-
for (i = 0; i < sp; ++i) {
3726-
poly.push(vertices[stack[i]]);
3727-
}
3728-
return poly;
3729-
};
3730-
function d3_geom_hullCCW(i1, i2, i3, v) {
3731-
var t, a, b, c, d, e, f;
3732-
t = v[i1];
3733-
a = t[0];
3734-
b = t[1];
3735-
t = v[i2];
3736-
c = t[0];
3737-
d = t[1];
3738-
t = v[i3];
3739-
e = t[0];
3740-
f = t[1];
3741-
return (f - b) * (c - a) - (d - b) * (e - a) > 0;
3742-
}
3743-
d3.geom.polygon = function(coordinates) {
3744-
coordinates.area = function() {
3745-
var i = 0, n = coordinates.length, area = coordinates[n - 1][1] * coordinates[0][0] - coordinates[n - 1][0] * coordinates[0][1];
3746-
while (++i < n) {
3747-
area += coordinates[i - 1][1] * coordinates[i][0] - coordinates[i - 1][0] * coordinates[i][1];
3748-
}
3749-
return area * .5;
3750-
};
3751-
coordinates.centroid = function(k) {
3752-
var i = -1, n = coordinates.length, x = 0, y = 0, a, b = coordinates[n - 1], c;
3753-
if (!arguments.length) k = -1 / (6 * coordinates.area());
3754-
while (++i < n) {
3755-
a = b;
3756-
b = coordinates[i];
3757-
c = a[0] * b[1] - b[0] * a[1];
3758-
x += (a[0] + b[0]) * c;
3759-
y += (a[1] + b[1]) * c;
3760-
}
3761-
return [ x * k, y * k ];
3762-
};
3763-
coordinates.clip = function(subject) {
3764-
var input, i = -1, n = coordinates.length, j, m, a = coordinates[n - 1], b, c, d;
3765-
while (++i < n) {
3766-
input = subject.slice();
3767-
subject.length = 0;
3768-
b = coordinates[i];
3769-
c = input[(m = input.length) - 1];
3770-
j = -1;
3771-
while (++j < m) {
3772-
d = input[j];
3773-
if (d3_geom_polygonInside(d, a, b)) {
3774-
if (!d3_geom_polygonInside(c, a, b)) {
3775-
subject.push(d3_geom_polygonIntersect(c, d, a, b));
3776-
}
3777-
subject.push(d);
3778-
} else if (d3_geom_polygonInside(c, a, b)) {
3779-
subject.push(d3_geom_polygonIntersect(c, d, a, b));
3780-
}
3781-
c = d;
3782-
}
3783-
a = b;
3784-
}
3785-
return subject;
3786-
};
3787-
return coordinates;
3788-
};
3789-
function d3_geom_polygonInside(p, a, b) {
3790-
return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
3791-
}
3792-
function d3_geom_polygonIntersect(c, d, a, b) {
3793-
var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3, y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3, ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
3794-
return [ x1 + ua * x21, y1 + ua * y21 ];
3795-
}
37963663
d3.svg = {};
37973664
function d3_svg_line(projection) {
37983665
var x = d3_svg_lineX, y = d3_svg_lineY, defined = d3_true, interpolate = d3_svg_lineLinear, interpolateKey = interpolate.key, tension = .7;
@@ -4048,6 +3915,154 @@ d3 = function() {
40483915
function d3_svg_lineMonotone(points) {
40493916
return points.length < 3 ? d3_svg_lineLinear(points) : points[0] + d3_svg_lineHermite(points, d3_svg_lineMonotoneTangents(points));
40503917
}
3918+
d3.geom.hull = function(vertices) {
3919+
var x = d3_svg_lineX, y = d3_svg_lineY;
3920+
if (arguments.length) return hull(vertices);
3921+
function hull(data) {
3922+
if (data.length < 3) return [];
3923+
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;
3924+
if (fx === d3_svg_lineX && y === d3_svg_lineY) vertices = data; else for (i = 0,
3925+
vertices = []; i < n; ++i) {
3926+
vertices.push([ +fx.call(this, d = data[i], i), +fy.call(this, d, i) ]);
3927+
}
3928+
for (i = 1; i < n; ++i) {
3929+
if (vertices[i][1] < vertices[h][1]) {
3930+
h = i;
3931+
} else if (vertices[i][1] == vertices[h][1]) {
3932+
h = vertices[i][0] < vertices[h][0] ? i : h;
3933+
}
3934+
}
3935+
for (i = 0; i < n; ++i) {
3936+
if (i === h) continue;
3937+
y1 = vertices[i][1] - vertices[h][1];
3938+
x1 = vertices[i][0] - vertices[h][0];
3939+
points.push({
3940+
angle: Math.atan2(y1, x1),
3941+
index: i
3942+
});
3943+
}
3944+
points.sort(function(a, b) {
3945+
return a.angle - b.angle;
3946+
});
3947+
a = points[0].angle;
3948+
v = points[0].index;
3949+
u = 0;
3950+
for (i = 1; i < plen; ++i) {
3951+
j = points[i].index;
3952+
if (a == points[i].angle) {
3953+
x1 = vertices[v][0] - vertices[h][0];
3954+
y1 = vertices[v][1] - vertices[h][1];
3955+
x2 = vertices[j][0] - vertices[h][0];
3956+
y2 = vertices[j][1] - vertices[h][1];
3957+
if (x1 * x1 + y1 * y1 >= x2 * x2 + y2 * y2) {
3958+
points[i].index = -1;
3959+
} else {
3960+
points[u].index = -1;
3961+
a = points[i].angle;
3962+
u = i;
3963+
v = j;
3964+
}
3965+
} else {
3966+
a = points[i].angle;
3967+
u = i;
3968+
v = j;
3969+
}
3970+
}
3971+
stack.push(h);
3972+
for (i = 0, j = 0; i < 2; ++j) {
3973+
if (points[j].index !== -1) {
3974+
stack.push(points[j].index);
3975+
i++;
3976+
}
3977+
}
3978+
sp = stack.length;
3979+
for (;j < plen; ++j) {
3980+
if (points[j].index === -1) continue;
3981+
while (!d3_geom_hullCCW(stack[sp - 2], stack[sp - 1], points[j].index, vertices)) {
3982+
--sp;
3983+
}
3984+
stack[sp++] = points[j].index;
3985+
}
3986+
var poly = [];
3987+
for (i = 0; i < sp; ++i) {
3988+
poly.push(data[stack[i]]);
3989+
}
3990+
return poly;
3991+
}
3992+
hull.x = function(_) {
3993+
return arguments.length ? (x = _, hull) : x;
3994+
};
3995+
hull.y = function(_) {
3996+
return arguments.length ? (y = _, hull) : y;
3997+
};
3998+
return hull;
3999+
};
4000+
function d3_geom_hullCCW(i1, i2, i3, v) {
4001+
var t, a, b, c, d, e, f;
4002+
t = v[i1];
4003+
a = t[0];
4004+
b = t[1];
4005+
t = v[i2];
4006+
c = t[0];
4007+
d = t[1];
4008+
t = v[i3];
4009+
e = t[0];
4010+
f = t[1];
4011+
return (f - b) * (c - a) - (d - b) * (e - a) > 0;
4012+
}
4013+
d3.geom.polygon = function(coordinates) {
4014+
coordinates.area = function() {
4015+
var i = 0, n = coordinates.length, area = coordinates[n - 1][1] * coordinates[0][0] - coordinates[n - 1][0] * coordinates[0][1];
4016+
while (++i < n) {
4017+
area += coordinates[i - 1][1] * coordinates[i][0] - coordinates[i - 1][0] * coordinates[i][1];
4018+
}
4019+
return area * .5;
4020+
};
4021+
coordinates.centroid = function(k) {
4022+
var i = -1, n = coordinates.length, x = 0, y = 0, a, b = coordinates[n - 1], c;
4023+
if (!arguments.length) k = -1 / (6 * coordinates.area());
4024+
while (++i < n) {
4025+
a = b;
4026+
b = coordinates[i];
4027+
c = a[0] * b[1] - b[0] * a[1];
4028+
x += (a[0] + b[0]) * c;
4029+
y += (a[1] + b[1]) * c;
4030+
}
4031+
return [ x * k, y * k ];
4032+
};
4033+
coordinates.clip = function(subject) {
4034+
var input, i = -1, n = coordinates.length, j, m, a = coordinates[n - 1], b, c, d;
4035+
while (++i < n) {
4036+
input = subject.slice();
4037+
subject.length = 0;
4038+
b = coordinates[i];
4039+
c = input[(m = input.length) - 1];
4040+
j = -1;
4041+
while (++j < m) {
4042+
d = input[j];
4043+
if (d3_geom_polygonInside(d, a, b)) {
4044+
if (!d3_geom_polygonInside(c, a, b)) {
4045+
subject.push(d3_geom_polygonIntersect(c, d, a, b));
4046+
}
4047+
subject.push(d);
4048+
} else if (d3_geom_polygonInside(c, a, b)) {
4049+
subject.push(d3_geom_polygonIntersect(c, d, a, b));
4050+
}
4051+
c = d;
4052+
}
4053+
a = b;
4054+
}
4055+
return subject;
4056+
};
4057+
return coordinates;
4058+
};
4059+
function d3_geom_polygonInside(p, a, b) {
4060+
return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
4061+
}
4062+
function d3_geom_polygonIntersect(c, d, a, b) {
4063+
var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3, y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3, ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
4064+
return [ x1 + ua * x21, y1 + ua * y21 ];
4065+
}
40514066
d3.geom.delaunay = function(vertices) {
40524067
var edges = vertices.map(function() {
40534068
return [];

‎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.

0 commit comments

Comments
 (0)