Skip to content

Commit 77aedd5

Browse files
jasondaviesmbostock
jasondavies
authored and
mbostock
committed
Enforce minimum sample interval for resampling.
The minimum sample interval is somewhat arbitrarily set to 16 × δ, where δ is the Douglas–Peucker threshold. This fixes cases where resampling stops too early due to the perpendicular distance being below the threshold; particularly for points that are far apart and whose great-circle arc is projected to an S-shape. The midpoint lies along a straight line, failing the Douglas–Peucker check, but further resampling produces an S-shape. Ideally, resampling should also detect cases where an intermediate point does not need to be drawn, i.e. where there truly is a straight line. This fix causes points to be drawn at the minimum sample interval, and thus may degrade performance slightly due to drawing redundant points. Fixes d3#1162.
1 parent e15ac86 commit 77aedd5

4 files changed

Lines changed: 30 additions & 9 deletions

File tree

‎d3.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2970,7 +2970,7 @@ d3 = function() {
29702970
var dx = x1 - x0, dy = y1 - y0, d2 = dx * dx + dy * dy;
29712971
if (d2 > 4 * δ2 && depth--) {
29722972
var a = a0 + a1, b = b0 + b1, c = c0 + c1, m = Math.sqrt(a * a + b * b + c * c), φ2 = Math.asin(c /= m), λ2 = Math.abs(Math.abs(c) - 1) < ε ? (λ0 + λ1) / 2 : Math.atan2(b, a), p = project(λ2, φ2), x2 = p[0], y2 = p[1], dx2 = x2 - x0, dy2 = y2 - y0, dz = dy * dx2 - dx * dy2;
2973-
if (dz * dz / d2 > δ2 || Math.abs((dx * dx2 + dy * dy2) / d2 - .5) > .3) {
2973+
if (dz * dz / d2 > δ2 || Math.abs((dx * dx2 + dy * dy2) / d2 - .5) > .3 || dx2 * dx2 + dy2 * dy2 > 256 * δ2) {
29742974
resampleLineTo(x0, y0, λ0, a0, b0, c0, x2, y2, λ2, a /= m, b /= m, c, depth, stream);
29752975
stream.point(x2, y2);
29762976
resampleLineTo(x2, y2, λ2, a, b, c, x1, y1, λ1, a1, b1, c1, depth, stream);

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -75,7 +75,7 @@ function d3_geo_resample(project) {
7575
dx2 = x2 - x0,
7676
dy2 = y2 - y0,
7777
dz = dy * dx2 - dx * dy2;
78-
if (dz * dz / d2 > δ2 || Math.abs((dx * dx2 + dy * dy2) / d2 - .5) > .3) {
78+
if (dz * dz / d2 > δ2 || Math.abs((dx * dx2 + dy * dy2) / d2 - .5) > .3 || dx2 * dx2 + dy2 * dy2 > 256 * δ2) {
7979
resampleLineTo(x0, y0, λ0, a0, b0, c0, x2, y2, λ2, a /= m, b /= m, c, depth, stream);
8080
stream.point(x2, y2);
8181
resampleLineTo(x2, y2, λ2, a, b, c, x1, y1, λ1, a1, b1, c1, depth, stream);

‎test/geo/path-test.js‎

Lines changed: 27 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -287,14 +287,16 @@ suite.addBatch({
287287
},
288288
"area of a polygon": function(p) {
289289
var area = p.area({type: "Polygon", coordinates: [[[-122, 37], [-71, 42], [-80, 25], [-122, 37]]]});
290-
assert.inDelta(area, 124884.274, 1e-3);
290+
assert.inDelta(area, 125257.618, 1e-3);
291291
},
292292
"bounds of a line string": function(p) {
293293
assert.inDelta(p.bounds({type: "LineString", coordinates: [[-122, 37], [-74, 40], [-100, 0]]}),
294294
[[109.378, 189.584], [797.758, 504.660]], 1e-3);
295295
},
296296
"centroid of a line string": function(p) {
297-
assert.inDelta(p.centroid({type: "LineString", coordinates: [[-122, 37], [-74, 40], [-100, 0]]}), [545.130, 253.859], 1e-3);
297+
var centroid = p.centroid({type: "LineString", coordinates: [[-122, 37], [-74, 40], [-100, 0]]});
298+
assert.inDelta(centroid[0], 545.169, 1e-3);
299+
assert.inDelta(centroid[1], 253.753, 1e-3);
298300
}
299301
},
300302

@@ -757,19 +759,38 @@ suite.addBatch({
757759
},
758760

759761
"with an Albers projection and adaptive resampling": {
760-
topic: function(path) {
761-
return path()
762+
"correctly resamples near the poles": function(path) {
763+
var p = path()
762764
.context(testContext)
763765
.projection(_.geo.albers()
764766
.scale(140)
765767
.rotate([0, 0])
766768
.precision(1));
767-
},
768-
"correctly resamples near the poles": function(p) {
769769
p({type: "LineString", coordinates: [[0, 88], [180, 89]]});
770770
assert.isTrue(testContext.buffer().filter(function(d) { return d.type === "lineTo"; }).length > 1);
771771
p({type: "LineString", coordinates: [[180, 90], [1, 89.5]]});
772772
assert.isTrue(testContext.buffer().filter(function(d) { return d.type === "lineTo"; }).length > 1);
773+
},
774+
"rotate([11.5, 285])": function(path) {
775+
var p = path()
776+
.context(testContext)
777+
.projection(_.geo.albers()
778+
.scale(140)
779+
.rotate([11.5, 285])
780+
.precision(1));
781+
p({type: "LineString", coordinates: [[170, 20], [170, 0]]});
782+
assert.isTrue(testContext.buffer().filter(function(d) { return d.type === "lineTo"; }).length > 1);
783+
},
784+
"wavy projection": function(path) {
785+
var p = path()
786+
.context(testContext)
787+
.projection(_.geo.projection(function(λ, φ) {
788+
return [λ, Math.sin(λ * 4)];
789+
})
790+
.scale(140)
791+
.precision(1));
792+
p({type: "LineString", coordinates: [[-45, 0], [45, 0]]});
793+
assert.isTrue(testContext.buffer().filter(function(d) { return d.type === "lineTo"; }).length > 1);
773794
}
774795
},
775796

0 commit comments

Comments
 (0)