Skip to content

Commit 5596e4f

Browse files
mbostockmbostock
committed
Standardize on open polygons. Fixes d3#443.
If you try to create a d3.geom.polygon with a closed polygon, it is now automatically converted to an open polygon by stripping the closing coordinate.
1 parent 673c630 commit 5596e4f

2 files changed

Lines changed: 67 additions & 11 deletions

File tree

‎src/geom/polygon.js‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
import "geom";
22

3+
// Note: removes the closing coordinate if the polygon is not already open.
34
d3.geom.polygon = function(coordinates) {
5+
d3_geom_polygonOpen(coordinates);
46

57
coordinates.area = function() {
68
var i = -1,
@@ -36,7 +38,7 @@ d3.geom.polygon = function(coordinates) {
3638
};
3739

3840
// The Sutherland-Hodgman clipping algorithm.
39-
// Note: requires the clip polygon to be counterclockwise and convex.
41+
// Note: requires the clip polygon to be open, counterclockwise and convex.
4042
coordinates.clip = function(subject) {
4143
var input,
4244
i = -1,
@@ -84,3 +86,10 @@ function d3_geom_polygonIntersect(c, d, a, b) {
8486
ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
8587
return [x1 + ua * x21, y1 + ua * y21];
8688
}
89+
90+
// If coordinates is not open, removes the closing point.
91+
function d3_geom_polygonOpen(coordinates) {
92+
var a = coordinates[0],
93+
b = coordinates[coordinates.length - 1];
94+
if (!(a[0] - b[0] || a[1] - b[1])) coordinates.pop();
95+
}

‎test/geom/polygon-test.js‎

Lines changed: 57 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -12,70 +12,99 @@ suite.addBatch({
1212
topic: function(polygon) {
1313
return polygon([[0, 0], [0, 1], [1, 1], [1, 0], [0, 0]]);
1414
},
15+
"is converted to an open polygon": function(p) {
16+
assertPolygonInDelta(p, [[0, 0], [0, 1], [1, 1], [1, 0]]);
17+
},
1518
"has area 1": function(p) {
1619
assert.equal(p.area(), 1);
1720
},
1821
"has centroid ⟨.5,.5⟩": function(p) {
19-
assert.deepEqual(p.centroid(), [.5, .5]);
22+
assertPointInDelta(p.centroid(), [.5, .5]);
23+
},
24+
"can clip an open counterclockwise triangle": function(p) {
25+
assertPolygonInDelta(p.clip([[0.9, 0.5], [2, -1], [0.5, 0.1]]), [[0.9, 0.5], [1, 0.363636], [1, 0], [0.636363, 0], [0.5, 0.1]], 1e-4);
2026
}
2127
},
2228
"closed clockwise unit square": {
2329
topic: function(polygon) {
2430
return polygon([[0, 0], [1, 0], [1, 1], [0, 1], [0, 0]]);
2531
},
32+
"is converted to an open polygon": function(p) {
33+
assertPolygonInDelta(p, [[0, 0], [1, 0], [1, 1], [0, 1]]);
34+
},
2635
"has area 1": function(p) {
2736
assert.equal(p.area(), -1);
2837
},
2938
"has centroid ⟨.5,.5⟩": function(p) {
30-
assert.deepEqual(p.centroid(), [.5, .5]);
39+
assertPointInDelta(p.centroid(), [.5, .5]);
40+
},
41+
"is not currently supported for clipping": function(p) {
42+
// because clipping requires a counterclockwise source polygon
3143
}
3244
},
3345
"closed clockwise triangle": {
3446
topic: function(polygon) {
3547
return polygon([[1, 1], [3, 2], [2, 3], [1, 1]]);
3648
},
49+
"is converted to an open polygon": function(p) {
50+
assertPolygonInDelta(p, [[1, 1], [3, 2], [2, 3]]);
51+
},
3752
"has area 1.5": function(p) {
3853
assert.equal(p.area(), -1.5);
3954
},
4055
"has centroid ⟨2,2⟩": function(p) {
41-
var centroid = p.centroid();
42-
assert.inDelta(centroid[0], 2, 1e-6);
43-
assert.inDelta(centroid[1], 2, 1e-6);
56+
assertPointInDelta(p.centroid(), [2, 2]);
57+
},
58+
"is not currently supported for clipping": function(p) {
59+
// because clipping requires a counterclockwise source polygon
4460
}
4561
},
4662
"open counterclockwise unit square": {
4763
topic: function(polygon) {
4864
return polygon([[0, 0], [0, 1], [1, 1], [1, 0]]);
4965
},
66+
"remains an open polygon": function(p) {
67+
assertPolygonInDelta(p, [[0, 0], [0, 1], [1, 1], [1, 0]]);
68+
},
5069
"has area 1": function(p) {
5170
assert.equal(p.area(), 1);
5271
},
5372
"has centroid ⟨.5,.5⟩": function(p) {
54-
assert.deepEqual(p.centroid(), [.5, .5]);
73+
assertPointInDelta(p.centroid(), [.5, .5]);
74+
},
75+
"can clip an open counterclockwise triangle": function(p) {
76+
assertPolygonInDelta(p.clip([[0.9, 0.5], [2, -1], [0.5, 0.1]]), [[0.9, 0.5], [1, 0.363636], [1, 0], [0.636363, 0], [0.5, 0.1]], 1e-4);
5577
}
5678
},
5779
"open clockwise unit square": {
5880
topic: function(polygon) {
5981
return polygon([[0, 0], [1, 0], [1, 1], [0, 1]]);
6082
},
83+
"remains an open polygon": function(p) {
84+
assertPolygonInDelta(p, [[0, 0], [1, 0], [1, 1], [0, 1]]);
85+
},
6186
"has area 1": function(p) {
6287
assert.equal(p.area(), -1);
6388
},
6489
"has centroid ⟨.5,.5⟩": function(p) {
65-
assert.deepEqual(p.centroid(), [.5, .5]);
90+
assertPointInDelta(p.centroid(), [.5, .5]);
91+
},
92+
"is not currently supported for clipping": function(p) {
93+
// because clipping requires a counterclockwise source polygon
6694
}
6795
},
6896
"open clockwise triangle": {
6997
topic: function(polygon) {
7098
return polygon([[1, 1], [3, 2], [2, 3]]);
7199
},
100+
"remains an open polygon": function(p) {
101+
assertPolygonInDelta(p, [[1, 1], [3, 2], [2, 3]]);
102+
},
72103
"has area 1.5": function(p) {
73104
assert.equal(p.area(), -1.5);
74105
},
75106
"has centroid ⟨2,2⟩": function(p) {
76-
var centroid = p.centroid();
77-
assert.inDelta(centroid[0], 2, 1e-6);
78-
assert.inDelta(centroid[1], 2, 1e-6);
107+
assertPointInDelta(p.centroid(), [2, 2]);
79108
}
80109
},
81110
"large square": {
@@ -95,4 +124,22 @@ suite.addBatch({
95124
}
96125
});
97126

127+
function assertPointInDelta(expected, actual, δ, message) {
128+
if (!δ) δ = 0;
129+
if (!pointInDelta(expected, actual, δ)) {
130+
assert.fail(JSON.stringify(actual), JSON.stringify(expected), message || "expected {expected}, got {actual}", "===", assertPointInDelta);
131+
}
132+
}
133+
134+
function assertPolygonInDelta(expected, actual, δ, message) {
135+
if (!δ) δ = 0;
136+
if (expected.length !== actual.length || expected.some(function(e, i) { return !pointInDelta(e, actual[i], δ); })) {
137+
assert.fail(JSON.stringify(actual), JSON.stringify(expected), message || "expected {expected}, got {actual}", "===", assertPolygonInDelta);
138+
}
139+
}
140+
141+
function pointInDelta(a, b, δ) {
142+
return !(Math.abs(a[0] - b[0]) > δ || Math.abs(a[1] - b[1]) > δ);
143+
}
144+
98145
suite.export(module);

0 commit comments

Comments
 (0)