Skip to content

Commit 37f64b7

Browse files
jasondaviesjasondavies
committed
Fix streaming polygon clipping.
1 parent 604c57d commit 37f64b7

13 files changed

Lines changed: 262 additions & 155 deletions

File tree

‎Makefile‎

Lines changed: 0 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -181,9 +181,6 @@ d3.layout.js: \
181181
d3.geo.js: \
182182
src/geo/geo.js \
183183
src/geo/stream.js \
184-
src/geo/stream-radians.js \
185-
src/geo/stream-rotate.js \
186-
src/geo/stream-transform.js \
187184
src/geo/spherical.js \
188185
src/geo/cartesian.js \
189186
src/geo/type.js \

‎d3.js‎

Lines changed: 112 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -5397,32 +5397,11 @@
53975397
while (++i < n) d3_geo_streamLine(coordinates[i], listener, 1);
53985398
listener.polygonEnd();
53995399
}
5400-
function d3_geo_streamRadians(stream) {
5401-
return d3_geo_streamTransform(stream, function(x, y) {
5402-
stream.point(x * d3_radians, y * d3_radians);
5403-
});
5404-
}
5405-
function d3_geo_streamRotate(rotate, stream) {
5406-
return d3_geo_streamTransform(stream, function(x, y) {
5407-
x = rotate(x, y);
5408-
stream.point(x[0], x[1]);
5409-
});
5410-
}
5411-
function d3_geo_streamTransform(stream, point) {
5412-
return {
5413-
point: point,
5414-
sphere: stream.sphere,
5415-
lineStart: stream.lineStart,
5416-
lineEnd: stream.lineEnd,
5417-
polygonStart: stream.polygonStart,
5418-
polygonEnd: stream.polygonEnd
5419-
};
5420-
}
54215400
function d3_geo_spherical(cartesian) {
54225401
return [ Math.atan2(cartesian[1], cartesian[0]), Math.asin(Math.max(-1, Math.min(1, cartesian[2]))) ];
54235402
}
54245403
function d3_geo_sphericalEqual(a, b) {
5425-
return !a || Math.abs(a[0] - b[0]) < ε && Math.abs(a[1] - b[1]) < ε;
5404+
return Math.abs(a[0] - b[0]) < ε && Math.abs(a[1] - b[1]) < ε;
54265405
}
54275406
function d3_geo_cartesian(spherical) {
54285407
var λ = spherical[0], φ = spherical[1], cosφ = Math.cos(φ);
@@ -5528,7 +5507,7 @@
55285507
};
55295508
function d3_geo_clip(pointVisible, clipLine, interpolate) {
55305509
return function(listener) {
5531-
var line = clipLine(listener);
5510+
var line = clipLine(listener), polygon = [], ring;
55325511
var clip = {
55335512
point: point,
55345513
lineStart: lineStart,
@@ -5539,7 +5518,6 @@
55395518
clip.lineEnd = d3_noop;
55405519
},
55415520
polygonEnd: function() {
5542-
return;
55435521
clip.point = point;
55445522
clip.lineStart = lineStart;
55455523
clip.lineEnd = lineEnd;
@@ -5577,28 +5555,38 @@
55775555
polygon.push(ring = []);
55785556
}
55795557
};
5580-
var subject = [], clip = [], segments = [], visibleArea = 0, invisibleArea = 0, invisible = false;
5558+
}
5559+
function d3_geo_clipPolygon(polygon, clipRing, interpolate, listener) {
5560+
var subject = [], clip = [], segments = [], visibleArea = 0, invisibleArea = 0, invisible = false, buffer = d3_geo_clipBufferListener(), ringListener = clipRing(buffer);
5561+
listener.polygonStart();
55815562
var segments = d3.merge(polygon.map(function(ring) {
5582-
var x = clipRing(ring, bufferListener), ringSegments = x[1], segment, n = ringSegments.length;
5563+
ringListener.lineStart();
5564+
ring.forEach(function(point) {
5565+
ringListener.point(point[0], point[1]);
5566+
});
5567+
ringListener.lineEnd();
5568+
var clean = ringListener.clean(), ringSegments = buffer.buffer(), segment, n = ringSegments.length;
55835569
if (!n) {
55845570
invisible = true;
5585-
invisibleArea += d3_geo_areaRing(ring.map(d3_geo_clipRotationInvisible));
5571+
invisibleArea += d3_geo_clipAreaRing(ring, d3_geo_clipRotationInvisible);
55865572
return [];
55875573
}
5588-
if (x[0] & 1) {
5574+
if (clean & 1) {
55895575
segment = ringSegments[0];
5590-
visibleArea += d3_geo_areaRing(segment.map(d3_geo_clipRotation));
5591-
var n = segment.length - 1, i = -1, point;
5576+
visibleArea += d3_geo_clipAreaRing(segment, d3_geo_clipRotation);
5577+
var n = segment.length, i = -1, point;
55925578
listener.lineStart();
55935579
while (++i < n) listener.point((point = segment[i])[0], point[1]);
55945580
listener.lineEnd();
55955581
return [];
55965582
}
5597-
if (n > 1 && x[0] & 2) ringSegments.push(ringSegments.pop().concat(ringSegments.shift()));
5583+
if (n > 1 && clean & 2) ringSegments.push(ringSegments.pop().concat(ringSegments.shift()));
55985584
return ringSegments.filter(d3_geo_clipSegmentLength1);
55995585
}));
56005586
if (!segments.length && (visibleArea < -ε2 || invisible && invisibleArea < -ε2)) {
5587+
listener.lineStart();
56015588
interpolate(null, null, 1, listener);
5589+
listener.lineEnd();
56025590
}
56035591
segments.forEach(function(segment) {
56045592
var n = segment.length;
@@ -5644,8 +5632,8 @@
56445632
clip.sort(d3_geo_clipSort);
56455633
d3_geo_clipLinkCircular(subject);
56465634
d3_geo_clipLinkCircular(clip);
5647-
if (!subject.length) return;
5648-
var start = subject[0], current, points;
5635+
if (!subject.length) return listener.polygonEnd();
5636+
var start = subject[0], current, points, point;
56495637
while (1) {
56505638
current = start;
56515639
while (current.visited) if ((current = current.next) === start) return listener.polygonEnd();
@@ -5676,15 +5664,6 @@
56765664
}
56775665
listener.polygonEnd();
56785666
}
5679-
function d3_geo_clipPolygon(polygon, clipRing, interpolate, listener) {}
5680-
function d3_geo_clipRotation(point) {
5681-
var λ = point[0], φ = point[1], cosφ = Math.cos(φ);
5682-
return [ Math.atan2(Math.sin(λ) * cosφ, Math.sin(φ)), Math.asin(Math.max(-1, Math.min(1, -Math.cos(λ) * cosφ))) ];
5683-
}
5684-
function d3_geo_clipRotationInvisible(point) {
5685-
var λ = point[0] + π, φ = point[1], cosφ = Math.cos(φ);
5686-
return [ Math.atan2(Math.sin(λ) * cosφ, Math.sin(φ)), Math.asin(Math.max(-1, Math.min(1, -Math.cos(λ) * cosφ))) ];
5687-
}
56885667
function d3_geo_clipLinkCircular(array) {
56895668
if (!(n = array.length)) return;
56905669
var n, i = 0, a = array[0], b;
@@ -5702,12 +5681,50 @@
57025681
function d3_geo_clipSegmentLength1(segment) {
57035682
return segment.length > 1;
57045683
}
5705-
var d3_geo_cut = d3_geo_clip(d3_identity, d3_geo_cutLine, d3_geo_cutInterpolate);
5684+
function d3_geo_clipBufferListener() {
5685+
var lines = [], line;
5686+
return {
5687+
lineStart: function() {
5688+
lines.push(line = []);
5689+
},
5690+
point: function(λ, φ) {
5691+
line.push([ λ, φ ]);
5692+
},
5693+
lineEnd: d3_noop,
5694+
buffer: function() {
5695+
var buffer = lines;
5696+
lines = [];
5697+
line = null;
5698+
return buffer;
5699+
}
5700+
};
5701+
}
5702+
function d3_geo_clipAreaRing(ring, rotate) {
5703+
d3_geo_area.polygonStart();
5704+
d3_geo_area.lineStart();
5705+
for (var i = 0, n = ring.length, p; i < n; ++i) {
5706+
p = rotate(ring[i]);
5707+
d3_geo_area.point(p[0] * d3_degrees, p[1] * d3_degrees);
5708+
}
5709+
d3_geo_area.lineEnd();
5710+
d3_geo_area.polygonEnd();
5711+
return d3_geo_areaRing;
5712+
}
5713+
function d3_geo_clipRotation(point) {
5714+
var λ = point[0], φ = point[1], cosφ = Math.cos(φ);
5715+
return [ Math.atan2(Math.sin(λ) * cosφ, Math.sin(φ)), Math.asin(Math.max(-1, Math.min(1, -Math.cos(λ) * cosφ))) ];
5716+
}
5717+
function d3_geo_clipRotationInvisible(point) {
5718+
var λ = point[0] + π, φ = point[1], cosφ = Math.cos(φ);
5719+
return [ Math.atan2(Math.sin(λ) * cosφ, Math.sin(φ)), Math.asin(Math.max(-1, Math.min(1, -Math.cos(λ) * cosφ))) ];
5720+
}
5721+
var d3_geo_cut = d3_geo_clip(d3_true, d3_geo_cutLine, d3_geo_cutInterpolate);
57065722
function d3_geo_cutLine(listener) {
5707-
var λ0 = NaN, φ0 = NaN, sλ0 = NaN, clean = 1;
5723+
var λ0 = NaN, φ0 = NaN, sλ0 = NaN, clean;
57085724
return {
57095725
lineStart: function() {
57105726
listener.lineStart();
5727+
clean = 1;
57115728
},
57125729
point: function(λ1, φ1) {
57135730
var sλ1 = λ1 > 0 ? π : -π, dλ = Math.abs(λ1 - λ0);
@@ -5733,8 +5750,11 @@
57335750
sλ0 = sλ1;
57345751
},
57355752
lineEnd: function() {
5736-
λ0 = φ0 = NaN;
57375753
listener.lineEnd();
5754+
λ0 = φ0 = NaN;
5755+
},
5756+
clean: function() {
5757+
return 2 - clean;
57385758
}
57395759
};
57405760
}
@@ -5779,8 +5799,12 @@
57795799
resample.point = resamplePoint;
57805800
listener.lineEnd();
57815801
},
5782-
polygonStart: d3_noop,
5783-
polygonEnd: d3_noop
5802+
polygonStart: function() {
5803+
listener.polygonStart();
5804+
},
5805+
polygonEnd: function() {
5806+
listener.polygonEnd();
5807+
}
57845808
};
57855809
function resamplePoint(λ, φ) {
57865810
var point = projectPoint(λ, φ);
@@ -6032,22 +6056,25 @@
60326056
function d3_geo_circleClip(degrees) {
60336057
var radians = degrees * d3_radians, cr = Math.cos(radians), interpolate = d3_geo_circleInterpolate(radians, 6 * d3_radians);
60346058
return d3_geo_clip(visible, clipLine, interpolate);
6035-
function visible(point) {
6036-
return Math.cos(point[1]) * Math.cos(point[0]) > cr;
6059+
function visible(λ, φ) {
6060+
return Math.cos(λ) * Math.cos(φ) > cr;
60376061
}
60386062
function clipLine(listener) {
6039-
var point0, v0 = false, v00 = false, clean = 1;
6063+
var point0, v0, v00, clean;
60406064
return {
6041-
lineStart: d3_noop,
6065+
lineStart: function() {
6066+
v00 = v0 = false;
6067+
clean = 1;
6068+
},
60426069
point: function(λ, φ) {
6043-
var point1 = [ λ, φ ], point2, v = visible(point1);
6070+
var point1 = [ λ, φ ], point2, v = visible(λ, φ);
60446071
if (!point0 && (v00 = v0 = v)) listener.lineStart();
60456072
if (v !== v0) {
60466073
point2 = intersect(point0, point1);
60476074
if (d3_geo_sphericalEqual(point0, point2) || d3_geo_sphericalEqual(point1, point2)) {
60486075
point1[0] += ε;
60496076
point1[1] += ε;
6050-
v = visible(point1);
6077+
v = visible(point1[0], point1[1]);
60516078
}
60526079
}
60536080
if (v !== v0) {
@@ -6063,14 +6090,15 @@
60636090
}
60646091
point0 = point2;
60656092
}
6066-
if (v && !d3_geo_sphericalEqual(point0, point1)) listener.point(point1[0], point1[1]);
6093+
if (v && (!point0 || !d3_geo_sphericalEqual(point0, point1))) listener.point(point1[0], point1[1]);
60676094
point0 = point1;
60686095
},
60696096
lineEnd: function() {
60706097
if (v0) listener.lineEnd();
6071-
v0 = v00 = false;
60726098
point0 = null;
6073-
clean = 1;
6099+
},
6100+
clean: function() {
6101+
return clean | (v00 && v0) << 1;
60746102
}
60756103
};
60766104
}
@@ -6260,6 +6288,7 @@
62606288
d3.geo.path = function() {
62616289
var pointRadius = 4.5, pointCircle = d3_geo_pathCircle(pointRadius), projection = d3.geo.albersUsa(), context, buffer = [];
62626290
function path(object) {
6291+
if (object == null) return;
62636292
var radius = typeof pointRadius === "function" ? pointRadius.apply(this, arguments) : pointRadius;
62646293
d3.geo.stream(object, projection.stream(context == null ? new d3_geo_pathBuffer(buffer, radius) : new d3_geo_pathContext(context, radius)));
62656294
if (buffer.length) {
@@ -6439,7 +6468,7 @@
64396468
x00 = x0 = x, y00 = y0 = y;
64406469
};
64416470
function nextPoint(x, y) {
6442-
var dx = x - x0, dy = y - y0, z = y0 * x - x0 * y;
6471+
var z = y0 * x - x0 * y;
64436472
d3_geo_centroidX += z * (x0 + x);
64446473
d3_geo_centroidY += z * (y0 + y);
64456474
d3_geo_centroidZ += z * 3;
@@ -6472,7 +6501,7 @@
64726501
}
64736502
};
64746503
function d3_geo_areaRingStart() {
6475-
var λ00, φ00, λ1, λ0, φ0, cosφ0, sinφ0;
6504+
var λ00, φ00, λ1, φ1, λ0, φ0, cosφ0, sinφ0;
64766505
d3_geo_area.point = function(λ, φ) {
64776506
d3_geo_area.point = nextPoint;
64786507
λ1 = λ0 = (λ00 = λ) * d3_radians, φ0 = (φ00 = φ) * d3_radians, cosφ0 = Math.cos(φ0),
@@ -6500,7 +6529,7 @@
65006529
})();
65016530
}
65026531
function d3_geo_projectionMutator(projectAt) {
6503-
var project, projectRotate, k = 150, x = 480, y = 250, λ = 0, φ = 0, δλ = 0, δφ = 0, δγ = 0, δx, δy, clip = d3_geo_cut, clipAngle = null, projectResample = d3_geo_resample(projectPoint);
6532+
var project, projectRotate, rotate, k = 150, x = 480, y = 250, λ = 0, φ = 0, δλ = 0, δφ = 0, δγ = 0, δx, δy, clip = d3_geo_cut, clipAngle = null, projectResample = d3_geo_resample(projectPoint);
65046533
function projection(coordinates) {
65056534
coordinates = projectRotate(coordinates[0] * d3_radians, coordinates[1] * d3_radians);
65066535
return [ coordinates[0] * k + δx, δy - coordinates[1] * k ];
@@ -6510,7 +6539,7 @@
65106539
return [ coordinates[0] * d3_degrees, coordinates[1] * d3_degrees ];
65116540
}
65126541
projection.stream = function(listener) {
6513-
return d3_geo_streamRadians(d3_geo_streamRotate(rotate, clip(projectResample(listener))));
6542+
return d3_geo_projectionRadiansRotate(rotate, clip(projectResample(listener)));
65146543
};
65156544
projection.clipAngle = function(_) {
65166545
if (!arguments.length) return clipAngle;
@@ -6559,6 +6588,29 @@
65596588
return reset();
65606589
};
65616590
}
6591+
function d3_geo_projectionRadiansRotate(rotate, stream) {
6592+
return {
6593+
point: function(λ, φ) {
6594+
var p = rotate(λ * d3_radians, φ * d3_radians);
6595+
stream.point(p[0], p[1]);
6596+
},
6597+
sphere: function() {
6598+
stream.sphere();
6599+
},
6600+
lineStart: function() {
6601+
stream.lineStart();
6602+
},
6603+
lineEnd: function() {
6604+
stream.lineEnd();
6605+
},
6606+
polygonStart: function() {
6607+
stream.polygonStart();
6608+
},
6609+
polygonEnd: function() {
6610+
stream.polygonEnd();
6611+
}
6612+
};
6613+
}
65626614
function d3_geo_rotation(δλ, δφ, δγ) {
65636615
return δλ ? δφ || δγ ? d3_geo_compose(d3_geo_rotationλ(δλ), d3_geo_rotationφγ(δφ, δγ)) : d3_geo_rotationλ(δλ) : δφ || δγ ? d3_geo_rotationφγ(δφ, δγ) : d3_geo_identityRotation;
65646616
}

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,7 @@ var d3_geo_area = {
2525
};
2626

2727
function d3_geo_areaRingStart() {
28-
var λ00, φ00, λ1, λ0, φ0, cosφ0, sinφ0; // start point and two previous points
28+
var λ00, φ00, λ1, φ1, λ0, φ0, cosφ0, sinφ0; // start point and two previous points
2929

3030
// For the first point, …
3131
d3_geo_area.point = function(λ, φ) {
@@ -41,7 +41,7 @@ function d3_geo_areaRingStart() {
4141
if (Math.abs(Math.abs(φ0) - π / 2) < ε && Math.abs(Math.abs(φ) - π / 2) < ε) return;
4242
var cosφ = Math.cos(φ), sinφ = Math.sin(φ);
4343

44-
// If the previous point is at the south pole, something involving lunes…
44+
// If the previous point is at the north pole, then compute lune area.
4545
if (Math.abs(φ0 - π / 2) < ε) d3_geo_areaRing += (λ - λ1) * 2;
4646

4747
// TODO Explain this wonderous mathematics.

0 commit comments

Comments
 (0)