Skip to content

Commit d93f45e

Browse files
jasondaviesjasondavies
committed
Fix small-circle clipping of lines.
This corrects the handling of lines that are long enough to have two visible or invisible endpoints, but still cross the small circle and thus have an invisible or visible intermediate segment. Fixes d3#1127.
1 parent 6b04c1f commit d93f45e

6 files changed

Lines changed: 188 additions & 47 deletions

File tree

‎d3.js‎

Lines changed: 52 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -2245,16 +2245,16 @@ d3 = function() {
22452245
};
22462246
return circle.angle(90);
22472247
};
2248-
function d3_geo_circleInterpolate(radians, precision) {
2249-
var cr = Math.cos(radians), sr = Math.sin(radians);
2248+
function d3_geo_circleInterpolate(radius, precision) {
2249+
var cr = Math.cos(radius), sr = Math.sin(radius);
22502250
return function(from, to, direction, listener) {
22512251
if (from != null) {
22522252
from = d3_geo_circleAngle(cr, from);
22532253
to = d3_geo_circleAngle(cr, to);
22542254
if (direction > 0 ? from < to : from > to) from += direction * 2 * π;
22552255
} else {
2256-
from = radians + direction * 2 * π;
2257-
to = radians;
2256+
from = radius + direction * 2 * π;
2257+
to = radius;
22582258
}
22592259
var point;
22602260
for (var step = direction * precision, t = from; direction > 0 ? t > to : t < to; t -= step) {
@@ -2737,21 +2737,21 @@ d3 = function() {
27372737
listener.point(to[0], to[1]);
27382738
}
27392739
}
2740-
function d3_geo_clipCircle(degrees) {
2741-
var radians = degrees * d3_radians, cr = Math.cos(radians), interpolate = d3_geo_circleInterpolate(radians, 6 * d3_radians);
2740+
function d3_geo_clipCircle(radius) {
2741+
var cr = Math.cos(radius), smallRadius = cr > 0, notHemisphere = Math.abs(cr) > ε, interpolate = d3_geo_circleInterpolate(radius, 6 * d3_radians);
27422742
return d3_geo_clip(visible, clipLine, interpolate);
27432743
function visible(λ, φ) {
27442744
return Math.cos(λ) * Math.cos(φ) > cr;
27452745
}
27462746
function clipLine(listener) {
2747-
var point0, v0, v00, clean;
2747+
var point0, c0, v0, v00, clean;
27482748
return {
27492749
lineStart: function() {
27502750
v00 = v0 = false;
27512751
clean = 1;
27522752
},
27532753
point: function(λ, φ) {
2754-
var point1 = [ λ, φ ], point2, v = visible(λ, φ);
2754+
var point1 = [ λ, φ ], point2, v = visible(λ, φ), c = smallRadius ? v ? 0 : code(λ, φ) : v ? code(λ + (λ < 0 ? π : -π), φ) : 0;
27552755
if (!point0 && (v00 = v0 = v)) listener.lineStart();
27562756
if (v !== v0) {
27572757
point2 = intersect(point0, point1);
@@ -2763,7 +2763,7 @@ d3 = function() {
27632763
}
27642764
if (v !== v0) {
27652765
clean = 0;
2766-
if (v0 = v) {
2766+
if (v) {
27672767
listener.lineStart();
27682768
point2 = intersect(point1, point0);
27692769
listener.point(point2[0], point2[1]);
@@ -2773,9 +2773,27 @@ d3 = function() {
27732773
listener.lineEnd();
27742774
}
27752775
point0 = point2;
2776+
} else if (notHemisphere && point0 && smallRadius ^ v) {
2777+
var t;
2778+
if (!(c & c0) && (t = intersect(point1, point0, true))) {
2779+
clean = 0;
2780+
if (smallRadius) {
2781+
listener.lineStart();
2782+
listener.point(t[0][0], t[0][1]);
2783+
listener.point(t[1][0], t[1][1]);
2784+
listener.lineEnd();
2785+
} else {
2786+
listener.point(t[1][0], t[1][1]);
2787+
listener.lineEnd();
2788+
listener.lineStart();
2789+
listener.point(t[0][0], t[0][1]);
2790+
}
2791+
}
27762792
}
2777-
if (v && (!point0 || !d3_geo_sphericalEqual(point0, point1))) listener.point(point1[0], point1[1]);
2778-
point0 = point1;
2793+
if (v && (!point0 || !d3_geo_sphericalEqual(point0, point1))) {
2794+
listener.point(point1[0], point1[1]);
2795+
}
2796+
point0 = point1, v0 = v, c0 = c;
27792797
},
27802798
lineEnd: function() {
27812799
if (v0) listener.lineEnd();
@@ -2786,15 +2804,33 @@ d3 = function() {
27862804
}
27872805
};
27882806
}
2789-
function intersect(a, b) {
2807+
function intersect(a, b, two) {
27902808
var pa = d3_geo_cartesian(a), pb = d3_geo_cartesian(b);
27912809
var n1 = [ 1, 0, 0 ], n2 = d3_geo_cartesianCross(pa, pb), n2n2 = d3_geo_cartesianDot(n2, n2), n1n2 = n2[0], determinant = n2n2 - n1n2 * n1n2;
2792-
if (!determinant) return a;
2810+
if (!determinant) return !two && a;
27932811
var c1 = cr * n2n2 / determinant, c2 = -cr * n1n2 / determinant, n1xn2 = d3_geo_cartesianCross(n1, n2), A = d3_geo_cartesianScale(n1, c1), B = d3_geo_cartesianScale(n2, c2);
27942812
d3_geo_cartesianAdd(A, B);
2795-
var u = n1xn2, w = d3_geo_cartesianDot(A, u), uu = d3_geo_cartesianDot(u, u), t = Math.sqrt(w * w - uu * (d3_geo_cartesianDot(A, A) - 1)), q = d3_geo_cartesianScale(u, (-w - t) / uu);
2813+
var u = n1xn2, w = d3_geo_cartesianDot(A, u), uu = d3_geo_cartesianDot(u, u), t2 = w * w - uu * (d3_geo_cartesianDot(A, A) - 1);
2814+
if (t2 < 0) return;
2815+
var t = Math.sqrt(t2), q = d3_geo_cartesianScale(u, (-w - t) / uu);
27962816
d3_geo_cartesianAdd(q, A);
2797-
return d3_geo_spherical(q);
2817+
q = d3_geo_spherical(q);
2818+
if (!two) return q;
2819+
var λ0 = a[0], λ1 = b[0], φ0 = a[1], φ1 = b[1], z;
2820+
if (λ1 < λ0) z = λ0, λ0 = λ1, λ1 = z;
2821+
var δλ = λ1 - λ0, polar = Math.abs(δλ - π) < ε, meridian = polar || δλ < ε;
2822+
if (!polar && φ1 < φ0) z = φ0, φ0 = φ1, φ1 = z;
2823+
if (meridian ? polar ? φ0 + φ1 > 0 ^ q[1] < (Math.abs(q[0] - λ0) < ε ? φ0 : φ1) : φ0 <= q[1] && q[1] <= φ1 : δλ > π ^ (λ0 <= q[0] && q[0] <= λ1)) {
2824+
var q1 = d3_geo_cartesianScale(u, (-w + t) / uu);
2825+
d3_geo_cartesianAdd(q1, A);
2826+
return [ q, d3_geo_spherical(q1) ];
2827+
}
2828+
}
2829+
function code(λ, φ) {
2830+
var r = smallRadius ? radius : π - radius, code = 0;
2831+
if (λ < -r) code |= 1; else if (λ > r) code |= 2;
2832+
if (φ < -r) code |= 4; else if (φ > r) code |= 8;
2833+
return code;
27982834
}
27992835
}
28002836
function d3_geo_clipView(x0, y0, x1, y1) {
@@ -3046,7 +3082,7 @@ d3 = function() {
30463082
};
30473083
projection.clipAngle = function(_) {
30483084
if (!arguments.length) return clipAngle;
3049-
preclip = _ == null ? (clipAngle = _, d3_geo_clipAntimeridian) : d3_geo_clipCircle(clipAngle = +_);
3085+
preclip = _ == null ? (clipAngle = _, d3_geo_clipAntimeridian) : d3_geo_clipCircle((clipAngle = +_) * d3_radians);
30503086
return projection;
30513087
};
30523088
projection.clipExtent = function(_) {

‎d3.min.js‎

Lines changed: 5 additions & 5 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/geo/circle.js‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -48,17 +48,17 @@ d3.geo.circle = function() {
4848

4949
// Interpolates along a circle centered at [0°, 0°], with a given radius and
5050
// precision.
51-
function d3_geo_circleInterpolate(radians, precision) {
52-
var cr = Math.cos(radians),
53-
sr = Math.sin(radians);
51+
function d3_geo_circleInterpolate(radius, precision) {
52+
var cr = Math.cos(radius),
53+
sr = Math.sin(radius);
5454
return function(from, to, direction, listener) {
5555
if (from != null) {
5656
from = d3_geo_circleAngle(cr, from);
5757
to = d3_geo_circleAngle(cr, to);
5858
if (direction > 0 ? from < to: from > to) from += direction * 2 * π;
5959
} else {
60-
from = radians + direction * 2 * π;
61-
to = radians;
60+
from = radius + direction * 2 * π;
61+
to = radius;
6262
}
6363
var point;
6464
for (var step = direction * precision, t = from; direction > 0 ? t > to : t < to; t -= step) {

‎src/geo/clip-circle.js‎

Lines changed: 89 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -4,29 +4,30 @@ import "clip";
44
import "circle";
55
import "spherical";
66

7-
// Clip features against a circle centered at [0°, 0°], with a given radius.
8-
function d3_geo_clipCircle(degrees) {
9-
var radians = degrees * d3_radians,
10-
cr = Math.cos(radians),
11-
interpolate = d3_geo_circleInterpolate(radians, 6 * d3_radians);
7+
// Clip features against a small circle centered at [0°, 0°].
8+
function d3_geo_clipCircle(radius) {
9+
var cr = Math.cos(radius),
10+
smallRadius = cr > 0,
11+
notHemisphere = Math.abs(cr) > ε, // TODO optimise for this common case
12+
interpolate = d3_geo_circleInterpolate(radius, 6 * d3_radians);
1213

1314
return d3_geo_clip(visible, clipLine, interpolate);
1415

1516
function visible(λ, φ) {
1617
return Math.cos(λ) * Math.cos(φ) > cr;
1718
}
1819

19-
// TODO handle two invisible endpoints with visible intermediate segment.
2020
// Takes a line and cuts into visible segments. Return values used for
2121
// polygon clipping:
2222
// 0: there were intersections or the line was empty.
2323
// 1: no intersections.
2424
// 2: there were intersections, and the first and last segments should be
2525
// rejoined.
2626
function clipLine(listener) {
27-
var point0,
28-
v0,
29-
v00,
27+
var point0, // previous point
28+
c0, // code for previous point
29+
v0, // visibility of previous point
30+
v00, // visibility of first point
3031
clean; // no intersections
3132
return {
3233
lineStart: function() {
@@ -36,9 +37,13 @@ function d3_geo_clipCircle(degrees) {
3637
point: function(λ, φ) {
3738
var point1 = [λ, φ],
3839
point2,
39-
v = visible(λ, φ);
40+
v = visible(λ, φ),
41+
c = smallRadius
42+
? v ? 0 : code(λ, φ)
43+
: v ? code(λ + (λ < 0 ? π : -π), φ) : 0;
4044
if (!point0 && (v00 = v0 = v)) listener.lineStart();
41-
// handle degeneracies
45+
// Handle degeneracies.
46+
// TODO ignore if not clipping polygons.
4247
if (v !== v0) {
4348
point2 = intersect(point0, point1);
4449
if (d3_geo_sphericalEqual(point0, point2) || d3_geo_sphericalEqual(point1, point2)) {
@@ -49,7 +54,7 @@ function d3_geo_clipCircle(degrees) {
4954
}
5055
if (v !== v0) {
5156
clean = 0;
52-
if (v0 = v) {
57+
if (v) {
5358
// outside going in
5459
listener.lineStart();
5560
point2 = intersect(point1, point0);
@@ -61,9 +66,29 @@ function d3_geo_clipCircle(degrees) {
6166
listener.lineEnd();
6267
}
6368
point0 = point2;
69+
} else if (notHemisphere && point0 && smallRadius ^ v) {
70+
var t;
71+
// If the codes for two points are different, or are both zero,
72+
// and there this segment intersects with the small circle.
73+
if (!(c & c0) && (t = intersect(point1, point0, true))) {
74+
clean = 0;
75+
if (smallRadius) {
76+
listener.lineStart();
77+
listener.point(t[0][0], t[0][1]);
78+
listener.point(t[1][0], t[1][1]);
79+
listener.lineEnd();
80+
} else {
81+
listener.point(t[1][0], t[1][1]);
82+
listener.lineEnd();
83+
listener.lineStart();
84+
listener.point(t[0][0], t[0][1]);
85+
}
86+
}
87+
}
88+
if (v && (!point0 || !d3_geo_sphericalEqual(point0, point1))) {
89+
listener.point(point1[0], point1[1]);
6490
}
65-
if (v && (!point0 || !d3_geo_sphericalEqual(point0, point1))) listener.point(point1[0], point1[1]);
66-
point0 = point1;
91+
point0 = point1, v0 = v, c0 = c;
6792
},
6893
lineEnd: function() {
6994
if (v0) listener.lineEnd();
@@ -76,32 +101,76 @@ function d3_geo_clipCircle(degrees) {
76101
}
77102

78103
// Intersects the great circle between a and b with the clip circle.
79-
function intersect(a, b) {
104+
function intersect(a, b, two) {
80105
var pa = d3_geo_cartesian(a),
81106
pb = d3_geo_cartesian(b);
107+
82108
// We have two planes, n1.p = d1 and n2.p = d2.
83-
// Find intersection line p(t) = c1 n1 + c2 n2 + t (n1 x n2).
109+
// Find intersection line p(t) = c1 n1 + c2 n2 + t (n1 ⨯ n2).
84110
var n1 = [1, 0, 0], // normal
85111
n2 = d3_geo_cartesianCross(pa, pb),
86112
n2n2 = d3_geo_cartesianDot(n2, n2),
87113
n1n2 = n2[0], // d3_geo_cartesianDot(n1, n2),
88114
determinant = n2n2 - n1n2 * n1n2;
115+
89116
// Two polar points.
90-
if (!determinant) return a;
117+
if (!determinant) return !two && a;
91118

92119
var c1 = cr * n2n2 / determinant,
93120
c2 = -cr * n1n2 / determinant,
94121
n1xn2 = d3_geo_cartesianCross(n1, n2),
95122
A = d3_geo_cartesianScale(n1, c1),
96123
B = d3_geo_cartesianScale(n2, c2);
97124
d3_geo_cartesianAdd(A, B);
98-
// Now solve |p(t)|^2 = 1.
125+
126+
// Solve |p(t)|^2 = 1.
99127
var u = n1xn2,
100128
w = d3_geo_cartesianDot(A, u),
101129
uu = d3_geo_cartesianDot(u, u),
102-
t = Math.sqrt(w * w - uu * (d3_geo_cartesianDot(A, A) - 1)),
130+
t2 = w * w - uu * (d3_geo_cartesianDot(A, A) - 1);
131+
132+
if (t2 < 0) return;
133+
134+
var t = Math.sqrt(t2),
103135
q = d3_geo_cartesianScale(u, (-w - t) / uu);
104136
d3_geo_cartesianAdd(q, A);
105-
return d3_geo_spherical(q);
137+
q = d3_geo_spherical(q);
138+
if (!two) return q;
139+
140+
// Two intersection points.
141+
var λ0 = a[0],
142+
λ1 = b[0],
143+
φ0 = a[1],
144+
φ1 = b[1],
145+
z;
146+
if (λ1 < λ0) z = λ0, λ0 = λ1, λ1 = z;
147+
var δλ = λ1 - λ0,
148+
polar = Math.abs(δλ - π) < ε,
149+
meridian = polar || δλ < ε;
150+
151+
if (!polar && φ1 < φ0) z = φ0, φ0 = φ1, φ1 = z;
152+
153+
// Check that the first point is between a and b.
154+
if (meridian
155+
? polar
156+
? φ0 + φ1 > 0 ^ q[1] < (Math.abs(q[0] - λ0) < ε ? φ0 : φ1)
157+
: φ0 <= q[1] && q[1] <= φ1
158+
: δλ > π ^ (λ0 <= q[0] && q[0] <= λ1)) {
159+
var q1 = d3_geo_cartesianScale(u, (-w + t) / uu);
160+
d3_geo_cartesianAdd(q1, A);
161+
return [q, d3_geo_spherical(q1)];
162+
}
163+
}
164+
165+
// Generates a 4-bit vector representing the location of a point relative to
166+
// the small circle's bounding box.
167+
function code(λ, φ) {
168+
var r = smallRadius ? radius : π - radius,
169+
code = 0;
170+
if (λ < -r) code |= 1; // left
171+
else if (λ > r) code |= 2; // right
172+
if (φ < -r) code |= 4; // below
173+
else if (φ > r) code |= 8; // above
174+
return code;
106175
}
107176
}

‎src/geo/projection.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@ function d3_geo_projectionMutator(projectAt) {
4848

4949
projection.clipAngle = function(_) {
5050
if (!arguments.length) return clipAngle;
51-
preclip = _ == null ? (clipAngle = _, d3_geo_clipAntimeridian) : d3_geo_clipCircle(clipAngle = +_);
51+
preclip = _ == null ? (clipAngle = _, d3_geo_clipAntimeridian) : d3_geo_clipCircle((clipAngle = +_) * d3_radians);
5252
return projection;
5353
};
5454

‎test/geo/path-test.js‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -589,6 +589,42 @@ suite.addBatch({
589589
}
590590
}
591591
},
592+
"clipAngle(30)": {
593+
topic: function() {
594+
return d3.geo.path()
595+
.context(testContext)
596+
.projection(d3.geo.equirectangular()
597+
.scale(900 / Math.PI)
598+
.precision(0)
599+
.clipAngle(30));
600+
},
601+
"clips lines with two invisible endpoints and visible middle": function(path) {
602+
path({type: "LineString", coordinates: [[-45, 0], [45, 0]]});
603+
assert.deepEqual(testContext.buffer(), [
604+
{type: "moveTo", x: 330, y: 250},
605+
{type: "lineTo", x: 630, y: 250}
606+
]);
607+
}
608+
},
609+
"clipAngle(150)": {
610+
topic: function() {
611+
return d3.geo.path()
612+
.context(testContext)
613+
.projection(d3.geo.equirectangular()
614+
.scale(900 / Math.PI)
615+
.precision(0)
616+
.clipAngle(150));
617+
},
618+
"clips lines with two visible endpoints and invisible middle": function(path) {
619+
path({type: "LineString", coordinates: [[135, 0], [-135, 0]]});
620+
assert.deepEqual(testContext.buffer(), [
621+
{type: "moveTo", x: 1155, y: 250},
622+
{type: "lineTo", x: 1230, y: 250},
623+
{type: "moveTo", x: -270, y: 250},
624+
{type: "lineTo", x: -195, y: 250}
625+
]);
626+
}
627+
},
592628

593629
"antimeridian cutting": {
594630
"rotate([98, 0])": {

0 commit comments

Comments
 (0)