Skip to content

Commit 881e0e5

Browse files
mbostockmbostock
committed
Extract simple vector math from d3_geo_circle.
1 parent 1c8bff5 commit 881e0e5

6 files changed

Lines changed: 126 additions & 116 deletions

File tree

‎Makefile‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -180,6 +180,8 @@ d3.layout.js: \
180180

181181
d3.geo.js: \
182182
src/geo/geo.js \
183+
src/geo/spherical.js \
184+
src/geo/cartesian.js \
183185
src/geo/type.js \
184186
src/geo/albers-usa.js \
185187
src/geo/albers.js \

‎d3.js‎

Lines changed: 42 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -5333,6 +5333,36 @@
53335333
d3.csv = d3_dsv(",", "text/csv");
53345334
d3.tsv = d3_dsv(" ", "text/tab-separated-values");
53355335
d3.geo = {};
5336+
function d3_geo_spherical(cartesian) {
5337+
return [ Math.atan2(cartesian[1], cartesian[0]), Math.asin(Math.max(-1, Math.min(1, cartesian[2]))) ];
5338+
}
5339+
function d3_geo_sphericalEqual(a, b) {
5340+
return Math.abs(a[0] - b[0]) < ε && Math.abs(a[1] - b[1]) < ε;
5341+
}
5342+
function d3_geo_cartesian(spherical, origin) {
5343+
var λ = spherical[0], φ = spherical[1], cosφ = Math.cos(φ);
5344+
return [ cosφ * Math.cos(λ) - origin, cosφ * Math.sin(λ), Math.sin(φ) ];
5345+
}
5346+
function d3_geo_cartesianDot(a, b) {
5347+
return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
5348+
}
5349+
function d3_geo_cartesianCross(a, b) {
5350+
return [ a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0] ];
5351+
}
5352+
function d3_geo_cartesianAdd(a, b) {
5353+
a[0] += b[0];
5354+
a[1] += b[1];
5355+
a[2] += b[2];
5356+
}
5357+
function d3_geo_cartesianScale(vector, k) {
5358+
return [ vector[0] * k, vector[1] * k, vector[2] * k ];
5359+
}
5360+
function d3_geo_cartesianNormalize(d) {
5361+
var l = Math.sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2]);
5362+
d[0] /= l;
5363+
d[1] /= l;
5364+
d[2] /= l;
5365+
}
53365366
function d3_geo_type(types) {
53375367
for (var type in d3_geo_typeDefaults) {
53385368
if (!(type in types)) {
@@ -5702,7 +5732,7 @@
57025732
v = visible(point1);
57035733
if (v !== v0) {
57045734
point2 = intersect(point0, point1);
5705-
if (d3_geo_circlePointsEqual(point0, point2) || d3_geo_circlePointsEqual(point1, point2)) {
5735+
if (d3_geo_sphericalEqual(point0, point2) || d3_geo_sphericalEqual(point1, point2)) {
57065736
point1[0] += ε;
57075737
point1[1] += ε;
57085738
v = visible(point1);
@@ -5727,20 +5757,20 @@
57275757
x0 = x;
57285758
y0 = y;
57295759
}
5730-
if (v && !d3_geo_circlePointsEqual(point0, point1)) context.lineTo(point1[0], point1[1]);
5760+
if (v && !d3_geo_sphericalEqual(point0, point1)) context.lineTo(point1[0], point1[1]);
57315761
point0 = point1;
57325762
}
57335763
return [ clean && area * .5, v00 && v ];
57345764
}
57355765
function intersect(a, b) {
5736-
var pa = d3_geo_circleCartesian(a, [ 0, 0, 0 ]), pb = d3_geo_circleCartesian(b, [ 0, 0, 0 ]);
5737-
var n1 = [ 1, 0, 0 ], n2 = d3_geo_circleCross(pa, pb), n2n2 = d3_geo_circleDot(n2, n2), n1n2 = n2[0], determinant = n2n2 - n1n2 * n1n2;
5766+
var pa = d3_geo_cartesian(a, 0), pb = d3_geo_cartesian(b, 0);
5767+
var n1 = [ 1, 0, 0 ], n2 = d3_geo_cartesianCross(pa, pb), n2n2 = d3_geo_cartesianDot(n2, n2), n1n2 = n2[0], determinant = n2n2 - n1n2 * n1n2;
57385768
if (!determinant) return a;
5739-
var c1 = cr * n2n2 / determinant, c2 = -cr * n1n2 / determinant, n1xn2 = d3_geo_circleCross(n1, n2), A = d3_geo_circleScale(n1, c1), B = d3_geo_circleScale(n2, c2);
5740-
d3_geo_circleAdd(A, B);
5741-
var u = n1xn2, w = d3_geo_circleDot(A, u), uu = d3_geo_circleDot(u, u), t = Math.sqrt(w * w - uu * (d3_geo_circleDot(A, A) - 1)), q = d3_geo_circleScale(u, (-w - t) / uu);
5742-
d3_geo_circleAdd(q, A);
5743-
return d3_geo_circleSpherical(q);
5769+
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);
5770+
d3_geo_cartesianAdd(A, B);
5771+
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);
5772+
d3_geo_cartesianAdd(q, A);
5773+
return d3_geo_spherical(q);
57445774
}
57455775
}
57465776
function d3_geo_circleInterpolate(radians, precision) {
@@ -5755,7 +5785,7 @@
57555785
to = radians;
57565786
}
57575787
for (var step = direction * precision, t = from; direction > 0 ? t > to : t < to; t -= step) {
5758-
var c = Math.cos(t), s = Math.sin(t), point = d3_geo_circleSpherical([ cr, -sr * c, -sr * s ]);
5788+
var c = Math.cos(t), s = Math.sin(t), point = d3_geo_spherical([ cr, -sr * c, -sr * s ]);
57595789
context.lineTo(point[0], point[1]);
57605790
}
57615791
};
@@ -5872,38 +5902,11 @@
58725902
return ((a = a.point)[0] < 0 ? a[1] - π / 2 - ε : π / 2 - a[1]) - ((b = b.point)[0] < 0 ? b[1] - π / 2 - ε : π / 2 - b[1]);
58735903
}
58745904
function d3_geo_circleAngle(cr, point) {
5875-
var a = d3_geo_circleCartesian(point, [ cr, 0, 0 ]);
5876-
d3_geo_circleNormalize(a);
5905+
var a = d3_geo_cartesian(point, cr);
5906+
d3_geo_cartesianNormalize(a);
58775907
var angle = Math.acos(Math.max(-1, Math.min(1, -a[1])));
58785908
return ((-a[2] < 0 ? -angle : angle) + 2 * Math.PI - ε) % (2 * Math.PI);
58795909
}
5880-
function d3_geo_circleCartesian(point, origin) {
5881-
var p0 = point[0], p1 = point[1], c1 = Math.cos(p1);
5882-
return [ c1 * Math.cos(p0) - origin[0], c1 * Math.sin(p0) - origin[1], Math.sin(p1) - origin[2] ];
5883-
}
5884-
function d3_geo_circleSpherical(point) {
5885-
return [ Math.atan2(point[1], point[0]), Math.asin(Math.max(-1, Math.min(1, point[2]))) ];
5886-
}
5887-
function d3_geo_circleDot(a, b) {
5888-
return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
5889-
}
5890-
function d3_geo_circleCross(a, b) {
5891-
return [ a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0] ];
5892-
}
5893-
function d3_geo_circleAdd(a, b) {
5894-
a[0] += b[0];
5895-
a[1] += b[1];
5896-
a[2] += b[2];
5897-
}
5898-
function d3_geo_circleScale(vector, s) {
5899-
return [ vector[0] * s, vector[1] * s, vector[2] * s ];
5900-
}
5901-
function d3_geo_circleNormalize(d) {
5902-
var l = Math.sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2]);
5903-
d[0] /= l;
5904-
d[1] /= l;
5905-
d[2] /= l;
5906-
}
59075910
function d3_geo_circleBufferSegments(f) {
59085911
return function(coordinates) {
59095912
var segments = [], segment;
@@ -5917,9 +5920,6 @@
59175920
}, true), segments ];
59185921
};
59195922
}
5920-
function d3_geo_circlePointsEqual(a, b) {
5921-
return Math.abs(a[0] - b[0]) < ε && Math.abs(a[1] - b[1]) < ε;
5922-
}
59235923
function d3_geo_circleSegmentLength1(segment) {
59245924
return segment.length > 1;
59255925
}

