Skip to content

Commit 5396d39

Browse files
jasondaviesjasondavies
committed
Fix CCW polygon detection issue.
The south pole rotation could result in line segments that go through the poles. These are characterised by a 180° longitudinal difference. These cases were not handled properly by the approximation algorithm, but it now handles both north and south pole cases.
1 parent 4dd25f7 commit 5396d39

4 files changed

Lines changed: 36 additions & 7 deletions

File tree

‎d3.js‎

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5928,14 +5928,17 @@
59285928
}
59295929
function d3_geo_clipAreaRing(ring, invisible) {
59305930
if (!(n = ring.length)) return 0;
5931-
var n, i = 0, area = 0, p = ring[0], λ = p[0], φ = p[1], cosφ = Math.cos(φ), x0 = Math.atan2(invisible * Math.sin(λ) * cosφ, Math.sin(φ)), y0 = 1 - invisible * Math.cos(λ) * cosφ, x, y;
5931+
var n, i = 0, area = 0, p = ring[0], λ = p[0], φ = p[1], cosφ = Math.cos(φ), x0 = Math.atan2(invisible * Math.sin(λ) * cosφ, Math.sin(φ)), y0 = 1 - invisible * Math.cos(λ) * cosφ, x1 = x0, x, y;
59325932
while (++i < n) {
59335933
p = ring[i];
59345934
cosφ = Math.cos(φ = p[1]);
59355935
x = Math.atan2(invisible * Math.sin(λ = p[0]) * cosφ, Math.sin(φ));
59365936
y = 1 - invisible * Math.cos(λ) * cosφ;
5937-
if (Math.abs(y) < ε || Math.abs(y0) < ε) {} else if (Math.abs(y0 - 2) < ε) area += 4 * (x - x0); else area += ((3 * π + x - x0) % (2 * π) - π) * (y0 + y);
5938-
x0 = x, y0 = y;
5937+
if (Math.abs(y0 - 2) < ε && Math.abs(y - 2) < ε) continue;
5938+
if (Math.abs(y) < ε || Math.abs(y0) < ε) {} else if (Math.abs(Math.abs(x - x0) - π) < ε) {
5939+
if (y + y0 > 2) area += 4 * (x - x0);
5940+
} else if (Math.abs(y0 - 2) < ε) area += 4 * (x - x1); else area += ((3 * π + x - x0) % (2 * π) - π) * (y0 + y);
5941+
x1 = x0, x0 = x, y0 = y;
59395942
}
59405943
return area;
59415944
}

‎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/clip.js‎

Lines changed: 17 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -228,24 +228,38 @@ function d3_geo_clipAreaRing(ring, invisible) {
228228
cosφ = Math.cos(φ),
229229
x0 = Math.atan2(invisible * Math.sin(λ) * cosφ, Math.sin(φ)),
230230
y0 = 1 - invisible * Math.cos(λ) * cosφ,
231+
x1 = x0,
231232
x, // λ'; λ rotated to south pole.
232233
y; // φ' = 1 + sin(φ); φ rotated to south pole.
233234
while (++i < n) {
234235
p = ring[i];
235236
cosφ = Math.cos(φ = p[1]);
236237
x = Math.atan2(invisible * Math.sin(λ = p[0]) * cosφ, Math.sin(φ));
237238
y = 1 - invisible * Math.cos(λ) * cosφ;
238-
// If this or the previous point is at the south pole, the area is 0.
239+
240+
// If both the current point and the previous point are at the north pole,
241+
// skip this point.
242+
if (Math.abs(y0 - 2) < ε && Math.abs(y - 2) < ε) continue;
243+
244+
// If this or the previous point is at the south pole, or if this segment
245+
// goes through the south pole, the area is 0.
239246
if (Math.abs(y) < ε || Math.abs(y0) < ε) {}
240247

248+
// If this segment goes through either pole…
249+
else if (Math.abs(Math.abs(x - x0) - π) < ε) {
250+
// For the north pole, compute lune area.
251+
if (y + y0 > 2) area += 4 * (x - x0);
252+
// For the south pole, the area is zero.
253+
}
254+
241255
// If the previous point is at the north pole, then compute lune area.
242-
else if (Math.abs(y0 - 2) < ε) area += 4 * (x - x0);
256+
else if (Math.abs(y0 - 2) < ε) area += 4 * (x - x1);
243257

244258
// Otherwise, the spherical triangle area is approximately
245259
// δλ * (1 + sinφ0 + 1 + sinφ) / 2.
246260
else area += ((3 * π + x - x0) % (2 * π) - π) * (y0 + y);
247261

248-
x0 = x, y0 = y;
262+
x1 = x0, x0 = x, y0 = y;
249263
}
250264
return area;
251265
}

‎test/geo/path-test.js‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,18 @@ suite.addBatch({
8989
]);
9090
},
9191

92+
"winding order": {
93+
"tiny polygon": function(path) {
94+
path({type: "Polygon", coordinates: [[
95+
[-0.06904102953339501, 0.346043661846373],
96+
[-6.725674252975136e-15, 0.3981303360336475],
97+
[-6.742247658534323e-15, -0.08812465346531581],
98+
[-0.17301258217724075, -0.12278150669440671],
99+
[-0.06904102953339501, 0.346043661846373]]]});
100+
assert.equal(testContext.buffer().filter(function(d) { return d.type === "moveTo"; }).length, 1);
101+
}
102+
},
103+
92104
"with no context": {
93105
topic: function(path) {
94106
return d3.geo.path().projection(path.projection());

0 commit comments

Comments
 (0)