Skip to content

Commit 399b145

Browse files
jasondaviesjasondavies
committed
Add d3.geo.greatcircle.
Can be used to generate great circle paths. Similar to R's geosphere.gcIntermediate (in which I discovered a bug, while writing the test case for this!) Includes d3.geo.greatcircle().distance for computing the shortest geo path distance using the Haversine formula. For a tutorial on using great circles, see: http://flowingdata.com/2011/05/11/how-to-map-connections-with-great-circles/
1 parent cd135d5 commit 399b145

5 files changed

Lines changed: 157 additions & 1 deletion

File tree

‎Makefile‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -185,6 +185,7 @@ d3.geo.js: \
185185
src/geo/mercator.js \
186186
src/geo/path.js \
187187
src/geo/bounds.js \
188+
src/geo/greatcircle.js \
188189
src/end.js
189190

190191
d3.csv.js: \

‎d3.geo.js‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -564,4 +564,61 @@ function d3_geo_boundsPolygon(o, f) {
564564
f.apply(null, a[i]);
565565
}
566566
}
567+
// From http://williams.best.vwh.net/avform.htm#Intermediate
568+
d3.geo.greatcircle = function() {
569+
// TODO: breakAtDateLine?
570+
function greatcircle(from, to, n) {
571+
var x0 = from[0] * d3_radians,
572+
y0 = from[1] * d3_radians,
573+
x1 = to[0] * d3_radians,
574+
y1 = to[1] * d3_radians,
575+
cx0 = Math.cos(x0),
576+
sx0 = Math.sin(x0),
577+
cy0 = Math.cos(y0),
578+
sy0 = Math.sin(y0),
579+
cx1 = Math.cos(x1),
580+
sx1 = Math.sin(x1),
581+
cy1 = Math.cos(y1),
582+
sy1 = Math.sin(y1),
583+
d = Math.acos(sy0 * sy1 + cy0 * cy1 * Math.cos(x1 - x0)),
584+
sd = Math.sin(d),
585+
f = d / (n - 1),
586+
e = -f,
587+
path = [],
588+
i = -1;
589+
590+
while (++i < n) {
591+
e += f;
592+
var A = Math.sin(d - e) / sd,
593+
B = Math.sin(e) / sd,
594+
x = A * cy0 * cx0 + B * cy1 * cx1,
595+
y = A * cy0 * sx0 + B * cy1 * sx1,
596+
z = A * sy0 + B * sy1;
597+
path[i] = [
598+
Math.atan2(y, x) / d3_radians,
599+
Math.atan2(z, Math.sqrt(x * x + y * y)) / d3_radians
600+
];
601+
}
602+
603+
return path;
604+
}
605+
606+
greatcircle.distance = d3_geo_greatcircleDistance;
607+
608+
return greatcircle;
609+
};
610+
611+
// Haversine formula for great-circle distance.
612+
function d3_geo_greatcircleDistance(from, to, radius) {
613+
if (arguments.length < 3) radius = 6371;
614+
var x0 = from[0] * d3_radians,
615+
y0 = from[1] * d3_radians,
616+
x1 = to[0] * d3_radians,
617+
y1 = to[1] * d3_radians,
618+
sy = Math.sin((y1 - y0) / 2),
619+
sx = Math.sin((x1 - x0) / 2),
620+
a = sy * sy + Math.cos(y0) * Math.cos(y1) * sx * sx;
621+
622+
return radius * 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
623+
};
567624
})();

‎d3.geo.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/greatcircle.js‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
// From http://williams.best.vwh.net/avform.htm#Intermediate
2+
d3.geo.greatcircle = function() {
3+
// TODO: breakAtDateLine?
4+
function greatcircle(from, to, n) {
5+
var x0 = from[0] * d3_radians,
6+
y0 = from[1] * d3_radians,
7+
x1 = to[0] * d3_radians,
8+
y1 = to[1] * d3_radians,
9+
cx0 = Math.cos(x0),
10+
sx0 = Math.sin(x0),
11+
cy0 = Math.cos(y0),
12+
sy0 = Math.sin(y0),
13+
cx1 = Math.cos(x1),
14+
sx1 = Math.sin(x1),
15+
cy1 = Math.cos(y1),
16+
sy1 = Math.sin(y1),
17+
d = Math.acos(sy0 * sy1 + cy0 * cy1 * Math.cos(x1 - x0)),
18+
sd = Math.sin(d),
19+
f = d / (n - 1),
20+
e = -f,
21+
path = [],
22+
i = -1;
23+
24+
while (++i < n) {
25+
e += f;
26+
var A = Math.sin(d - e) / sd,
27+
B = Math.sin(e) / sd,
28+
x = A * cy0 * cx0 + B * cy1 * cx1,
29+
y = A * cy0 * sx0 + B * cy1 * sx1,
30+
z = A * sy0 + B * sy1;
31+
path[i] = [
32+
Math.atan2(y, x) / d3_radians,
33+
Math.atan2(z, Math.sqrt(x * x + y * y)) / d3_radians
34+
];
35+
}
36+
37+
return path;
38+
}
39+
40+
greatcircle.distance = d3_geo_greatcircleDistance;
41+
42+
return greatcircle;
43+
};
44+
45+
// Haversine formula for great-circle distance.
46+
function d3_geo_greatcircleDistance(from, to, radius) {
47+
if (arguments.length < 3) radius = 6371;
48+
var x0 = from[0] * d3_radians,
49+
y0 = from[1] * d3_radians,
50+
x1 = to[0] * d3_radians,
51+
y1 = to[1] * d3_radians,
52+
sy = Math.sin((y1 - y0) / 2),
53+
sx = Math.sin((x1 - x0) / 2),
54+
a = sy * sy + Math.cos(y0) * Math.cos(y1) * sx * sx;
55+
56+
return radius * 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
57+
};

‎test/geo/greatcircle-test.js‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
require("../env");
2+
require("../../d3");
3+
require("../../d3.geo");
4+
5+
var vows = require("vows"),
6+
assert = require("assert");
7+
8+
var suite = vows.describe("d3.geo.greatcircle");
9+
10+
suite.addBatch({
11+
"greatcircle": {
12+
topic: function() {
13+
return d3.geo.greatcircle();
14+
},
15+
"distance": function(circle) {
16+
assert.equal(circle.distance([0, 0], [0, 0]), 0);
17+
assert.inDelta(circle.distance(
18+
[118 + 24 / 60, 33 + 57 / 60],
19+
[ 73 + 47 / 60, 40 + 38 / 60]
20+
), 3973, .5);
21+
},
22+
"geodesic": function(circle) {
23+
assert.inDelta(circle([5, 52], [-120, 37], 12), [
24+
[ 5, 52 ],
25+
[ -3.805036, 57.05083],
26+
[ -15.122869, 61.30118],
27+
[ -29.396213, 64.34584],
28+
[ -46.132729, 65.72409],
29+
[ -63.394401, 65.15597],
30+
[ -78.854311, 62.76337],
31+
[ -91.401599, 58.96701],
32+
[-101.190927, 54.21333],
33+
[-108.843633, 48.83586],
34+
[-114.961152, 43.05231],
35+
[-120, 37 ]
36+
], .5);
37+
}
38+
}
39+
});
40+
41+
suite.export(module);

0 commit comments

Comments
 (0)