Skip to content

Commit d580a64

Browse files
mbostockmbostock
committed
Merge branch 'geo-centroid' of git://github.com/jasondavies/d3 into 3.0
2 parents 5fd98b6 + b97715b commit d580a64

4 files changed

Lines changed: 198 additions & 42 deletions

File tree

‎d3.js‎

Lines changed: 43 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -6664,24 +6664,44 @@
66646664
function polygonArea(coordinates) {
66656665
return ringArea(coordinates[0]) - d3.sum(coordinates.slice(1), ringArea);
66666666
}
6667+
function geometryDimension(o) {
6668+
switch (o.type) {
6669+
case "Point":
6670+
case "MultiPoint":
6671+
return 0;
6672+
case "LineString":
6673+
case "MultiLineString":
6674+
return 1;
6675+
case "Polygon":
6676+
case "MultiPolygon":
6677+
return 2;
6678+
}
6679+
}
66676680
function singleCentroid(weightedCentroid) {
66686681
return function(o) {
66696682
var centroid = weightedCentroid(o.coordinates);
6670-
return [ centroid[0] / centroid[2], centroid[1] / centroid[2] ];
6683+
return centroid ? [ centroid[0] / centroid[2], centroid[1] / centroid[2] ] : null;
66716684
};
66726685
}
66736686
function multiCentroid(weightedCentroid) {
66746687
return function(o) {
66756688
var coordinates = o.coordinates, centroid, x = 0, y = 0, z = 0, i = -1, n = coordinates.length;
66766689
while (++i < n) {
66776690
centroid = weightedCentroid(coordinates[i]);
6678-
x += centroid[0];
6679-
y += centroid[1];
6680-
z += centroid[2];
6691+
if (centroid != null) {
6692+
x += centroid[0];
6693+
y += centroid[1];
6694+
z += centroid[2];
6695+
}
66816696
}
6682-
return [ x / z, y / z ];
6697+
return z ? [ x / z, y / z ] : null;
66836698
};
66846699
}
6700+
function pointCentroid(coordinates) {
6701+
coordinates = projection(coordinates);
6702+
coordinates.push(1);
6703+
return coordinates;
6704+
}
66856705
function lineCentroid(coordinates) {
66866706
if (!(n = coordinates.length)) return null;
66876707
var n, point = projection(coordinates[0]), x0 = point[0], y0 = point[1], x1, y1, dx, dy, x = 0, y = 0, z = 0, i = 0, δ;
@@ -6696,7 +6716,7 @@
66966716
x0 = x1;
66976717
y0 = y1;
66986718
}
6699-
return [ x, y, z ];
6719+
return z ? [ x, y, z ] : null;
67006720
}
67016721
function polygonCentroid(coordinates) {
67026722
var polygon = d3.geom.polygon(coordinates[0].map(projection)), area = polygon.area(), centroid = polygon.centroid(area < 0 ? (area *= -1, 1) : -1), x = centroid[0], y = centroid[1], z = area, i = 0, n = coordinates.length;
@@ -6708,7 +6728,7 @@
67086728
y -= centroid[1];
67096729
z -= area;
67106730
}
6711-
return [ x, y, 6 * z ];
6731+
return z ? [ x, y, 6 * z ] : null;
67126732
}
67136733
var pointRadius = 4.5, pointCircle = d3_geo_pathCircle(pointRadius), projection = d3.geo.albersUsa(), buffer = [];
67146734
var bufferContext = {
@@ -6766,22 +6786,28 @@
67666786
return centroidType.geometry(feature.geometry);
67676787
},
67686788
FeatureCollection: function(collection) {
6769-
return d3.sum(collection.features, centroidType.Feature);
6789+
return centroidType.GeometryCollection({
6790+
geometries: collection.features.map(function(feature) {
6791+
return feature.geometry;
6792+
})
6793+
});
67706794
},
67716795
GeometryCollection: function(collection) {
6772-
return d3.sum(collection.geometries, centroidType.geometry);
6796+
var geometries = collection.geometries, dimensions = geometries.map(geometryDimension), dimension = d3.max(dimensions), coordinates = [];
6797+
for (var i = 0, n = geometries.length, o; i < n; i++) {
6798+
if (dimensions[i] !== dimension) continue;
6799+
o = geometries[i];
6800+
if (/^Multi/.test(o.type)) coordinates = coordinates.concat(o.coordinates); else coordinates.push(o.coordinates);
6801+
}
6802+
return coordinates.length ? centroidType["Multi" + (dimension === 0 ? "Point" : dimension === 1 ? "LineString" : "Polygon")]({
6803+
coordinates: coordinates
6804+
}) : null;
67736805
},
67746806
LineString: singleCentroid(lineCentroid),
67756807
MultiLineString: multiCentroid(lineCentroid),
6776-
MultiPoint: multiCentroid(function(coordinates) {
6777-
coordinates = projection(coordinates);
6778-
coordinates.push(1);
6779-
return coordinates;
6780-
}),
6808+
MultiPoint: multiCentroid(pointCentroid),
67816809
MultiPolygon: multiCentroid(polygonCentroid),
6782-
Point: function(point) {
6783-
return projection(point.coordinates);
6784-
},
6810+
Point: singleCentroid(pointCentroid),
67856811
Polygon: singleCentroid(polygonCentroid)
67866812
});
67876813
path.centroid = function(object) {

‎d3.min.js‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/geo/path.js‎

Lines changed: 49 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -55,24 +55,50 @@ d3.geo.path = function() {
5555

5656
var centroidType = d3_geo_type({
5757
Feature: function(feature) { return centroidType.geometry(feature.geometry); },
58-
FeatureCollection: function(collection) { return d3.sum(collection.features, centroidType.Feature); },
59-
GeometryCollection: function(collection) { return d3.sum(collection.geometries, centroidType.geometry); },
58+
FeatureCollection: function(collection) {
59+
return centroidType.GeometryCollection({geometries: collection.features.map(function(feature) { return feature.geometry; }) });
60+
},
61+
GeometryCollection: function(collection) {
62+
var geometries = collection.geometries,
63+
dimensions = geometries.map(geometryDimension),
64+
dimension = d3.max(dimensions),
65+
coordinates = [];
66+
for (var i = 0, n = geometries.length, o; i < n; i++) {
67+
if (dimensions[i] !== dimension) continue;
68+
o = geometries[i];
69+
if (/^Multi/.test(o.type)) coordinates = coordinates.concat(o.coordinates);
70+
else coordinates.push(o.coordinates);
71+
}
72+
return coordinates.length
73+
? centroidType["Multi" + (dimension === 0 ? "Point" : dimension === 1 ? "LineString" : "Polygon")]({coordinates: coordinates})
74+
: null;
75+
},
6076
LineString: singleCentroid(lineCentroid),
6177
MultiLineString: multiCentroid(lineCentroid),
62-
MultiPoint: multiCentroid(function(coordinates) {
63-
coordinates = projection(coordinates);
64-
coordinates.push(1);
65-
return coordinates;
66-
}),
78+
MultiPoint: multiCentroid(pointCentroid),
6779
MultiPolygon: multiCentroid(polygonCentroid),
68-
Point: function(point) { return projection(point.coordinates); },
80+
Point: singleCentroid(pointCentroid),
6981
Polygon: singleCentroid(polygonCentroid)
7082
});
7183

84+
function geometryDimension(o) {
85+
switch (o.type) {
86+
case "Point":
87+
case "MultiPoint":
88+
return 0;
89+
case "LineString":
90+
case "MultiLineString":
91+
return 1;
92+
case "Polygon":
93+
case "MultiPolygon":
94+
return 2;
95+
}
96+
}
97+
7298
function singleCentroid(weightedCentroid) {
7399
return function(o) {
74100
var centroid = weightedCentroid(o.coordinates);
75-
return [centroid[0] / centroid[2], centroid[1] / centroid[2]];
101+
return centroid ? [centroid[0] / centroid[2], centroid[1] / centroid[2]] : null;
76102
};
77103
}
78104

@@ -87,14 +113,22 @@ d3.geo.path = function() {
87113
n = coordinates.length;
88114
while (++i < n) {
89115
centroid = weightedCentroid(coordinates[i]);
90-
x += centroid[0];
91-
y += centroid[1];
92-
z += centroid[2];
116+
if (centroid != null) {
117+
x += centroid[0];
118+
y += centroid[1];
119+
z += centroid[2];
120+
}
93121
}
94-
return [x / z, y / z];
122+
return z ? [x / z, y / z] : null;
95123
}
96124
}
97125

126+
function pointCentroid(coordinates) {
127+
coordinates = projection(coordinates);
128+
coordinates.push(1);
129+
return coordinates;
130+
}
131+
98132
function lineCentroid(coordinates) {
99133
if (!(n = coordinates.length)) return null;
100134
var n,
@@ -121,7 +155,7 @@ d3.geo.path = function() {
121155
x0 = x1;
122156
y0 = y1;
123157
}
124-
return [x, y, z]; // weighted centroid
158+
return z ? [x, y, z] : null; // weighted centroid
125159
}
126160

127161
function polygonCentroid(coordinates) {
@@ -141,7 +175,7 @@ d3.geo.path = function() {
141175
y -= centroid[1];
142176
z -= area;
143177
}
144-
return [x, y, 6 * z]; // weighted centroid
178+
return z ? [x, y, 6 * z] : null; // weighted centroid
145179
}
146180

147181
path.centroid = function(object) { return centroidType.object(object); };

‎test/geo/path-test.js‎

Lines changed: 105 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -97,21 +97,113 @@ suite.addBatch({
9797
"Point": function(centroid) {
9898
assert.deepEqual(centroid({type: "Point", coordinates: [0, 0]}), [480, 250]);
9999
},
100-
"MultiPoint": function(centroid) {
101-
assert.deepEqual(centroid({type: "MultiPoint", coordinates: [[0, 0]]}), [480, 250]);
100+
"MultiPoint": {
101+
"empty": function(centroid) {
102+
assert.isNull(centroid({type: "MultiPoint", coordinates: []}));
103+
},
104+
"single point": function(centroid) {
105+
assert.deepEqual(centroid({type: "MultiPoint", coordinates: [[0, 0]]}), [480, 250]);
106+
},
107+
"two points": function(centroid) {
108+
assert.deepEqual(centroid({type: "MultiPoint", coordinates: [[-122, 37], [-74, 40]]}), [-10, 57.5]);
109+
}
102110
},
103-
"LineString": function(centroid) {
104-
assert.deepEqual(centroid({type: "LineString", coordinates: [[100, 0], [0, 0]]}), [730, 250]);
105-
assert.deepEqual(centroid({type: "LineString", coordinates: [[0, 0], [100, 0], [101, 0]]}), [732.5, 250]);
111+
"LineString": {
112+
"empty": function(centroid) {
113+
assert.isNull(centroid({type: "LineString", coordinates: []}));
114+
},
115+
"two points": function(centroid) {
116+
assert.deepEqual(centroid({type: "LineString", coordinates: [[100, 0], [0, 0]]}), [730, 250]);
117+
assert.deepEqual(centroid({type: "LineString", coordinates: [[0, 0], [100, 0], [101, 0]]}), [732.5, 250]);
118+
},
119+
"two points, one unique": function(centroid) {
120+
assert.isNull(centroid({type: "LineString", coordinates: [[-122, 37], [-122, 37]]}));
121+
assert.isNull(centroid({type: "LineString", coordinates: [[ -74, 40], [ -74, 40]]}));
122+
},
123+
"three points; two unique": function(centroid) {
124+
assert.deepEqual(centroid({type: "LineString", coordinates: [[-122, 37], [-74, 40], [-74, 40]]}), [-10, 57.5]);
125+
},
126+
"three points": function(centroid) {
127+
assert.inDelta(centroid({type: "LineString", coordinates: [[-122, 37], [-74, 40], [-100, 0]]}), [17.389135, 103.563545], 1e-6);
128+
}
106129
},
107130
"MultiLineString": function(centroid) {
108131
assert.deepEqual(centroid({type: "MultiLineString", coordinates: [[[100, 0], [0, 0]], [[-10, 0], [0, 0]]]}), [705, 250]);
109132
},
110-
"Polygon": function(centroid) {
111-
assert.deepEqual(centroid({type: "Polygon", coordinates: [[[100, 0], [101, 0], [101, 1], [100, 1], [100, 0]]]}), [982.5, 247.5]);
133+
"Polygon": {
134+
"single ring": function(centroid) {
135+
assert.deepEqual(centroid({type: "Polygon", coordinates: [[[100, 0], [101, 0], [101, 1], [100, 1], [100, 0]]]}), [982.5, 247.5]);
136+
},
137+
"zero area": function(centroid) {
138+
assert.isNull(centroid({type: "Polygon", coordinates: [[[1, 0], [2, 0], [3, 0], [1, 0]]]}));
139+
},
140+
"two rings, one zero area": function(centroid) {
141+
assert.deepEqual(centroid({type: "Polygon", coordinates: [[[100, 0], [101, 0], [101, 1], [100, 1], [100, 0]], [[100.1, 0], [100.2, 0], [100.3, 0], [100.1, 0]]]}), [982.5, 247.5]);
142+
}
143+
},
144+
"MultiPolygon": {
145+
"empty": function(centroid) {
146+
assert.isNull(centroid({type: "MultiPolygon", coordinates: []}));
147+
},
148+
"single polygon": function(centroid) {
149+
assert.deepEqual(centroid({type: "MultiPolygon", coordinates: [[[[100, 0], [101, 0], [101, 1], [100, 1], [100, 0]]]]}), [982.5, 247.5]);
150+
},
151+
"two polygons": function(centroid) {
152+
assert.deepEqual(centroid({type: "MultiPolygon", coordinates: [[[[100, 0], [101, 0], [101, 1], [100, 1], [100, 0]]], [[[0, 0], [1, 0], [1, -1], [0, -1], [0, 0]]]]}), [732.5, 250]);
153+
},
154+
"two polygons, one zero area": function(centroid) {
155+
assert.deepEqual(centroid({type: "MultiPolygon", coordinates: [[[[100, 0], [101, 0], [101, 1], [100, 1], [100, 0]]], [[[0, 0], [1, 0], [2, 0], [0, 0]]]]}), [982.5, 247.5]);
156+
}
157+
},
158+
"GeometryCollection": {
159+
"empty": function(centroid) {
160+
assert.isNull(centroid({type: "GeometryCollection", geometries: []}));
161+
},
162+
"collection containing an empty geometry": function(centroid) {
163+
assert.deepEqual(centroid({type: "GeometryCollection", geometries: [
164+
{type: "MultiPoint", coordinates: []},
165+
{type: "Point", coordinates: [-122, 37]}
166+
]}), [-130, 65]);
167+
},
168+
"ignores dimensions lower than one": function(centroid) {
169+
assert.deepEqual(centroid({type: "GeometryCollection", geometries: [
170+
{type: "Point", coordinates: [-122, 37]},
171+
{type: "MultiPoint", coordinates: [[-122, 37]]},
172+
{type: "LineString", coordinates: [[-122, 37], [-74, 40]]}
173+
]}), [-10, 57.5]);
174+
},
175+
"ignores dimensions lower than two": function(centroid) {
176+
assert.deepEqual(centroid({type: "GeometryCollection", geometries: [
177+
{type: "Point", coordinates: [-122, 37]},
178+
{type: "MultiPoint", coordinates: [[-122, 37]]},
179+
{type: "LineString", coordinates: [[-122, 37], [-74, 40]]},
180+
{type: "Polygon", coordinates: [[[100, 0], [101, 0], [101, 1], [100, 1], [100, 0]]]}
181+
]}), [982.5, 247.5]);
182+
},
183+
"empty higher dimensions": function(centroid) {
184+
assert.isNull(centroid({type: "GeometryCollection", geometries: [
185+
{type: "Point", coordinates: [-122, 37]},
186+
{type: "MultiPoint", coordinates: [[-122, 37]]},
187+
{type: "MultiLineString", coordinates: []}
188+
]}));
189+
}
112190
},
113-
"MultiPolygon": function(centroid) {
114-
assert.deepEqual(centroid({type: "MultiPolygon", coordinates: [[[[100, 0], [101, 0], [101, 1], [100, 1], [100, 0]]], [[[0, 0], [1, 0], [1, -1], [0, -1], [0, 0]]]]}), [732.5, 250]);
191+
"FeatureCollection": {
192+
"empty": function(centroid) {
193+
assert.isNull(centroid({type: "FeatureCollection", features: []}));
194+
},
195+
"collection containing a feature with an empty geometry": function(centroid) {
196+
assert.deepEqual(centroid({type: "FeatureCollection", features: [
197+
feature({type: "MultiPoint", coordinates: []}),
198+
feature({type: "Point", coordinates: [-122, 37]})
199+
]}), [-130, 65]);
200+
},
201+
"repeated geometries": function(centroid) {
202+
var lineString = {type: "LineString", coordinates: [[-122, 37], [-74, 40]]};
203+
assert.deepEqual(centroid({type: "FeatureCollection", features: [lineString].map(feature)}), [-10, 57.5]);
204+
assert.deepEqual(centroid({type: "FeatureCollection", features: [lineString, lineString].map(feature)}), [-10, 57.5]);
205+
assert.deepEqual(centroid({type: "FeatureCollection", features: [lineString, lineString, lineString].map(feature)}), [-10, 57.5]);
206+
}
115207
}
116208
}
117209
}
@@ -127,4 +219,8 @@ var testContext = {
127219
buffer: function() { var result = testBuffer; testBuffer = []; return result; }
128220
};
129221

222+
function feature(o) {
223+
return {type: "Feature", geometry: o};
224+
}
225+
130226
suite.export(module);

0 commit comments

Comments
 (0)