Skip to content

Commit 61a1651

Browse files
mbostockmbostock
committed
Merge branch 'clip-circle' of git://github.com/jasondavies/d3 into 3.1.0
2 parents 29d6055 + d93f45e commit 61a1651

7 files changed

Lines changed: 189 additions & 48 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.

‎package.json‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,7 @@
3131
"jsdom": "~0.5.2"
3232
},
3333
"devDependencies": {
34-
"smash": "~0.0.3",
34+
"smash": "~0.0.4",
3535
"uglify-js": "2.2.x",
3636
"vows": "0.7.x"
3737
},

‎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)