Skip to content

Commit 2467834

Browse files
jasondaviesmbostock
jasondavies
authored and
mbostock
committed
Add d3.geo.centroid.
Polygons are temporarily treated as lines while I work on adding area weighting. See d3#941.
1 parent 560a091 commit 2467834

6 files changed

Lines changed: 272 additions & 27 deletions

File tree

‎Makefile‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,7 @@ d3.geo.js: \
186186
src/geo/azimuthal-equal-area.js \
187187
src/geo/azimuthal-equidistant.js \
188188
src/geo/bounds.js \
189+
src/geo/centroid.js \
189190
src/geo/circle.js \
190191
src/geo/compose.js \
191192
src/geo/equirectangular.js \

‎d3.js‎

Lines changed: 77 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -5501,6 +5501,83 @@
55015501
return [ [ x0, y0 ], [ x1, y1 ] ];
55025502
};
55035503
}
5504+
d3.geo.centroid = function(object) {
5505+
return d3_geo_centroidType.object(object);
5506+
};
5507+
var d3_geo_centroidType = d3_geo_type({
5508+
Feature: function(feature) {
5509+
return this.geometry(feature.geometry);
5510+
},
5511+
Point: function(point) {
5512+
return point.coordinates;
5513+
},
5514+
MultiPoint: function(multiPoint) {
5515+
var coordinates = multiPoint.coordinates, n = coordinates.length, i = 0, point, λ, φ, cosφ, x = 0, y = 0, z = 0;
5516+
while (i < n) {
5517+
point = coordinates[i++];
5518+
λ = point[0] * d3_radians;
5519+
cosφ = Math.cos(φ = point[1] * d3_radians);
5520+
x += (cosφ * Math.cos(λ) - x) / i;
5521+
y += (cosφ * Math.sin(λ) - y) / i;
5522+
z += (Math.sin(φ) - z) / i;
5523+
}
5524+
return n ? [ Math.atan2(y, x) * d3_degrees, Math.asin(Math.max(-1, Math.min(1, z))) * d3_degrees ] : null;
5525+
},
5526+
LineString: function(line) {
5527+
var centroid = d3_geo_centroidLine(line.coordinates), cx, cy, cz;
5528+
return centroid && centroid[3] ? [ Math.atan2(cy = centroid[1], cx = centroid[0]) * d3_degrees, Math.asin(Math.max(-1, Math.min(1, (cz = centroid[2]) / Math.sqrt(cx * cx + cy * cy + cz * cz)))) * d3_degrees ] : null;
5529+
},
5530+
MultiLineString: function(multiLine) {
5531+
var coordinates = multiLine.coordinates, n = coordinates.length, i = -1, cx = 0, cy = 0, cz = 0, weight = 0;
5532+
while (++i < n) {
5533+
centroid = d3_geo_centroidLine(coordinates[i]);
5534+
if (!centroid) continue;
5535+
cx += centroid[0];
5536+
cy += centroid[1];
5537+
cz += centroid[2];
5538+
weight += centroid[3];
5539+
}
5540+
return weight ? [ Math.atan2(cy, cx) * d3_degrees, Math.asin(Math.max(-1, Math.min(1, cz / Math.sqrt(cx * cx + cy * cy + cz * cz)))) * d3_degrees ] : null;
5541+
},
5542+
Polygon: function(polygon) {
5543+
return this.MultiLineString(polygon);
5544+
},
5545+
MultiPolygon: function(multiPolygon) {
5546+
var coordinates = multiPolygon.coordinates, n = coordinates.length, i = -1, cx = 0, cy = 0, cz = 0, weight = 0, polygon;
5547+
while (++i < n) {
5548+
polygon = coordinates[i];
5549+
for (var j = 0, m = polygon.length; j < m; ++j) {
5550+
centroid = d3_geo_centroidLine(polygon[j]);
5551+
if (!centroid) continue;
5552+
cx += centroid[0];
5553+
cy += centroid[1];
5554+
cz += centroid[2];
5555+
weight += centroid[3];
5556+
}
5557+
}
5558+
return weight ? [ Math.atan2(cy, cx) * d3_degrees, Math.asin(Math.max(-1, Math.min(1, cz / Math.sqrt(cx * cx + cy * cy + cz * cz)))) * d3_degrees ] : null;
5559+
}
5560+
});
5561+
function d3_geo_centroidLine(coordinates) {
5562+
if (!(n = coordinates.length)) return null;
5563+
var point = coordinates[0], i = 0, n, λ = point[0] * d3_radians, φ, cosφ = Math.cos(φ = point[1] * d3_radians), x0 = cosφ * Math.cos(λ), y0 = cosφ * Math.sin(λ), z0 = Math.sin(φ), cx = 0, cy = 0, cz = 0, x, y, z, w, weight = 0;
5564+
while (++i < n) {
5565+
point = coordinates[i];
5566+
λ = point[0] * d3_radians;
5567+
cosφ = Math.cos(φ = point[1] * d3_radians);
5568+
x = cosφ * Math.cos(λ);
5569+
y = cosφ * Math.sin(λ);
5570+
z = Math.sin(φ);
5571+
weight += w = Math.atan2(Math.sqrt((w = y0 * z - z0 * y) * w + (w = z0 * x - x0 * z) * w + (w = x0 * y - y0 * x) * w), x0 * x + y0 * y + z0 * z);
5572+
x = (x0 + (x0 = x)) / 2;
5573+
y = (y0 + (y0 = y)) / 2;
5574+
z = (z0 + (z0 = z)) / 2;
5575+
cx += w * x;
5576+
cy += w * y;
5577+
cz += w * z;
5578+
}
5579+
return [ cx, cy, cz, weight ];
5580+
}
55045581
d3.geo.circle = function() {
55055582
var origin = [ 0, 0 ], angle, precision = 6, rotate, interpolate;
55065583
function circle() {
@@ -6144,17 +6221,6 @@
61446221
function d3_geo_pathCircle(radius) {
61456222
return "m0," + radius + "a" + radius + "," + radius + " 0 1,1 0," + -2 * radius + "a" + radius + "," + radius + " 0 1,1 0," + +2 * radius + "z";
61466223
}
6147-
var d3_geo_pathIdentity = d3.geo.path().projection({
6148-
polygon: function(polygon, context) {
6149-
polygon.forEach(function(ring) {
6150-
var n = ring.length, i = 0, point;
6151-
context.moveTo((point = ring[0])[0], point[1]);
6152-
while (++i < n) context.lineTo((point = ring[i])[0], point[1]);
6153-
context.closePath();
6154-
});
6155-
}
6156-
});
6157-
d3.geo.centroid = d3_geo_pathIdentity.centroid;
61586224
d3.geo.projection = d3_geo_projection;
61596225
d3.geo.projectionMutator = d3_geo_projectionMutator;
61606226
function d3_geo_projection(project) {

‎d3.min.js‎

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

‎src/geo/centroid.js‎

Lines changed: 132 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,132 @@
1-
d3.geo.centroid = d3_geo_pathIdentity.centroid;
1+
d3.geo.centroid = function(object) {
2+
return d3_geo_centroidType.object(object);
3+
};
4+
5+
var d3_geo_centroidType = d3_geo_type({
6+
Feature: function(feature) { return this.geometry(feature.geometry); },
7+
Point: function(point) { return point.coordinates; },
8+
MultiPoint: function(multiPoint) {
9+
var coordinates = multiPoint.coordinates,
10+
n = coordinates.length,
11+
i = 0,
12+
point,
13+
λ,
14+
φ,
15+
cosφ,
16+
x = 0,
17+
y = 0,
18+
z = 0;
19+
while (i < n) {
20+
point = coordinates[i++];
21+
λ = point[0] * d3_radians;
22+
cosφ = Math.cos(φ = point[1] * d3_radians);
23+
x += (cosφ * Math.cos(λ) - x) / i;
24+
y += (cosφ * Math.sin(λ) - y) / i;
25+
z += (Math.sin(φ) - z) / i;
26+
}
27+
return n ? [
28+
Math.atan2(y, x) * d3_degrees,
29+
Math.asin(Math.max(-1, Math.min(1, z))) * d3_degrees
30+
] : null;
31+
},
32+
LineString: function(line) {
33+
var centroid = d3_geo_centroidLine(line.coordinates),
34+
cx,
35+
cy,
36+
cz;
37+
return centroid && centroid[3] ? [
38+
Math.atan2(cy = centroid[1], cx = centroid[0]) * d3_degrees,
39+
Math.asin(Math.max(-1, Math.min(1, (cz = centroid[2]) / Math.sqrt(cx * cx + cy * cy + cz * cz)))) * d3_degrees
40+
] : null;
41+
},
42+
MultiLineString: function(multiLine) {
43+
var coordinates = multiLine.coordinates,
44+
n = coordinates.length,
45+
i = -1,
46+
cx = 0,
47+
cy = 0,
48+
cz = 0,
49+
weight = 0;
50+
while (++i < n) {
51+
centroid = d3_geo_centroidLine(coordinates[i]);
52+
if (!centroid) continue;
53+
cx += centroid[0];
54+
cy += centroid[1];
55+
cz += centroid[2];
56+
weight += centroid[3];
57+
}
58+
return weight ? [
59+
Math.atan2(cy, cx) * d3_degrees,
60+
Math.asin(Math.max(-1, Math.min(1, cz / Math.sqrt(cx * cx + cy * cy + cz * cz)))) * d3_degrees
61+
] : null;
62+
},
63+
Polygon: function(polygon) {
64+
// TODO use area weighting
65+
return this.MultiLineString(polygon);
66+
},
67+
MultiPolygon: function(multiPolygon) {
68+
// TODO use area weighting
69+
var coordinates = multiPolygon.coordinates,
70+
n = coordinates.length,
71+
i = -1,
72+
cx = 0,
73+
cy = 0,
74+
cz = 0,
75+
weight = 0,
76+
polygon;
77+
while (++i < n) {
78+
polygon = coordinates[i];
79+
for (var j = 0, m = polygon.length; j < m; ++j) {
80+
centroid = d3_geo_centroidLine(polygon[j]);
81+
if (!centroid) continue;
82+
cx += centroid[0];
83+
cy += centroid[1];
84+
cz += centroid[2];
85+
weight += centroid[3];
86+
}
87+
}
88+
return weight ? [
89+
Math.atan2(cy, cx) * d3_degrees,
90+
Math.asin(Math.max(-1, Math.min(1, cz / Math.sqrt(cx * cx + cy * cy + cz * cz)))) * d3_degrees
91+
] : null;
92+
}
93+
});
94+
95+
function d3_geo_centroidLine(coordinates) {
96+
if (!(n = coordinates.length)) return null;
97+
var point = coordinates[0],
98+
i = 0,
99+
n,
100+
λ = point[0] * d3_radians,
101+
φ,
102+
cosφ = Math.cos(φ = point[1] * d3_radians),
103+
x0 = cosφ * Math.cos(λ),
104+
y0 = cosφ * Math.sin(λ),
105+
z0 = Math.sin(φ),
106+
cx = 0,
107+
cy = 0,
108+
cz = 0,
109+
x,
110+
y,
111+
z,
112+
w,
113+
weight = 0;
114+
while (++i < n) {
115+
point = coordinates[i];
116+
λ = point[0] * d3_radians;
117+
cosφ = Math.cos(φ = point[1] * d3_radians);
118+
x = cosφ * Math.cos(λ);
119+
y = cosφ * Math.sin(λ);
120+
z = Math.sin(φ);
121+
weight += w = Math.atan2(
122+
Math.sqrt((w = y0 * z - z0 * y) * w + (w = z0 * x - x0 * z) * w + (w = x0 * y - y0 * x) * w),
123+
x0 * x + y0 * y + z0 * z);
124+
x = (x0 + (x0 = x)) / 2;
125+
y = (y0 + (y0 = y)) / 2;
126+
z = (z0 + (z0 = z)) / 2;
127+
cx += w * x;
128+
cy += w * y;
129+
cz += w * z;
130+
}
131+
return [cx, cy, cz, weight];
132+
}

‎src/geo/path.js‎

Lines changed: 0 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -185,14 +185,3 @@ function d3_geo_pathCircle(radius) {
185185
+ "a" + radius + "," + radius + " 0 1,1 0," + (+2 * radius)
186186
+ "z";
187187
}
188-
189-
var d3_geo_pathIdentity = d3.geo.path().projection({
190-
polygon: function(polygon, context) {
191-
polygon.forEach(function(ring) {
192-
var n = ring.length, i = 0, point;
193-
context.moveTo((point = ring[0])[0], point[1]);
194-
while (++i < n) context.lineTo((point = ring[i])[0], point[1]);
195-
context.closePath();
196-
});
197-
}
198-
});

‎test/geo/centroid-test.js‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
require("../env");
2+
3+
var vows = require("vows"),
4+
assert = require("assert");
5+
6+
var suite = vows.describe("d3.geo.centroid");
7+
8+
suite.addBatch({
9+
"centroid": {
10+
topic: function() {
11+
return d3.geo.centroid;
12+
},
13+
"Point": function(centroid) {
14+
assert.deepEqual(centroid({type: "Point", coordinates: [0, 0]}), [0, 0]);
15+
},
16+
"MultiPoint": function(centroid) {
17+
assert.inDelta(centroid({type: "MultiPoint", coordinates: [[0, 0], [1, 2]]}), [0.499847, 0.999847], 1e-6);
18+
assert.deepEqual(centroid({type: "MultiPoint", coordinates: [[179, 0], [-179, 0]]}), [180, 0]);
19+
},
20+
"LineString": function(centroid) {
21+
assert.inDelta(centroid({type: "LineString", coordinates: [[0, 0], [1, 0]]}), [.5, 0], 1e-6);
22+
assert.inDelta(centroid({type: "LineString", coordinates: [[0, 0], [0, 90]]}), [0, 45], 1e-6);
23+
assert.inDelta(centroid({type: "LineString", coordinates: [[0, 0], [0, 45], [0, 90]]}), [0, 45], 1e-6);
24+
assert.inDelta(centroid({type: "LineString", coordinates: [[-1, -1], [1, 1]]}), [0, 0], 1e-6);
25+
assert.inDelta(centroid({type: "LineString", coordinates: [[-60, -1], [60, 1]]}), [0, 0], 1e-6);
26+
assert.inDelta(centroid({type: "LineString", coordinates: [[179, -1], [-179, 1]]}), [180, 0], 1e-6);
27+
assert.inDelta(centroid({type: "LineString", coordinates: [[-179, 0], [0, 0], [179, 0]]}), [0, 0], 1e-6);
28+
assert.inDelta(centroid({type: "LineString", coordinates: [[0, -90], [0, 90]]}), [0, 0], 1e-6);
29+
assert.inDelta(centroid({type: "LineString", coordinates: [[-180, -90], [0, 90]]}), [-90, 0], 1e-6);
30+
},
31+
"MultiLineString": function(centroid) {
32+
assert.inDelta(centroid({type: "MultiLineString", coordinates: [[[0, 0], [0, 2]]]}), [0, 1], 1e-6);
33+
},
34+
"Polygon": function(centroid) {
35+
assert.inDelta(centroid({type: "Polygon", coordinates: [[[0, -90], [0, 0], [0, 90], [1, 0], [0, -90]]]}), [.5, 0], 1e-6);
36+
assert.inDelta(centroid(d3.geo.circle().angle(5).origin([0, 45])()), [0, 45], 1e-6);
37+
assert.equal(centroid({type: "Polygon", coordinates: [d3.range(-180, 180 + 1 / 2, 1).map(function(x) { return [x, -60]; })]})[1], -90);
38+
assert.inDelta(centroid({type: "Polygon", coordinates: [[[0, -10], [0, 10], [10, 10], [10, -10], [0, -10]]]}), [5, 0], 1e-6);
39+
},
40+
"MultiPolygon": function(centroid) {
41+
assert.inDelta(centroid({type: "MultiPolygon", coordinates: [[[[0, -90], [0, 0], [0, 90], [1, 0], [0, -90]]]]}), [.5, 0], 1e-6);
42+
},
43+
"Sphere": function(centroid) {
44+
assert.isUndefined(centroid({type: "Sphere"}));
45+
},
46+
"Feature": function(centroid) {
47+
assert.deepEqual(centroid({type: "Feature", geometry: {type: "Point", coordinates: [0, 0]}}), [0, 0]);
48+
},
49+
"FeatureCollection": function(centroid) {
50+
assert.isUndefined(centroid({type: "FeatureCollection", features: [{type: "Feature", geometry: {type: "Point", coordinates: [0, 0]}}]}));
51+
},
52+
"GeometryCollection": function(centroid) {
53+
assert.isUndefined(centroid({type: "GeometryCollection", geometries: [{type: "Point", coordinates: [0, 0]}]}));
54+
}
55+
}
56+
});
57+
58+
suite.export(module);

0 commit comments

Comments
 (0)