‎d3.min.js‎

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

‎src/geo/cartesian.js‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
// TODO
2+
// cross and scale return new vectors,
3+
// whereas add and normalize operate in-place
4+
5+
function d3_geo_cartesian(spherical, origin) {
6+
var λ = spherical[0],
7+
φ = spherical[1],
8+
cosφ = Math.cos(φ);
9+
return [
10+
cosφ * Math.cos(λ) - origin,
11+
cosφ * Math.sin(λ),
12+
Math.sin(φ)
13+
];
14+
}
15+
16+
function d3_geo_cartesianDot(a, b) {
17+
return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
18+
}
19+
20+
function d3_geo_cartesianCross(a, b) {
21+
return [
22+
a[1] * b[2] - a[2] * b[1],
23+
a[2] * b[0] - a[0] * b[2],
24+
a[0] * b[1] - a[1] * b[0]
25+
];
26+
}
27+
28+
function d3_geo_cartesianAdd(a, b) {
29+
a[0] += b[0];
30+
a[1] += b[1];
31+
a[2] += b[2];
32+
}
33+
34+
function d3_geo_cartesianScale(vector, k) {
35+
return [
36+
vector[0] * k,
37+
vector[1] * k,
38+
vector[2] * k
39+
];
40+
}
41+
42+
function d3_geo_cartesianNormalize(d) {
43+
var l = Math.sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2]);
44+
d[0] /= l;
45+
d[1] /= l;
46+
d[2] /= l;
47+
}

‎src/geo/circle.js‎

Lines changed: 22 additions & 71 deletions
Original file line numberDiff line numberDiff line change
@@ -98,7 +98,7 @@ function d3_geo_circleClip(degrees, rotate) {
9898
// handle degeneracies
9999
if (v !== v0) {
100100
point2 = intersect(point0, point1);
101-
if (d3_geo_circlePointsEqual(point0, point2) || d3_geo_circlePointsEqual(point1, point2)) {
101+
if (d3_geo_sphericalEqual(point0, point2) || d3_geo_sphericalEqual(point1, point2)) {
102102
point1[0] += ε;
103103
point1[1] += ε;
104104
v = visible(point1);
@@ -125,7 +125,7 @@ function d3_geo_circleClip(degrees, rotate) {
125125
x0 = x;
126126
y0 = y;
127127
}
128-
if (v && !d3_geo_circlePointsEqual(point0, point1)) context.lineTo(point1[0], point1[1]);
128+
if (v && !d3_geo_sphericalEqual(point0, point1)) context.lineTo(point1[0], point1[1]);
129129
point0 = point1;
130130
}
131131
return [
@@ -137,32 +137,32 @@ function d3_geo_circleClip(degrees, rotate) {
137137
// Intersects the great circle between a and b with the clip circle.
138138
// TODO special case: clipAngle(90°); avoid conversion ↔ Cartesian 3-space.
139139
function intersect(a, b) {
140-
var pa = d3_geo_circleCartesian(a, [0, 0, 0]),
141-
pb = d3_geo_circleCartesian(b, [0, 0, 0]);
140+
var pa = d3_geo_cartesian(a, 0),
141+
pb = d3_geo_cartesian(b, 0);
142142
// We have two planes, n1.p = d1 and n2.p = d2.
143143
// Find intersection line p(t) = c1 n1 + c2 n2 + t (n1 x n2).
144144
var n1 = [1, 0, 0], // normal
145-
n2 = d3_geo_circleCross(pa, pb),
146-
n2n2 = d3_geo_circleDot(n2, n2),
147-
n1n2 = n2[0], // d3_geo_circleDot(n1, n2),
145+
n2 = d3_geo_cartesianCross(pa, pb),
146+
n2n2 = d3_geo_cartesianDot(n2, n2),
147+
n1n2 = n2[0], // d3_geo_cartesianDot(n1, n2),
148148
determinant = n2n2 - n1n2 * n1n2;
149149
// Two polar points.
150150
if (!determinant) return a;
151151

152152
var c1 = cr * n2n2 / determinant,
153153
c2 = -cr * n1n2 / determinant,
154-
n1xn2 = d3_geo_circleCross(n1, n2),
155-
A = d3_geo_circleScale(n1, c1),
156-
B = d3_geo_circleScale(n2, c2);
157-
d3_geo_circleAdd(A, B);
154+
n1xn2 = d3_geo_cartesianCross(n1, n2),
155+
A = d3_geo_cartesianScale(n1, c1),
156+
B = d3_geo_cartesianScale(n2, c2);
157+
d3_geo_cartesianAdd(A, B);
158158
// Now solve |p(t)|^2 = 1.
159159
var u = n1xn2,
160-
w = d3_geo_circleDot(A, u),
161-
uu = d3_geo_circleDot(u, u),
162-
t = Math.sqrt(w * w - uu * (d3_geo_circleDot(A, A) - 1)),
163-
q = d3_geo_circleScale(u, (-w - t) / uu);
164-
d3_geo_circleAdd(q, A);
165-
return d3_geo_circleSpherical(q);
160+
w = d3_geo_cartesianDot(A, u),
161+
uu = d3_geo_cartesianDot(u, u),
162+
t = Math.sqrt(w * w - uu * (d3_geo_cartesianDot(A, A) - 1)),
163+
q = d3_geo_cartesianScale(u, (-w - t) / uu);
164+
d3_geo_cartesianAdd(q, A);
165+
return d3_geo_spherical(q);
166166
}
167167
}
168168

@@ -181,7 +181,7 @@ function d3_geo_circleInterpolate(radians, precision) {
181181
for (var step = direction * precision, t = from; direction > 0 ? t > to : t < to; t -= step) {
182182
var c = Math.cos(t),
183183
s = Math.sin(t),
184-
point = d3_geo_circleSpherical([
184+
point = d3_geo_spherical([
185185
cr,
186186
-sr * c,
187187
-sr * s
@@ -309,59 +309,12 @@ function d3_geo_circleClipSort(a, b) {
309309

310310
// Signed angle of a cartesian point relative to [0, 0, 0].
311311
function d3_geo_circleAngle(cr, point) {
312-
var a = d3_geo_circleCartesian(point, [cr, 0, 0]);
313-
d3_geo_circleNormalize(a);
312+
var a = d3_geo_cartesian(point, cr);
313+
d3_geo_cartesianNormalize(a);
314314
var angle = Math.acos(Math.max(-1, Math.min(1, -a[1])));
315315
return ((-a[2] < 0 ? -angle : angle) + 2 * Math.PI - ε) % (2 * Math.PI);
316316
}
317317

318-
// Convert spherical to normalized Cartesian coordinates, relative to a
319-
// Cartesian origin.
320-
function d3_geo_circleCartesian(point, origin) {
321-
var p0 = point[0],
322-
p1 = point[1],
323-
c1 = Math.cos(p1);
324-
return [c1 * Math.cos(p0) - origin[0],
325-
c1 * Math.sin(p0) - origin[1],
326-
Math.sin(p1) - origin[2]];
327-
}
328-
329-
// Convert from Cartesian to spherical coordinates.
330-
function d3_geo_circleSpherical(point) {
331-
return [
332-
Math.atan2(point[1], point[0]),
333-
Math.asin(Math.max(-1, Math.min(1, point[2])))
334-
];
335-
}
336-
337-
function d3_geo_circleDot(a, b) {
338-
return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
339-
}
340-
341-
function d3_geo_circleCross(a, b) {
342-
return [
343-
a[1] * b[2] - a[2] * b[1],
344-
a[2] * b[0] - a[0] * b[2],
345-
a[0] * b[1] - a[1] * b[0]];
346-
}
347-
348-
function d3_geo_circleAdd(a, b) {
349-
a[0] += b[0];
350-
a[1] += b[1];
351-
a[2] += b[2];
352-
}
353-
354-
function d3_geo_circleScale(vector, s) {
355-
return [vector[0] * s, vector[1] * s, vector[2] * s];
356-
}
357-
358-
function d3_geo_circleNormalize(d) {
359-
var l = Math.sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2]);
360-
d[0] /= l;
361-
d[1] /= l;
362-
d[2] /= l;
363-
}
364-
365318
function d3_geo_circleBufferSegments(f) {
366319
return function(coordinates) {
367320
var segments = [],
@@ -376,8 +329,6 @@ function d3_geo_circleBufferSegments(f) {
376329
};
377330
}
378331

379-
function d3_geo_circlePointsEqual(a, b) {
380-
return Math.abs(a[0] - b[0]) < ε && Math.abs(a[1] - b[1]) < ε;
332+
function d3_geo_circleSegmentLength1(segment) {
333+
return segment.length > 1;
381334
}
382-
383-
function d3_geo_circleSegmentLength1(segment) { return segment.length > 1; }

‎src/geo/spherical.js‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
function d3_geo_spherical(cartesian) {
2+
return [
3+
Math.atan2(cartesian[1], cartesian[0]),
4+
Math.asin(Math.max(-1, Math.min(1, cartesian[2])))
5+
];
6+
}
7+
8+
function d3_geo_sphericalEqual(a, b) {
9+
return Math.abs(a[0] - b[0]) < ε && Math.abs(a[1] - b[1]) < ε;
10+
}

0 commit comments

Comments
 (0)