2ecfaf5255d49a26f4206910d7b50f3f84eeea81
[rails.git] / vendor / assets / iD / iD.js
1 (function(exports) {
2
3   var bootstrap = (typeof exports.bootstrap === "object") ?
4     exports.bootstrap :
5     (exports.bootstrap = {});
6
7   bootstrap.tooltip = function() {
8
9     var tooltip = function(selection) {
10         selection.each(setup);
11       },
12       animation = d3.functor(false),
13       html = d3.functor(false),
14       title = function() {
15         var title = this.getAttribute("data-original-title");
16         if (title) {
17           return title;
18         } else {
19           title = this.getAttribute("title");
20           this.removeAttribute("title");
21           this.setAttribute("data-original-title", title);
22         }
23         return title;
24       },
25       over = "mouseenter.tooltip",
26       out = "mouseleave.tooltip",
27       placements = "top left bottom right".split(" "),
28       placement = d3.functor("top");
29
30     tooltip.title = function(_) {
31       if (arguments.length) {
32         title = d3.functor(_);
33         return tooltip;
34       } else {
35         return title;
36       }
37     };
38
39     tooltip.html = function(_) {
40       if (arguments.length) {
41         html = d3.functor(_);
42         return tooltip;
43       } else {
44         return html;
45       }
46     };
47
48     tooltip.placement = function(_) {
49       if (arguments.length) {
50         placement = d3.functor(_);
51         return tooltip;
52       } else {
53         return placement;
54       }
55     };
56
57     tooltip.show = function(selection) {
58       selection.each(show);
59     };
60
61     tooltip.hide = function(selection) {
62       selection.each(hide);
63     };
64
65     tooltip.toggle = function(selection) {
66       selection.each(toggle);
67     };
68
69     tooltip.destroy = function(selection) {
70       selection
71         .on(over, null)
72         .on(out, null)
73         .attr("title", function() {
74           return this.getAttribute("data-original-title") || this.getAttribute("title");
75         })
76         .attr("data-original-title", null)
77         .select(".tooltip")
78         .remove();
79     };
80
81     function setup() {
82       var root = d3.select(this),
83           animate = animation.apply(this, arguments),
84           tip = root.append("div")
85             .attr("class", "tooltip");
86
87       if (animate) {
88         tip.classed("fade", true);
89       }
90
91       // TODO "inside" checks?
92
93       tip.append("div")
94         .attr("class", "tooltip-arrow");
95       tip.append("div")
96         .attr("class", "tooltip-inner");
97
98       var place = placement.apply(this, arguments);
99       tip.classed(place, true);
100
101       root.on(over, show);
102       root.on(out, hide);
103     }
104
105     function show() {
106       var root = d3.select(this),
107           content = title.apply(this, arguments),
108           tip = root.select(".tooltip")
109             .classed("in", true),
110           markup = html.apply(this, arguments),
111           innercontent = tip.select(".tooltip-inner")[markup ? "html" : "text"](content),
112           place = placement.apply(this, arguments),
113           outer = getPosition(root.node()),
114           inner = getPosition(tip.node()),
115           pos;
116
117       switch (place) {
118         case "top":
119           pos = {x: outer.x + (outer.w - inner.w) / 2, y: outer.y - inner.h};
120           break;
121         case "right":
122           pos = {x: outer.x + outer.w, y: outer.y + (outer.h - inner.h) / 2};
123           break;
124         case "left":
125           pos = {x: outer.x - inner.w, y: outer.y + (outer.h - inner.h) / 2};
126           break;
127         case "bottom":
128           pos = {x: Math.max(0, outer.x + (outer.w - inner.w) / 2), y: outer.y + outer.h};
129           break;
130       }
131
132       tip.style(pos ?
133         {left: ~~pos.x + "px", top: ~~pos.y + "px"} :
134         {left: null, top: null});
135
136       this.tooltipVisible = true;
137     }
138
139     function hide() {
140       d3.select(this).select(".tooltip")
141         .classed("in", false);
142
143       this.tooltipVisible = false;
144     }
145
146     function toggle() {
147       if (this.tooltipVisible) {
148         hide.apply(this, arguments);
149       } else {
150         show.apply(this, arguments);
151       }
152     }
153
154     return tooltip;
155   };
156
157   function getPosition(node) {
158     var mode = d3.select(node).style('position');
159     if (mode === 'absolute' || mode === 'static') {
160       return {
161         x: node.offsetLeft,
162         y: node.offsetTop,
163         w: node.offsetWidth,
164         h: node.offsetHeight
165       };
166     } else {
167       return {
168         x: 0,
169         y: 0,
170         w: node.offsetWidth,
171         h: node.offsetHeight
172       };
173     }
174   }
175
176 })(this);
177 !function(){
178   var d3 = {version: "3.4.6"}; // semver
179 d3.ascending = d3_ascending;
180
181 function d3_ascending(a, b) {
182   return a < b ? -1 : a > b ? 1 : a >= b ? 0 : NaN;
183 }
184 d3.descending = function(a, b) {
185   return b < a ? -1 : b > a ? 1 : b >= a ? 0 : NaN;
186 };
187 d3.min = function(array, f) {
188   var i = -1,
189       n = array.length,
190       a,
191       b;
192   if (arguments.length === 1) {
193     while (++i < n && !((a = array[i]) != null && a <= a)) a = undefined;
194     while (++i < n) if ((b = array[i]) != null && a > b) a = b;
195   } else {
196     while (++i < n && !((a = f.call(array, array[i], i)) != null && a <= a)) a = undefined;
197     while (++i < n) if ((b = f.call(array, array[i], i)) != null && a > b) a = b;
198   }
199   return a;
200 };
201 d3.max = function(array, f) {
202   var i = -1,
203       n = array.length,
204       a,
205       b;
206   if (arguments.length === 1) {
207     while (++i < n && !((a = array[i]) != null && a <= a)) a = undefined;
208     while (++i < n) if ((b = array[i]) != null && b > a) a = b;
209   } else {
210     while (++i < n && !((a = f.call(array, array[i], i)) != null && a <= a)) a = undefined;
211     while (++i < n) if ((b = f.call(array, array[i], i)) != null && b > a) a = b;
212   }
213   return a;
214 };
215 d3.extent = function(array, f) {
216   var i = -1,
217       n = array.length,
218       a,
219       b,
220       c;
221   if (arguments.length === 1) {
222     while (++i < n && !((a = c = array[i]) != null && a <= a)) a = c = undefined;
223     while (++i < n) if ((b = array[i]) != null) {
224       if (a > b) a = b;
225       if (c < b) c = b;
226     }
227   } else {
228     while (++i < n && !((a = c = f.call(array, array[i], i)) != null && a <= a)) a = undefined;
229     while (++i < n) if ((b = f.call(array, array[i], i)) != null) {
230       if (a > b) a = b;
231       if (c < b) c = b;
232     }
233   }
234   return [a, c];
235 };
236 d3.sum = function(array, f) {
237   var s = 0,
238       n = array.length,
239       a,
240       i = -1;
241
242   if (arguments.length === 1) {
243     while (++i < n) if (!isNaN(a = +array[i])) s += a;
244   } else {
245     while (++i < n) if (!isNaN(a = +f.call(array, array[i], i))) s += a;
246   }
247
248   return s;
249 };
250 function d3_number(x) {
251   return x != null && !isNaN(x);
252 }
253
254 d3.mean = function(array, f) {
255   var s = 0,
256       n = array.length,
257       a,
258       i = -1,
259       j = n;
260   if (arguments.length === 1) {
261     while (++i < n) if (d3_number(a = array[i])) s += a; else --j;
262   } else {
263     while (++i < n) if (d3_number(a = f.call(array, array[i], i))) s += a; else --j;
264   }
265   return j ? s / j : undefined;
266 };
267 // R-7 per <http://en.wikipedia.org/wiki/Quantile>
268 d3.quantile = function(values, p) {
269   var H = (values.length - 1) * p + 1,
270       h = Math.floor(H),
271       v = +values[h - 1],
272       e = H - h;
273   return e ? v + e * (values[h] - v) : v;
274 };
275
276 d3.median = function(array, f) {
277   if (arguments.length > 1) array = array.map(f);
278   array = array.filter(d3_number);
279   return array.length ? d3.quantile(array.sort(d3_ascending), .5) : undefined;
280 };
281
282 function d3_bisector(compare) {
283   return {
284     left: function(a, x, lo, hi) {
285       if (arguments.length < 3) lo = 0;
286       if (arguments.length < 4) hi = a.length;
287       while (lo < hi) {
288         var mid = lo + hi >>> 1;
289         if (compare(a[mid], x) < 0) lo = mid + 1;
290         else hi = mid;
291       }
292       return lo;
293     },
294     right: function(a, x, lo, hi) {
295       if (arguments.length < 3) lo = 0;
296       if (arguments.length < 4) hi = a.length;
297       while (lo < hi) {
298         var mid = lo + hi >>> 1;
299         if (compare(a[mid], x) > 0) hi = mid;
300         else lo = mid + 1;
301       }
302       return lo;
303     }
304   };
305 }
306
307 var d3_bisect = d3_bisector(d3_ascending);
308 d3.bisectLeft = d3_bisect.left;
309 d3.bisect = d3.bisectRight = d3_bisect.right;
310
311 d3.bisector = function(f) {
312   return d3_bisector(f.length === 1
313       ? function(d, x) { return d3_ascending(f(d), x); }
314       : f);
315 };
316 d3.shuffle = function(array) {
317   var m = array.length, t, i;
318   while (m) {
319     i = Math.random() * m-- | 0;
320     t = array[m], array[m] = array[i], array[i] = t;
321   }
322   return array;
323 };
324 d3.permute = function(array, indexes) {
325   var i = indexes.length, permutes = new Array(i);
326   while (i--) permutes[i] = array[indexes[i]];
327   return permutes;
328 };
329 d3.pairs = function(array) {
330   var i = 0, n = array.length - 1, p0, p1 = array[0], pairs = new Array(n < 0 ? 0 : n);
331   while (i < n) pairs[i] = [p0 = p1, p1 = array[++i]];
332   return pairs;
333 };
334
335 d3.zip = function() {
336   if (!(n = arguments.length)) return [];
337   for (var i = -1, m = d3.min(arguments, d3_zipLength), zips = new Array(m); ++i < m;) {
338     for (var j = -1, n, zip = zips[i] = new Array(n); ++j < n;) {
339       zip[j] = arguments[j][i];
340     }
341   }
342   return zips;
343 };
344
345 function d3_zipLength(d) {
346   return d.length;
347 }
348
349 d3.transpose = function(matrix) {
350   return d3.zip.apply(d3, matrix);
351 };
352 d3.keys = function(map) {
353   var keys = [];
354   for (var key in map) keys.push(key);
355   return keys;
356 };
357 d3.values = function(map) {
358   var values = [];
359   for (var key in map) values.push(map[key]);
360   return values;
361 };
362 d3.entries = function(map) {
363   var entries = [];
364   for (var key in map) entries.push({key: key, value: map[key]});
365   return entries;
366 };
367 d3.merge = function(arrays) {
368   var n = arrays.length,
369       m,
370       i = -1,
371       j = 0,
372       merged,
373       array;
374
375   while (++i < n) j += arrays[i].length;
376   merged = new Array(j);
377
378   while (--n >= 0) {
379     array = arrays[n];
380     m = array.length;
381     while (--m >= 0) {
382       merged[--j] = array[m];
383     }
384   }
385
386   return merged;
387 };
388 var abs = Math.abs;
389
390 d3.range = function(start, stop, step) {
391   if (arguments.length < 3) {
392     step = 1;
393     if (arguments.length < 2) {
394       stop = start;
395       start = 0;
396     }
397   }
398   if ((stop - start) / step === Infinity) throw new Error("infinite range");
399   var range = [],
400        k = d3_range_integerScale(abs(step)),
401        i = -1,
402        j;
403   start *= k, stop *= k, step *= k;
404   if (step < 0) while ((j = start + step * ++i) > stop) range.push(j / k);
405   else while ((j = start + step * ++i) < stop) range.push(j / k);
406   return range;
407 };
408
409 function d3_range_integerScale(x) {
410   var k = 1;
411   while (x * k % 1) k *= 10;
412   return k;
413 }
414 function d3_class(ctor, properties) {
415   try {
416     for (var key in properties) {
417       Object.defineProperty(ctor.prototype, key, {
418         value: properties[key],
419         enumerable: false
420       });
421     }
422   } catch (e) {
423     ctor.prototype = properties;
424   }
425 }
426
427 d3.map = function(object) {
428   var map = new d3_Map;
429   if (object instanceof d3_Map) object.forEach(function(key, value) { map.set(key, value); });
430   else for (var key in object) map.set(key, object[key]);
431   return map;
432 };
433
434 function d3_Map() {}
435
436 d3_class(d3_Map, {
437   has: d3_map_has,
438   get: function(key) {
439     return this[d3_map_prefix + key];
440   },
441   set: function(key, value) {
442     return this[d3_map_prefix + key] = value;
443   },
444   remove: d3_map_remove,
445   keys: d3_map_keys,
446   values: function() {
447     var values = [];
448     this.forEach(function(key, value) { values.push(value); });
449     return values;
450   },
451   entries: function() {
452     var entries = [];
453     this.forEach(function(key, value) { entries.push({key: key, value: value}); });
454     return entries;
455   },
456   size: d3_map_size,
457   empty: d3_map_empty,
458   forEach: function(f) {
459     for (var key in this) if (key.charCodeAt(0) === d3_map_prefixCode) f.call(this, key.substring(1), this[key]);
460   }
461 });
462
463 var d3_map_prefix = "\0", // prevent collision with built-ins
464     d3_map_prefixCode = d3_map_prefix.charCodeAt(0);
465
466 function d3_map_has(key) {
467   return d3_map_prefix + key in this;
468 }
469
470 function d3_map_remove(key) {
471   key = d3_map_prefix + key;
472   return key in this && delete this[key];
473 }
474
475 function d3_map_keys() {
476   var keys = [];
477   this.forEach(function(key) { keys.push(key); });
478   return keys;
479 }
480
481 function d3_map_size() {
482   var size = 0;
483   for (var key in this) if (key.charCodeAt(0) === d3_map_prefixCode) ++size;
484   return size;
485 }
486
487 function d3_map_empty() {
488   for (var key in this) if (key.charCodeAt(0) === d3_map_prefixCode) return false;
489   return true;
490 }
491
492 d3.nest = function() {
493   var nest = {},
494       keys = [],
495       sortKeys = [],
496       sortValues,
497       rollup;
498
499   function map(mapType, array, depth) {
500     if (depth >= keys.length) return rollup
501         ? rollup.call(nest, array) : (sortValues
502         ? array.sort(sortValues)
503         : array);
504
505     var i = -1,
506         n = array.length,
507         key = keys[depth++],
508         keyValue,
509         object,
510         setter,
511         valuesByKey = new d3_Map,
512         values;
513
514     while (++i < n) {
515       if (values = valuesByKey.get(keyValue = key(object = array[i]))) {
516         values.push(object);
517       } else {
518         valuesByKey.set(keyValue, [object]);
519       }
520     }
521
522     if (mapType) {
523       object = mapType();
524       setter = function(keyValue, values) {
525         object.set(keyValue, map(mapType, values, depth));
526       };
527     } else {
528       object = {};
529       setter = function(keyValue, values) {
530         object[keyValue] = map(mapType, values, depth);
531       };
532     }
533
534     valuesByKey.forEach(setter);
535     return object;
536   }
537
538   function entries(map, depth) {
539     if (depth >= keys.length) return map;
540
541     var array = [],
542         sortKey = sortKeys[depth++];
543
544     map.forEach(function(key, keyMap) {
545       array.push({key: key, values: entries(keyMap, depth)});
546     });
547
548     return sortKey
549         ? array.sort(function(a, b) { return sortKey(a.key, b.key); })
550         : array;
551   }
552
553   nest.map = function(array, mapType) {
554     return map(mapType, array, 0);
555   };
556
557   nest.entries = function(array) {
558     return entries(map(d3.map, array, 0), 0);
559   };
560
561   nest.key = function(d) {
562     keys.push(d);
563     return nest;
564   };
565
566   // Specifies the order for the most-recently specified key.
567   // Note: only applies to entries. Map keys are unordered!
568   nest.sortKeys = function(order) {
569     sortKeys[keys.length - 1] = order;
570     return nest;
571   };
572
573   // Specifies the order for leaf values.
574   // Applies to both maps and entries array.
575   nest.sortValues = function(order) {
576     sortValues = order;
577     return nest;
578   };
579
580   nest.rollup = function(f) {
581     rollup = f;
582     return nest;
583   };
584
585   return nest;
586 };
587
588 d3.set = function(array) {
589   var set = new d3_Set;
590   if (array) for (var i = 0, n = array.length; i < n; ++i) set.add(array[i]);
591   return set;
592 };
593
594 function d3_Set() {}
595
596 d3_class(d3_Set, {
597   has: d3_map_has,
598   add: function(value) {
599     this[d3_map_prefix + value] = true;
600     return value;
601   },
602   remove: function(value) {
603     value = d3_map_prefix + value;
604     return value in this && delete this[value];
605   },
606   values: d3_map_keys,
607   size: d3_map_size,
608   empty: d3_map_empty,
609   forEach: function(f) {
610     for (var value in this) if (value.charCodeAt(0) === d3_map_prefixCode) f.call(this, value.substring(1));
611   }
612 });
613 d3.behavior = {};
614 var d3_arraySlice = [].slice,
615     d3_array = function(list) { return d3_arraySlice.call(list); }; // conversion for NodeLists
616
617 var d3_document = document,
618     d3_documentElement = d3_document.documentElement,
619     d3_window = window;
620
621 // Redefine d3_array if the browser doesn’t support slice-based conversion.
622 try {
623   d3_array(d3_documentElement.childNodes)[0].nodeType;
624 } catch(e) {
625   d3_array = function(list) {
626     var i = list.length, array = new Array(i);
627     while (i--) array[i] = list[i];
628     return array;
629   };
630 }
631 // Copies a variable number of methods from source to target.
632 d3.rebind = function(target, source) {
633   var i = 1, n = arguments.length, method;
634   while (++i < n) target[method = arguments[i]] = d3_rebind(target, source, source[method]);
635   return target;
636 };
637
638 // Method is assumed to be a standard D3 getter-setter:
639 // If passed with no arguments, gets the value.
640 // If passed with arguments, sets the value and returns the target.
641 function d3_rebind(target, source, method) {
642   return function() {
643     var value = method.apply(source, arguments);
644     return value === source ? target : value;
645   };
646 }
647
648 function d3_vendorSymbol(object, name) {
649   if (name in object) return name;
650   name = name.charAt(0).toUpperCase() + name.substring(1);
651   for (var i = 0, n = d3_vendorPrefixes.length; i < n; ++i) {
652     var prefixName = d3_vendorPrefixes[i] + name;
653     if (prefixName in object) return prefixName;
654   }
655 }
656
657 var d3_vendorPrefixes = ["webkit", "ms", "moz", "Moz", "o", "O"];
658 function d3_noop() {}
659
660 d3.dispatch = function() {
661   var dispatch = new d3_dispatch,
662       i = -1,
663       n = arguments.length;
664   while (++i < n) dispatch[arguments[i]] = d3_dispatch_event(dispatch);
665   return dispatch;
666 };
667
668 function d3_dispatch() {}
669
670 d3_dispatch.prototype.on = function(type, listener) {
671   var i = type.indexOf("."),
672       name = "";
673
674   // Extract optional namespace, e.g., "click.foo"
675   if (i >= 0) {
676     name = type.substring(i + 1);
677     type = type.substring(0, i);
678   }
679
680   if (type) return arguments.length < 2
681       ? this[type].on(name)
682       : this[type].on(name, listener);
683
684   if (arguments.length === 2) {
685     if (listener == null) for (type in this) {
686       if (this.hasOwnProperty(type)) this[type].on(name, null);
687     }
688     return this;
689   }
690 };
691
692 function d3_dispatch_event(dispatch) {
693   var listeners = [],
694       listenerByName = new d3_Map;
695
696   function event() {
697     var z = listeners, // defensive reference
698         i = -1,
699         n = z.length,
700         l;
701     while (++i < n) if (l = z[i].on) l.apply(this, arguments);
702     return dispatch;
703   }
704
705   event.on = function(name, listener) {
706     var l = listenerByName.get(name),
707         i;
708
709     // return the current listener, if any
710     if (arguments.length < 2) return l && l.on;
711
712     // remove the old listener, if any (with copy-on-write)
713     if (l) {
714       l.on = null;
715       listeners = listeners.slice(0, i = listeners.indexOf(l)).concat(listeners.slice(i + 1));
716       listenerByName.remove(name);
717     }
718
719     // add the new listener, if any
720     if (listener) listeners.push(listenerByName.set(name, {on: listener}));
721
722     return dispatch;
723   };
724
725   return event;
726 }
727
728 d3.event = null;
729
730 function d3_eventPreventDefault() {
731   d3.event.preventDefault();
732 }
733
734 function d3_eventCancel() {
735   d3.event.preventDefault();
736   d3.event.stopPropagation();
737 }
738
739 function d3_eventSource() {
740   var e = d3.event, s;
741   while (s = e.sourceEvent) e = s;
742   return e;
743 }
744
745 // Like d3.dispatch, but for custom events abstracting native UI events. These
746 // events have a target component (such as a brush), a target element (such as
747 // the svg:g element containing the brush) and the standard arguments `d` (the
748 // target element's data) and `i` (the selection index of the target element).
749 function d3_eventDispatch(target) {
750   var dispatch = new d3_dispatch,
751       i = 0,
752       n = arguments.length;
753
754   while (++i < n) dispatch[arguments[i]] = d3_dispatch_event(dispatch);
755
756   // Creates a dispatch context for the specified `thiz` (typically, the target
757   // DOM element that received the source event) and `argumentz` (typically, the
758   // data `d` and index `i` of the target element). The returned function can be
759   // used to dispatch an event to any registered listeners; the function takes a
760   // single argument as input, being the event to dispatch. The event must have
761   // a "type" attribute which corresponds to a type registered in the
762   // constructor. This context will automatically populate the "sourceEvent" and
763   // "target" attributes of the event, as well as setting the `d3.event` global
764   // for the duration of the notification.
765   dispatch.of = function(thiz, argumentz) {
766     return function(e1) {
767       try {
768         var e0 =
769         e1.sourceEvent = d3.event;
770         e1.target = target;
771         d3.event = e1;
772         dispatch[e1.type].apply(thiz, argumentz);
773       } finally {
774         d3.event = e0;
775       }
776     };
777   };
778
779   return dispatch;
780 }
781 d3.requote = function(s) {
782   return s.replace(d3_requote_re, "\\$&");
783 };
784
785 var d3_requote_re = /[\\\^\$\*\+\?\|\[\]\(\)\.\{\}]/g;
786 var d3_subclass = {}.__proto__?
787
788 // Until ECMAScript supports array subclassing, prototype injection works well.
789 function(object, prototype) {
790   object.__proto__ = prototype;
791 }:
792
793 // And if your browser doesn't support __proto__, we'll use direct extension.
794 function(object, prototype) {
795   for (var property in prototype) object[property] = prototype[property];
796 };
797
798 function d3_selection(groups) {
799   d3_subclass(groups, d3_selectionPrototype);
800   return groups;
801 }
802
803 var d3_select = function(s, n) { return n.querySelector(s); },
804     d3_selectAll = function(s, n) { return n.querySelectorAll(s); },
805     d3_selectMatcher = d3_documentElement[d3_vendorSymbol(d3_documentElement, "matchesSelector")],
806     d3_selectMatches = function(n, s) { return d3_selectMatcher.call(n, s); };
807
808 // Prefer Sizzle, if available.
809 if (typeof Sizzle === "function") {
810   d3_select = function(s, n) { return Sizzle(s, n)[0] || null; };
811   d3_selectAll = Sizzle;
812   d3_selectMatches = Sizzle.matchesSelector;
813 }
814
815 d3.selection = function() {
816   return d3_selectionRoot;
817 };
818
819 var d3_selectionPrototype = d3.selection.prototype = [];
820
821
822 d3_selectionPrototype.select = function(selector) {
823   var subgroups = [],
824       subgroup,
825       subnode,
826       group,
827       node;
828
829   selector = d3_selection_selector(selector);
830
831   for (var j = -1, m = this.length; ++j < m;) {
832     subgroups.push(subgroup = []);
833     subgroup.parentNode = (group = this[j]).parentNode;
834     for (var i = -1, n = group.length; ++i < n;) {
835       if (node = group[i]) {
836         subgroup.push(subnode = selector.call(node, node.__data__, i, j));
837         if (subnode && "__data__" in node) subnode.__data__ = node.__data__;
838       } else {
839         subgroup.push(null);
840       }
841     }
842   }
843
844   return d3_selection(subgroups);
845 };
846
847 function d3_selection_selector(selector) {
848   return typeof selector === "function" ? selector : function() {
849     return d3_select(selector, this);
850   };
851 }
852
853 d3_selectionPrototype.selectAll = function(selector) {
854   var subgroups = [],
855       subgroup,
856       node;
857
858   selector = d3_selection_selectorAll(selector);
859
860   for (var j = -1, m = this.length; ++j < m;) {
861     for (var group = this[j], i = -1, n = group.length; ++i < n;) {
862       if (node = group[i]) {
863         subgroups.push(subgroup = d3_array(selector.call(node, node.__data__, i, j)));
864         subgroup.parentNode = node;
865       }
866     }
867   }
868
869   return d3_selection(subgroups);
870 };
871
872 function d3_selection_selectorAll(selector) {
873   return typeof selector === "function" ? selector : function() {
874     return d3_selectAll(selector, this);
875   };
876 }
877 var d3_nsPrefix = {
878   svg: "http://www.w3.org/2000/svg",
879   xhtml: "http://www.w3.org/1999/xhtml",
880   xlink: "http://www.w3.org/1999/xlink",
881   xml: "http://www.w3.org/XML/1998/namespace",
882   xmlns: "http://www.w3.org/2000/xmlns/"
883 };
884
885 d3.ns = {
886   prefix: d3_nsPrefix,
887   qualify: function(name) {
888     var i = name.indexOf(":"),
889         prefix = name;
890     if (i >= 0) {
891       prefix = name.substring(0, i);
892       name = name.substring(i + 1);
893     }
894     return d3_nsPrefix.hasOwnProperty(prefix)
895         ? {space: d3_nsPrefix[prefix], local: name}
896         : name;
897   }
898 };
899
900 d3_selectionPrototype.attr = function(name, value) {
901   if (arguments.length < 2) {
902
903     // For attr(string), return the attribute value for the first node.
904     if (typeof name === "string") {
905       var node = this.node();
906       name = d3.ns.qualify(name);
907       return name.local
908           ? node.getAttributeNS(name.space, name.local)
909           : node.getAttribute(name);
910     }
911
912     // For attr(object), the object specifies the names and values of the
913     // attributes to set or remove. The values may be functions that are
914     // evaluated for each element.
915     for (value in name) this.each(d3_selection_attr(value, name[value]));
916     return this;
917   }
918
919   return this.each(d3_selection_attr(name, value));
920 };
921
922 function d3_selection_attr(name, value) {
923   name = d3.ns.qualify(name);
924
925   // For attr(string, null), remove the attribute with the specified name.
926   function attrNull() {
927     this.removeAttribute(name);
928   }
929   function attrNullNS() {
930     this.removeAttributeNS(name.space, name.local);
931   }
932
933   // For attr(string, string), set the attribute with the specified name.
934   function attrConstant() {
935     this.setAttribute(name, value);
936   }
937   function attrConstantNS() {
938     this.setAttributeNS(name.space, name.local, value);
939   }
940
941   // For attr(string, function), evaluate the function for each element, and set
942   // or remove the attribute as appropriate.
943   function attrFunction() {
944     var x = value.apply(this, arguments);
945     if (x == null) this.removeAttribute(name);
946     else this.setAttribute(name, x);
947   }
948   function attrFunctionNS() {
949     var x = value.apply(this, arguments);
950     if (x == null) this.removeAttributeNS(name.space, name.local);
951     else this.setAttributeNS(name.space, name.local, x);
952   }
953
954   return value == null
955       ? (name.local ? attrNullNS : attrNull) : (typeof value === "function"
956       ? (name.local ? attrFunctionNS : attrFunction)
957       : (name.local ? attrConstantNS : attrConstant));
958 }
959 function d3_collapse(s) {
960   return s.trim().replace(/\s+/g, " ");
961 }
962
963 d3_selectionPrototype.classed = function(name, value) {
964   if (arguments.length < 2) {
965
966     // For classed(string), return true only if the first node has the specified
967     // class or classes. Note that even if the browser supports DOMTokenList, it
968     // probably doesn't support it on SVG elements (which can be animated).
969     if (typeof name === "string") {
970       var node = this.node(),
971           n = (name = d3_selection_classes(name)).length,
972           i = -1;
973       if (value = node.classList) {
974         while (++i < n) if (!value.contains(name[i])) return false;
975       } else {
976         value = node.getAttribute("class");
977         while (++i < n) if (!d3_selection_classedRe(name[i]).test(value)) return false;
978       }
979       return true;
980     }
981
982     // For classed(object), the object specifies the names of classes to add or
983     // remove. The values may be functions that are evaluated for each element.
984     for (value in name) this.each(d3_selection_classed(value, name[value]));
985     return this;
986   }
987
988   // Otherwise, both a name and a value are specified, and are handled as below.
989   return this.each(d3_selection_classed(name, value));
990 };
991
992 function d3_selection_classedRe(name) {
993   return new RegExp("(?:^|\\s+)" + d3.requote(name) + "(?:\\s+|$)", "g");
994 }
995
996 function d3_selection_classes(name) {
997   return name.trim().split(/^|\s+/);
998 }
999
1000 // Multiple class names are allowed (e.g., "foo bar").
1001 function d3_selection_classed(name, value) {
1002   name = d3_selection_classes(name).map(d3_selection_classedName);
1003   var n = name.length;
1004
1005   function classedConstant() {
1006     var i = -1;
1007     while (++i < n) name[i](this, value);
1008   }
1009
1010   // When the value is a function, the function is still evaluated only once per
1011   // element even if there are multiple class names.
1012   function classedFunction() {
1013     var i = -1, x = value.apply(this, arguments);
1014     while (++i < n) name[i](this, x);
1015   }
1016
1017   return typeof value === "function"
1018       ? classedFunction
1019       : classedConstant;
1020 }
1021
1022 function d3_selection_classedName(name) {
1023   var re = d3_selection_classedRe(name);
1024   return function(node, value) {
1025     if (c = node.classList) return value ? c.add(name) : c.remove(name);
1026     var c = node.getAttribute("class") || "";
1027     if (value) {
1028       re.lastIndex = 0;
1029       if (!re.test(c)) node.setAttribute("class", d3_collapse(c + " " + name));
1030     } else {
1031       node.setAttribute("class", d3_collapse(c.replace(re, " ")));
1032     }
1033   };
1034 }
1035
1036 d3_selectionPrototype.style = function(name, value, priority) {
1037   var n = arguments.length;
1038   if (n < 3) {
1039
1040     // For style(object) or style(object, string), the object specifies the
1041     // names and values of the attributes to set or remove. The values may be
1042     // functions that are evaluated for each element. The optional string
1043     // specifies the priority.
1044     if (typeof name !== "string") {
1045       if (n < 2) value = "";
1046       for (priority in name) this.each(d3_selection_style(priority, name[priority], value));
1047       return this;
1048     }
1049
1050     // For style(string), return the computed style value for the first node.
1051     if (n < 2) return d3_window.getComputedStyle(this.node(), null).getPropertyValue(name);
1052
1053     // For style(string, string) or style(string, function), use the default
1054     // priority. The priority is ignored for style(string, null).
1055     priority = "";
1056   }
1057
1058   // Otherwise, a name, value and priority are specified, and handled as below.
1059   return this.each(d3_selection_style(name, value, priority));
1060 };
1061
1062 function d3_selection_style(name, value, priority) {
1063
1064   // For style(name, null) or style(name, null, priority), remove the style
1065   // property with the specified name. The priority is ignored.
1066   function styleNull() {
1067     this.style.removeProperty(name);
1068   }
1069
1070   // For style(name, string) or style(name, string, priority), set the style
1071   // property with the specified name, using the specified priority.
1072   function styleConstant() {
1073     this.style.setProperty(name, value, priority);
1074   }
1075
1076   // For style(name, function) or style(name, function, priority), evaluate the
1077   // function for each element, and set or remove the style property as
1078   // appropriate. When setting, use the specified priority.
1079   function styleFunction() {
1080     var x = value.apply(this, arguments);
1081     if (x == null) this.style.removeProperty(name);
1082     else this.style.setProperty(name, x, priority);
1083   }
1084
1085   return value == null
1086       ? styleNull : (typeof value === "function"
1087       ? styleFunction : styleConstant);
1088 }
1089
1090 d3_selectionPrototype.property = function(name, value) {
1091   if (arguments.length < 2) {
1092
1093     // For property(string), return the property value for the first node.
1094     if (typeof name === "string") return this.node()[name];
1095
1096     // For property(object), the object specifies the names and values of the
1097     // properties to set or remove. The values may be functions that are
1098     // evaluated for each element.
1099     for (value in name) this.each(d3_selection_property(value, name[value]));
1100     return this;
1101   }
1102
1103   // Otherwise, both a name and a value are specified, and are handled as below.
1104   return this.each(d3_selection_property(name, value));
1105 };
1106
1107 function d3_selection_property(name, value) {
1108
1109   // For property(name, null), remove the property with the specified name.
1110   function propertyNull() {
1111     delete this[name];
1112   }
1113
1114   // For property(name, string), set the property with the specified name.
1115   function propertyConstant() {
1116     this[name] = value;
1117   }
1118
1119   // For property(name, function), evaluate the function for each element, and
1120   // set or remove the property as appropriate.
1121   function propertyFunction() {
1122     var x = value.apply(this, arguments);
1123     if (x == null) delete this[name];
1124     else this[name] = x;
1125   }
1126
1127   return value == null
1128       ? propertyNull : (typeof value === "function"
1129       ? propertyFunction : propertyConstant);
1130 }
1131
1132 d3_selectionPrototype.text = function(value) {
1133   return arguments.length
1134       ? this.each(typeof value === "function"
1135       ? function() { var v = value.apply(this, arguments); this.textContent = v == null ? "" : v; } : value == null
1136       ? function() { if (this.textContent !== "") this.textContent = ""; }
1137       : function() { if (this.textContent !== value) this.textContent = value; })
1138       : this.node().textContent;
1139 };
1140
1141 d3_selectionPrototype.html = function(value) {
1142   return arguments.length
1143       ? this.each(typeof value === "function"
1144       ? function() { var v = value.apply(this, arguments); this.innerHTML = v == null ? "" : v; } : value == null
1145       ? function() { this.innerHTML = ""; }
1146       : function() { this.innerHTML = value; })
1147       : this.node().innerHTML;
1148 };
1149
1150 d3_selectionPrototype.append = function(name) {
1151   name = d3_selection_creator(name);
1152   return this.select(function() {
1153     return this.appendChild(name.apply(this, arguments));
1154   });
1155 };
1156
1157 function d3_selection_creator(name) {
1158   return typeof name === "function" ? name
1159       : (name = d3.ns.qualify(name)).local ? function() { return this.ownerDocument.createElementNS(name.space, name.local); }
1160       : function() { return this.ownerDocument.createElementNS(this.namespaceURI, name); };
1161 }
1162
1163 d3_selectionPrototype.insert = function(name, before) {
1164   name = d3_selection_creator(name);
1165   before = d3_selection_selector(before);
1166   return this.select(function() {
1167     return this.insertBefore(name.apply(this, arguments), before.apply(this, arguments) || null);
1168   });
1169 };
1170
1171 // TODO remove(selector)?
1172 // TODO remove(node)?
1173 // TODO remove(function)?
1174 d3_selectionPrototype.remove = function() {
1175   return this.each(function() {
1176     var parent = this.parentNode;
1177     if (parent) parent.removeChild(this);
1178   });
1179 };
1180
1181 d3_selectionPrototype.data = function(value, key) {
1182   var i = -1,
1183       n = this.length,
1184       group,
1185       node;
1186
1187   // If no value is specified, return the first value.
1188   if (!arguments.length) {
1189     value = new Array(n = (group = this[0]).length);
1190     while (++i < n) {
1191       if (node = group[i]) {
1192         value[i] = node.__data__;
1193       }
1194     }
1195     return value;
1196   }
1197
1198   function bind(group, groupData) {
1199     var i,
1200         n = group.length,
1201         m = groupData.length,
1202         n0 = Math.min(n, m),
1203         updateNodes = new Array(m),
1204         enterNodes = new Array(m),
1205         exitNodes = new Array(n),
1206         node,
1207         nodeData;
1208
1209     if (key) {
1210       var nodeByKeyValue = new d3_Map,
1211           dataByKeyValue = new d3_Map,
1212           keyValues = [],
1213           keyValue;
1214
1215       for (i = -1; ++i < n;) {
1216         keyValue = key.call(node = group[i], node.__data__, i);
1217         if (nodeByKeyValue.has(keyValue)) {
1218           exitNodes[i] = node; // duplicate selection key
1219         } else {
1220           nodeByKeyValue.set(keyValue, node);
1221         }
1222         keyValues.push(keyValue);
1223       }
1224
1225       for (i = -1; ++i < m;) {
1226         keyValue = key.call(groupData, nodeData = groupData[i], i);
1227         if (node = nodeByKeyValue.get(keyValue)) {
1228           updateNodes[i] = node;
1229           node.__data__ = nodeData;
1230         } else if (!dataByKeyValue.has(keyValue)) { // no duplicate data key
1231           enterNodes[i] = d3_selection_dataNode(nodeData);
1232         }
1233         dataByKeyValue.set(keyValue, nodeData);
1234         nodeByKeyValue.remove(keyValue);
1235       }
1236
1237       for (i = -1; ++i < n;) {
1238         if (nodeByKeyValue.has(keyValues[i])) {
1239           exitNodes[i] = group[i];
1240         }
1241       }
1242     } else {
1243       for (i = -1; ++i < n0;) {
1244         node = group[i];
1245         nodeData = groupData[i];
1246         if (node) {
1247           node.__data__ = nodeData;
1248           updateNodes[i] = node;
1249         } else {
1250           enterNodes[i] = d3_selection_dataNode(nodeData);
1251         }
1252       }
1253       for (; i < m; ++i) {
1254         enterNodes[i] = d3_selection_dataNode(groupData[i]);
1255       }
1256       for (; i < n; ++i) {
1257         exitNodes[i] = group[i];
1258       }
1259     }
1260
1261     enterNodes.update
1262         = updateNodes;
1263
1264     enterNodes.parentNode
1265         = updateNodes.parentNode
1266         = exitNodes.parentNode
1267         = group.parentNode;
1268
1269     enter.push(enterNodes);
1270     update.push(updateNodes);
1271     exit.push(exitNodes);
1272   }
1273
1274   var enter = d3_selection_enter([]),
1275       update = d3_selection([]),
1276       exit = d3_selection([]);
1277
1278   if (typeof value === "function") {
1279     while (++i < n) {
1280       bind(group = this[i], value.call(group, group.parentNode.__data__, i));
1281     }
1282   } else {
1283     while (++i < n) {
1284       bind(group = this[i], value);
1285     }
1286   }
1287
1288   update.enter = function() { return enter; };
1289   update.exit = function() { return exit; };
1290   return update;
1291 };
1292
1293 function d3_selection_dataNode(data) {
1294   return {__data__: data};
1295 }
1296
1297 d3_selectionPrototype.datum = function(value) {
1298   return arguments.length
1299       ? this.property("__data__", value)
1300       : this.property("__data__");
1301 };
1302
1303 d3_selectionPrototype.filter = function(filter) {
1304   var subgroups = [],
1305       subgroup,
1306       group,
1307       node;
1308
1309   if (typeof filter !== "function") filter = d3_selection_filter(filter);
1310
1311   for (var j = 0, m = this.length; j < m; j++) {
1312     subgroups.push(subgroup = []);
1313     subgroup.parentNode = (group = this[j]).parentNode;
1314     for (var i = 0, n = group.length; i < n; i++) {
1315       if ((node = group[i]) && filter.call(node, node.__data__, i, j)) {
1316         subgroup.push(node);
1317       }
1318     }
1319   }
1320
1321   return d3_selection(subgroups);
1322 };
1323
1324 function d3_selection_filter(selector) {
1325   return function() {
1326     return d3_selectMatches(this, selector);
1327   };
1328 }
1329
1330 d3_selectionPrototype.order = function() {
1331   for (var j = -1, m = this.length; ++j < m;) {
1332     for (var group = this[j], i = group.length - 1, next = group[i], node; --i >= 0;) {
1333       if (node = group[i]) {
1334         if (next && next !== node.nextSibling) next.parentNode.insertBefore(node, next);
1335         next = node;
1336       }
1337     }
1338   }
1339   return this;
1340 };
1341
1342 d3_selectionPrototype.sort = function(comparator) {
1343   comparator = d3_selection_sortComparator.apply(this, arguments);
1344   for (var j = -1, m = this.length; ++j < m;) this[j].sort(comparator);
1345   return this.order();
1346 };
1347
1348 function d3_selection_sortComparator(comparator) {
1349   if (!arguments.length) comparator = d3_ascending;
1350   return function(a, b) {
1351     return a && b ? comparator(a.__data__, b.__data__) : !a - !b;
1352   };
1353 }
1354
1355 d3_selectionPrototype.each = function(callback) {
1356   return d3_selection_each(this, function(node, i, j) {
1357     callback.call(node, node.__data__, i, j);
1358   });
1359 };
1360
1361 function d3_selection_each(groups, callback) {
1362   for (var j = 0, m = groups.length; j < m; j++) {
1363     for (var group = groups[j], i = 0, n = group.length, node; i < n; i++) {
1364       if (node = group[i]) callback(node, i, j);
1365     }
1366   }
1367   return groups;
1368 }
1369
1370 d3_selectionPrototype.call = function(callback) {
1371   var args = d3_array(arguments);
1372   callback.apply(args[0] = this, args);
1373   return this;
1374 };
1375
1376 d3_selectionPrototype.empty = function() {
1377   return !this.node();
1378 };
1379
1380 d3_selectionPrototype.node = function() {
1381   for (var j = 0, m = this.length; j < m; j++) {
1382     for (var group = this[j], i = 0, n = group.length; i < n; i++) {
1383       var node = group[i];
1384       if (node) return node;
1385     }
1386   }
1387   return null;
1388 };
1389
1390 d3_selectionPrototype.size = function() {
1391   var n = 0;
1392   this.each(function() { ++n; });
1393   return n;
1394 };
1395
1396 function d3_selection_enter(selection) {
1397   d3_subclass(selection, d3_selection_enterPrototype);
1398   return selection;
1399 }
1400
1401 var d3_selection_enterPrototype = [];
1402
1403 d3.selection.enter = d3_selection_enter;
1404 d3.selection.enter.prototype = d3_selection_enterPrototype;
1405
1406 d3_selection_enterPrototype.append = d3_selectionPrototype.append;
1407 d3_selection_enterPrototype.empty = d3_selectionPrototype.empty;
1408 d3_selection_enterPrototype.node = d3_selectionPrototype.node;
1409 d3_selection_enterPrototype.call = d3_selectionPrototype.call;
1410 d3_selection_enterPrototype.size = d3_selectionPrototype.size;
1411
1412
1413 d3_selection_enterPrototype.select = function(selector) {
1414   var subgroups = [],
1415       subgroup,
1416       subnode,
1417       upgroup,
1418       group,
1419       node;
1420
1421   for (var j = -1, m = this.length; ++j < m;) {
1422     upgroup = (group = this[j]).update;
1423     subgroups.push(subgroup = []);
1424     subgroup.parentNode = group.parentNode;
1425     for (var i = -1, n = group.length; ++i < n;) {
1426       if (node = group[i]) {
1427         subgroup.push(upgroup[i] = subnode = selector.call(group.parentNode, node.__data__, i, j));
1428         subnode.__data__ = node.__data__;
1429       } else {
1430         subgroup.push(null);
1431       }
1432     }
1433   }
1434
1435   return d3_selection(subgroups);
1436 };
1437
1438 d3_selection_enterPrototype.insert = function(name, before) {
1439   if (arguments.length < 2) before = d3_selection_enterInsertBefore(this);
1440   return d3_selectionPrototype.insert.call(this, name, before);
1441 };
1442
1443 function d3_selection_enterInsertBefore(enter) {
1444   var i0, j0;
1445   return function(d, i, j) {
1446     var group = enter[j].update,
1447         n = group.length,
1448         node;
1449     if (j != j0) j0 = j, i0 = 0;
1450     if (i >= i0) i0 = i + 1;
1451     while (!(node = group[i0]) && ++i0 < n);
1452     return node;
1453   };
1454 }
1455
1456 // import "../transition/transition";
1457
1458 d3_selectionPrototype.transition = function() {
1459   var id = d3_transitionInheritId || ++d3_transitionId,
1460       subgroups = [],
1461       subgroup,
1462       node,
1463       transition = d3_transitionInherit || {time: Date.now(), ease: d3_ease_cubicInOut, delay: 0, duration: 250};
1464
1465   for (var j = -1, m = this.length; ++j < m;) {
1466     subgroups.push(subgroup = []);
1467     for (var group = this[j], i = -1, n = group.length; ++i < n;) {
1468       if (node = group[i]) d3_transitionNode(node, i, id, transition);
1469       subgroup.push(node);
1470     }
1471   }
1472
1473   return d3_transition(subgroups, id);
1474 };
1475 // import "../transition/transition";
1476
1477 d3_selectionPrototype.interrupt = function() {
1478   return this.each(d3_selection_interrupt);
1479 };
1480
1481 function d3_selection_interrupt() {
1482   var lock = this.__transition__;
1483   if (lock) ++lock.active;
1484 }
1485
1486 // TODO fast singleton implementation?
1487 d3.select = function(node) {
1488   var group = [typeof node === "string" ? d3_select(node, d3_document) : node];
1489   group.parentNode = d3_documentElement;
1490   return d3_selection([group]);
1491 };
1492
1493 d3.selectAll = function(nodes) {
1494   var group = d3_array(typeof nodes === "string" ? d3_selectAll(nodes, d3_document) : nodes);
1495   group.parentNode = d3_documentElement;
1496   return d3_selection([group]);
1497 };
1498
1499 var d3_selectionRoot = d3.select(d3_documentElement);
1500
1501 d3_selectionPrototype.on = function(type, listener, capture) {
1502   var n = arguments.length;
1503   if (n < 3) {
1504
1505     // For on(object) or on(object, boolean), the object specifies the event
1506     // types and listeners to add or remove. The optional boolean specifies
1507     // whether the listener captures events.
1508     if (typeof type !== "string") {
1509       if (n < 2) listener = false;
1510       for (capture in type) this.each(d3_selection_on(capture, type[capture], listener));
1511       return this;
1512     }
1513
1514     // For on(string), return the listener for the first node.
1515     if (n < 2) return (n = this.node()["__on" + type]) && n._;
1516
1517     // For on(string, function), use the default capture.
1518     capture = false;
1519   }
1520
1521   // Otherwise, a type, listener and capture are specified, and handled as below.
1522   return this.each(d3_selection_on(type, listener, capture));
1523 };
1524
1525 function d3_selection_on(type, listener, capture) {
1526   var name = "__on" + type,
1527       i = type.indexOf("."),
1528       wrap = d3_selection_onListener;
1529
1530   if (i > 0) type = type.substring(0, i);
1531   var filter = d3_selection_onFilters.get(type);
1532   if (filter) type = filter, wrap = d3_selection_onFilter;
1533
1534   function onRemove() {
1535     var l = this[name];
1536     if (l) {
1537       this.removeEventListener(type, l, l.$);
1538       delete this[name];
1539     }
1540   }
1541
1542   function onAdd() {
1543     var l = wrap(listener, d3_array(arguments));
1544     if (typeof Raven !== 'undefined') l = Raven.wrap(l);
1545     onRemove.call(this);
1546     this.addEventListener(type, this[name] = l, l.$ = capture);
1547     l._ = listener;
1548   }
1549
1550   function removeAll() {
1551     var re = new RegExp("^__on([^.]+)" + d3.requote(type) + "$"),
1552         match;
1553     for (var name in this) {
1554       if (match = name.match(re)) {
1555         var l = this[name];
1556         this.removeEventListener(match[1], l, l.$);
1557         delete this[name];
1558       }
1559     }
1560   }
1561
1562   return i
1563       ? listener ? onAdd : onRemove
1564       : listener ? d3_noop : removeAll;
1565 }
1566
1567 var d3_selection_onFilters = d3.map({
1568   mouseenter: "mouseover",
1569   mouseleave: "mouseout"
1570 });
1571
1572 d3_selection_onFilters.forEach(function(k) {
1573   if ("on" + k in d3_document) d3_selection_onFilters.remove(k);
1574 });
1575
1576 function d3_selection_onListener(listener, argumentz) {
1577   return function(e) {
1578     var o = d3.event; // Events can be reentrant (e.g., focus).
1579     d3.event = e;
1580     argumentz[0] = this.__data__;
1581     try {
1582       listener.apply(this, argumentz);
1583     } finally {
1584       d3.event = o;
1585     }
1586   };
1587 }
1588
1589 function d3_selection_onFilter(listener, argumentz) {
1590   var l = d3_selection_onListener(listener, argumentz);
1591   return function(e) {
1592     var target = this, related = e.relatedTarget;
1593     if (!related || (related !== target && !(related.compareDocumentPosition(target) & 8))) {
1594       l.call(target, e);
1595     }
1596   };
1597 }
1598
1599 var d3_event_dragSelect = "onselectstart" in d3_document ? null : d3_vendorSymbol(d3_documentElement.style, "userSelect"),
1600     d3_event_dragId = 0;
1601
1602 function d3_event_dragSuppress() {
1603   var name = ".dragsuppress-" + ++d3_event_dragId,
1604       click = "click" + name,
1605       w = d3.select(d3_window)
1606           .on("touchmove" + name, d3_eventPreventDefault)
1607           .on("dragstart" + name, d3_eventPreventDefault)
1608           .on("selectstart" + name, d3_eventPreventDefault);
1609   if (d3_event_dragSelect) {
1610     var style = d3_documentElement.style,
1611         select = style[d3_event_dragSelect];
1612     style[d3_event_dragSelect] = "none";
1613   }
1614   return function(suppressClick) {
1615     w.on(name, null);
1616     if (d3_event_dragSelect) style[d3_event_dragSelect] = select;
1617     if (suppressClick) { // suppress the next click, but only if it’s immediate
1618       function off() { w.on(click, null); }
1619       w.on(click, function() { d3_eventCancel(); off(); }, true);
1620       setTimeout(off, 0);
1621     }
1622   };
1623 }
1624
1625 d3.mouse = function(container) {
1626   return d3_mousePoint(container, d3_eventSource());
1627 };
1628
1629 function d3_mousePoint(container, e) {
1630   if (e.changedTouches) e = e.changedTouches[0];
1631   var svg = container.ownerSVGElement || container;
1632   if (svg.createSVGPoint) {
1633     var point = svg.createSVGPoint();
1634     point.x = e.clientX, point.y = e.clientY;
1635     point = point.matrixTransform(container.getScreenCTM().inverse());
1636     return [point.x, point.y];
1637   }
1638   var rect = container.getBoundingClientRect();
1639   return [e.clientX - rect.left - container.clientLeft, e.clientY - rect.top - container.clientTop];
1640 };
1641
1642 d3.touches = function(container, touches) {
1643   if (arguments.length < 2) touches = d3_eventSource().touches;
1644   return touches ? d3_array(touches).map(function(touch) {
1645     var point = d3_mousePoint(container, touch);
1646     point.identifier = touch.identifier;
1647     return point;
1648   }) : [];
1649 };
1650 var π = Math.PI,
1651     τ = 2 * π,
1652     halfπ = π / 2,
1653     ε = 1e-6,
1654     ε2 = ε * ε,
1655     d3_radians = π / 180,
1656     d3_degrees = 180 / π;
1657
1658 function d3_sgn(x) {
1659   return x > 0 ? 1 : x < 0 ? -1 : 0;
1660 }
1661
1662 // Returns the 2D cross product of AB and AC vectors, i.e., the z-component of
1663 // the 3D cross product in a quadrant I Cartesian coordinate system (+x is
1664 // right, +y is up). Returns a positive value if ABC is counter-clockwise,
1665 // negative if clockwise, and zero if the points are collinear.
1666 function d3_cross2d(a, b, c) {
1667   return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
1668 }
1669
1670 function d3_acos(x) {
1671   return x > 1 ? 0 : x < -1 ? π : Math.acos(x);
1672 }
1673
1674 function d3_asin(x) {
1675   return x > 1 ? halfπ : x < -1 ? -halfπ : Math.asin(x);
1676 }
1677
1678 function d3_sinh(x) {
1679   return ((x = Math.exp(x)) - 1 / x) / 2;
1680 }
1681
1682 function d3_cosh(x) {
1683   return ((x = Math.exp(x)) + 1 / x) / 2;
1684 }
1685
1686 function d3_tanh(x) {
1687   return ((x = Math.exp(2 * x)) - 1) / (x + 1);
1688 }
1689
1690 function d3_haversin(x) {
1691   return (x = Math.sin(x / 2)) * x;
1692 }
1693
1694 var ρ = Math.SQRT2,
1695     ρ2 = 2,
1696     ρ4 = 4;
1697
1698 // p0 = [ux0, uy0, w0]
1699 // p1 = [ux1, uy1, w1]
1700 d3.interpolateZoom = function(p0, p1) {
1701   var ux0 = p0[0], uy0 = p0[1], w0 = p0[2],
1702       ux1 = p1[0], uy1 = p1[1], w1 = p1[2];
1703
1704   var dx = ux1 - ux0,
1705       dy = uy1 - uy0,
1706       d2 = dx * dx + dy * dy,
1707       d1 = Math.sqrt(d2),
1708       b0 = (w1 * w1 - w0 * w0 + ρ4 * d2) / (2 * w0 * ρ2 * d1),
1709       b1 = (w1 * w1 - w0 * w0 - ρ4 * d2) / (2 * w1 * ρ2 * d1),
1710       r0 = Math.log(Math.sqrt(b0 * b0 + 1) - b0),
1711       r1 = Math.log(Math.sqrt(b1 * b1 + 1) - b1),
1712       dr = r1 - r0,
1713       S = (dr || Math.log(w1 / w0)) / ρ;
1714
1715   function interpolate(t) {
1716     var s = t * S;
1717     if (dr) {
1718       // General case.
1719       var coshr0 = d3_cosh(r0),
1720           u = w0 / (ρ2 * d1) * (coshr0 * d3_tanh(ρ * s + r0) - d3_sinh(r0));
1721       return [
1722         ux0 + u * dx,
1723         uy0 + u * dy,
1724         w0 * coshr0 / d3_cosh(ρ * s + r0)
1725       ];
1726     }
1727     // Special case for u0 ~= u1.
1728     return [
1729       ux0 + t * dx,
1730       uy0 + t * dy,
1731       w0 * Math.exp(ρ * s)
1732     ];
1733   }
1734
1735   interpolate.duration = S * 1000;
1736
1737   return interpolate;
1738 };
1739
1740 d3.behavior.zoom = function() {
1741   var view = {x: 0, y: 0, k: 1},
1742       translate0, // translate when we started zooming (to avoid drift)
1743       center, // desired position of translate0 after zooming
1744       size = [960, 500], // viewport size; required for zoom interpolation
1745       scaleExtent = d3_behavior_zoomInfinity,
1746       mousedown = "mousedown.zoom",
1747       mousemove = "mousemove.zoom",
1748       mouseup = "mouseup.zoom",
1749       mousewheelTimer,
1750       touchstart = "touchstart.zoom",
1751       touchtime, // time of last touchstart (to detect double-tap)
1752       event = d3_eventDispatch(zoom, "zoomstart", "zoom", "zoomend"),
1753       x0,
1754       x1,
1755       y0,
1756       y1;
1757
1758   function zoom(g) {
1759     g   .on(mousedown, mousedowned)
1760         .on(d3_behavior_zoomWheel + ".zoom", mousewheeled)
1761         .on(mousemove, mousewheelreset)
1762         .on("dblclick.zoom", dblclicked)
1763         .on(touchstart, touchstarted);
1764   }
1765
1766   zoom.event = function(g) {
1767     g.each(function() {
1768       var dispatch = event.of(this, arguments),
1769           view1 = view;
1770       if (d3_transitionInheritId) {
1771         d3.select(this).transition()
1772             .each("start.zoom", function() {
1773               view = this.__chart__ || {x: 0, y: 0, k: 1}; // pre-transition state
1774               zoomstarted(dispatch);
1775             })
1776             .tween("zoom:zoom", function() {
1777               var dx = size[0],
1778                   dy = size[1],
1779                   cx = dx / 2,
1780                   cy = dy / 2,
1781                   i = d3.interpolateZoom(
1782                     [(cx - view.x) / view.k, (cy - view.y) / view.k, dx / view.k],
1783                     [(cx - view1.x) / view1.k, (cy - view1.y) / view1.k, dx / view1.k]
1784                   );
1785               return function(t) {
1786                 var l = i(t), k = dx / l[2];
1787                 this.__chart__ = view = {x: cx - l[0] * k, y: cy - l[1] * k, k: k};
1788                 zoomed(dispatch);
1789               };
1790             })
1791             .each("end.zoom", function() {
1792               zoomended(dispatch);
1793             });
1794       } else {
1795         this.__chart__ = view;
1796         zoomstarted(dispatch);
1797         zoomed(dispatch);
1798         zoomended(dispatch);
1799       }
1800     });
1801   }
1802
1803   zoom.translate = function(_) {
1804     if (!arguments.length) return [view.x, view.y];
1805     view = {x: +_[0], y: +_[1], k: view.k}; // copy-on-write
1806     rescale();
1807     return zoom;
1808   };
1809
1810   zoom.scale = function(_) {
1811     if (!arguments.length) return view.k;
1812     view = {x: view.x, y: view.y, k: +_}; // copy-on-write
1813     rescale();
1814     return zoom;
1815   };
1816
1817   zoom.scaleExtent = function(_) {
1818     if (!arguments.length) return scaleExtent;
1819     scaleExtent = _ == null ? d3_behavior_zoomInfinity : [+_[0], +_[1]];
1820     return zoom;
1821   };
1822
1823   zoom.center = function(_) {
1824     if (!arguments.length) return center;
1825     center = _ && [+_[0], +_[1]];
1826     return zoom;
1827   };
1828
1829   zoom.size = function(_) {
1830     if (!arguments.length) return size;
1831     size = _ && [+_[0], +_[1]];
1832     return zoom;
1833   };
1834
1835   zoom.x = function(z) {
1836     if (!arguments.length) return x1;
1837     x1 = z;
1838     x0 = z.copy();
1839     view = {x: 0, y: 0, k: 1}; // copy-on-write
1840     return zoom;
1841   };
1842
1843   zoom.y = function(z) {
1844     if (!arguments.length) return y1;
1845     y1 = z;
1846     y0 = z.copy();
1847     view = {x: 0, y: 0, k: 1}; // copy-on-write
1848     return zoom;
1849   };
1850
1851   function location(p) {
1852     return [(p[0] - view.x) / view.k, (p[1] - view.y) / view.k];
1853   }
1854
1855   function point(l) {
1856     return [l[0] * view.k + view.x, l[1] * view.k + view.y];
1857   }
1858
1859   function scaleTo(s) {
1860     view.k = Math.max(scaleExtent[0], Math.min(scaleExtent[1], s));
1861   }
1862
1863   function translateTo(p, l) {
1864     l = point(l);
1865     view.x += p[0] - l[0];
1866     view.y += p[1] - l[1];
1867   }
1868
1869   function rescale() {
1870     if (x1) x1.domain(x0.range().map(function(x) { return (x - view.x) / view.k; }).map(x0.invert));
1871     if (y1) y1.domain(y0.range().map(function(y) { return (y - view.y) / view.k; }).map(y0.invert));
1872   }
1873
1874   function zoomstarted(dispatch) {
1875     dispatch({type: "zoomstart"});
1876   }
1877
1878   function zoomed(dispatch) {
1879     rescale();
1880     dispatch({type: "zoom", scale: view.k, translate: [view.x, view.y]});
1881   }
1882
1883   function zoomended(dispatch) {
1884     dispatch({type: "zoomend"});
1885   }
1886
1887   function mousedowned() {
1888     var that = this,
1889         target = d3.event.target,
1890         dispatch = event.of(that, arguments),
1891         dragged = 0,
1892         subject = d3.select(d3_window).on(mousemove, moved).on(mouseup, ended),
1893         location0 = location(d3.mouse(that)),
1894         dragRestore = d3_event_dragSuppress();
1895
1896     d3_selection_interrupt.call(that);
1897     zoomstarted(dispatch);
1898
1899     function moved() {
1900       dragged = 1;
1901       translateTo(d3.mouse(that), location0);
1902       zoomed(dispatch);
1903     }
1904
1905     function ended() {
1906       subject.on(mousemove, d3_window === that ? mousewheelreset : null).on(mouseup, null);
1907       dragRestore(dragged && d3.event.target === target);
1908       zoomended(dispatch);
1909     }
1910   }
1911
1912   // These closures persist for as long as at least one touch is active.
1913   function touchstarted() {
1914     var that = this,
1915         dispatch = event.of(that, arguments),
1916         locations0 = {}, // touchstart locations
1917         distance0 = 0, // distance² between initial touches
1918         scale0, // scale when we started touching
1919         zoomName = ".zoom-" + d3.event.changedTouches[0].identifier,
1920         touchmove = "touchmove" + zoomName,
1921         touchend = "touchend" + zoomName,
1922         target = d3.select(d3.event.target).on(touchmove, moved).on(touchend, ended),
1923         subject = d3.select(that).on(mousedown, null).on(touchstart, started), // prevent duplicate events
1924         dragRestore = d3_event_dragSuppress();
1925
1926     d3_selection_interrupt.call(that);
1927     started();
1928     zoomstarted(dispatch);
1929
1930     // Updates locations of any touches in locations0.
1931     function relocate() {
1932       var touches = d3.touches(that);
1933       scale0 = view.k;
1934       touches.forEach(function(t) {
1935         if (t.identifier in locations0) locations0[t.identifier] = location(t);
1936       });
1937       return touches;
1938     }
1939
1940     // Temporarily override touchstart while gesture is active.
1941     function started() {
1942       // Only track touches started on the target element.
1943       var changed = d3.event.changedTouches;
1944       for (var i = 0, n = changed.length; i < n; ++i) {
1945         locations0[changed[i].identifier] = null;
1946       }
1947
1948       var touches = relocate(),
1949           now = Date.now();
1950
1951       if (touches.length === 1) {
1952         if (now - touchtime < 500) { // dbltap
1953           var p = touches[0], l = locations0[p.identifier];
1954           scaleTo(view.k * 2);
1955           translateTo(p, l);
1956           d3_eventPreventDefault();
1957           zoomed(dispatch);
1958         }
1959         touchtime = now;
1960       } else if (touches.length > 1) {
1961         var p = touches[0], q = touches[1],
1962             dx = p[0] - q[0], dy = p[1] - q[1];
1963         distance0 = dx * dx + dy * dy;
1964       }
1965     }
1966
1967     function moved() {
1968       var touches = d3.touches(that),
1969           p0, l0,
1970           p1, l1;
1971       for (var i = 0, n = touches.length; i < n; ++i, l1 = null) {
1972         p1 = touches[i];
1973         if (l1 = locations0[p1.identifier]) {
1974           if (l0) break;
1975           p0 = p1, l0 = l1;
1976         }
1977       }
1978
1979       if (l1) {
1980         var distance1 = (distance1 = p1[0] - p0[0]) * distance1 + (distance1 = p1[1] - p0[1]) * distance1,
1981             scale1 = distance0 && Math.sqrt(distance1 / distance0);
1982         p0 = [(p0[0] + p1[0]) / 2, (p0[1] + p1[1]) / 2];
1983         l0 = [(l0[0] + l1[0]) / 2, (l0[1] + l1[1]) / 2];
1984         scaleTo(scale1 * scale0);
1985       }
1986
1987       touchtime = null;
1988       translateTo(p0, l0);
1989       zoomed(dispatch);
1990     }
1991
1992     function ended() {
1993       // If there are any globally-active touches remaining, remove the ended
1994       // touches from locations0.
1995       if (d3.event.touches.length) {
1996         var changed = d3.event.changedTouches;
1997         for (var i = 0, n = changed.length; i < n; ++i) {
1998           delete locations0[changed[i].identifier];
1999         }
2000         // If locations0 is not empty, then relocate and continue listening for
2001         // touchmove and touchend.
2002         for (var identifier in locations0) {
2003           return void relocate(); // locations may have detached due to rotation
2004         }
2005       }
2006       // Otherwise, remove touchmove and touchend listeners.
2007       target.on(zoomName, null);
2008       subject.on(mousedown, mousedowned).on(touchstart, touchstarted);
2009       dragRestore();
2010       zoomended(dispatch);
2011     }
2012   }
2013
2014   function mousewheeled() {
2015     var dispatch = event.of(this, arguments);
2016     if (mousewheelTimer) clearTimeout(mousewheelTimer);
2017     else d3_selection_interrupt.call(this), zoomstarted(dispatch);
2018     mousewheelTimer = setTimeout(function() { mousewheelTimer = null; zoomended(dispatch); }, 50);
2019     d3_eventPreventDefault();
2020     var point = center || d3.mouse(this);
2021     if (!translate0) translate0 = location(point);
2022     scaleTo(Math.pow(2, d3_behavior_zoomDelta() * .002) * view.k);
2023     translateTo(point, translate0);
2024     zoomed(dispatch);
2025   }
2026
2027   function mousewheelreset() {
2028     translate0 = null;
2029   }
2030
2031   function dblclicked() {
2032     var dispatch = event.of(this, arguments),
2033         p = d3.mouse(this),
2034         l = location(p),
2035         k = Math.log(view.k) / Math.LN2;
2036     zoomstarted(dispatch);
2037     scaleTo(Math.pow(2, d3.event.shiftKey ? Math.ceil(k) - 1 : Math.floor(k) + 1));
2038     translateTo(p, l);
2039     zoomed(dispatch);
2040     zoomended(dispatch);
2041   }
2042
2043   return d3.rebind(zoom, event, "on");
2044 };
2045
2046 var d3_behavior_zoomInfinity = [0, Infinity]; // default scale extent
2047
2048 // https://developer.mozilla.org/en-US/docs/Mozilla_event_reference/wheel
2049 var d3_behavior_zoomDelta, d3_behavior_zoomWheel
2050     = "onwheel" in d3_document ? (d3_behavior_zoomDelta = function() { return -d3.event.deltaY * (d3.event.deltaMode ? 120 : 1); }, "wheel")
2051     : "onmousewheel" in d3_document ? (d3_behavior_zoomDelta = function() { return d3.event.wheelDelta; }, "mousewheel")
2052     : (d3_behavior_zoomDelta = function() { return -d3.event.detail; }, "MozMousePixelScroll");
2053 function d3_functor(v) {
2054   return typeof v === "function" ? v : function() { return v; };
2055 }
2056
2057 d3.functor = d3_functor;
2058
2059 d3.touch = function(container, touches, identifier) {
2060   if (arguments.length < 3) identifier = touches, touches = d3_eventSource().changedTouches;
2061   if (touches) for (var i = 0, n = touches.length, touch; i < n; ++i) {
2062     if ((touch = touches[i]).identifier === identifier) {
2063       return d3_mousePoint(container, touch);
2064     }
2065   }
2066 };
2067
2068 var d3_timer_queueHead,
2069     d3_timer_queueTail,
2070     d3_timer_interval, // is an interval (or frame) active?
2071     d3_timer_timeout, // is a timeout active?
2072     d3_timer_active, // active timer object
2073     d3_timer_frame = d3_window[d3_vendorSymbol(d3_window, "requestAnimationFrame")] || function(callback) { setTimeout(callback, 17); };
2074
2075 // The timer will continue to fire until callback returns true.
2076 d3.timer = function(callback, delay, then) {
2077   var n = arguments.length;
2078   if (n < 2) delay = 0;
2079   if (n < 3) then = Date.now();
2080
2081   // Add the callback to the tail of the queue.
2082   var time = then + delay, timer = {c: callback, t: time, f: false, n: null};
2083   if (d3_timer_queueTail) d3_timer_queueTail.n = timer;
2084   else d3_timer_queueHead = timer;
2085   d3_timer_queueTail = timer;
2086
2087   // Start animatin'!
2088   if (!d3_timer_interval) {
2089     d3_timer_timeout = clearTimeout(d3_timer_timeout);
2090     d3_timer_interval = 1;
2091     d3_timer_frame(d3_timer_step);
2092   }
2093 };
2094
2095 function d3_timer_step() {
2096   var now = d3_timer_mark(),
2097       delay = d3_timer_sweep() - now;
2098   if (delay > 24) {
2099     if (isFinite(delay)) {
2100       clearTimeout(d3_timer_timeout);
2101       d3_timer_timeout = setTimeout(d3_timer_step, delay);
2102     }
2103     d3_timer_interval = 0;
2104   } else {
2105     d3_timer_interval = 1;
2106     d3_timer_frame(d3_timer_step);
2107   }
2108 }
2109
2110 d3.timer.flush = function() {
2111   d3_timer_mark();
2112   d3_timer_sweep();
2113 };
2114
2115 function d3_timer_mark() {
2116   var now = Date.now();
2117   d3_timer_active = d3_timer_queueHead;
2118   while (d3_timer_active) {
2119     if (now >= d3_timer_active.t) d3_timer_active.f = d3_timer_active.c(now - d3_timer_active.t);
2120     d3_timer_active = d3_timer_active.n;
2121   }
2122   return now;
2123 }
2124
2125 // Flush after callbacks to avoid concurrent queue modification.
2126 // Returns the time of the earliest active timer, post-sweep.
2127 function d3_timer_sweep() {
2128   var t0,
2129       t1 = d3_timer_queueHead,
2130       time = Infinity;
2131   while (t1) {
2132     if (t1.f) {
2133       t1 = t0 ? t0.n = t1.n : d3_timer_queueHead = t1.n;
2134     } else {
2135       if (t1.t < time) time = t1.t;
2136       t1 = (t0 = t1).n;
2137     }
2138   }
2139   d3_timer_queueTail = t0;
2140   return time;
2141 }
2142 d3.geo = {};
2143 function d3_identity(d) {
2144   return d;
2145 }
2146 function d3_true() {
2147   return true;
2148 }
2149
2150 function d3_geo_spherical(cartesian) {
2151   return [
2152     Math.atan2(cartesian[1], cartesian[0]),
2153     d3_asin(cartesian[2])
2154   ];
2155 }
2156
2157 function d3_geo_sphericalEqual(a, b) {
2158   return abs(a[0] - b[0]) < ε && abs(a[1] - b[1]) < ε;
2159 }
2160
2161 // General spherical polygon clipping algorithm: takes a polygon, cuts it into
2162 // visible line segments and rejoins the segments by interpolating along the
2163 // clip edge.
2164 function d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener) {
2165   var subject = [],
2166       clip = [];
2167
2168   segments.forEach(function(segment) {
2169     if ((n = segment.length - 1) <= 0) return;
2170     var n, p0 = segment[0], p1 = segment[n];
2171
2172     // If the first and last points of a segment are coincident, then treat as
2173     // a closed ring.
2174     // TODO if all rings are closed, then the winding order of the exterior
2175     // ring should be checked.
2176     if (d3_geo_sphericalEqual(p0, p1)) {
2177       listener.lineStart();
2178       for (var i = 0; i < n; ++i) listener.point((p0 = segment[i])[0], p0[1]);
2179       listener.lineEnd();
2180       return;
2181     }
2182
2183     var a = new d3_geo_clipPolygonIntersection(p0, segment, null, true),
2184         b = new d3_geo_clipPolygonIntersection(p0, null, a, false);
2185     a.o = b;
2186     subject.push(a);
2187     clip.push(b);
2188     a = new d3_geo_clipPolygonIntersection(p1, segment, null, false);
2189     b = new d3_geo_clipPolygonIntersection(p1, null, a, true);
2190     a.o = b;
2191     subject.push(a);
2192     clip.push(b);
2193   });
2194   clip.sort(compare);
2195   d3_geo_clipPolygonLinkCircular(subject);
2196   d3_geo_clipPolygonLinkCircular(clip);
2197   if (!subject.length) return;
2198
2199   for (var i = 0, entry = clipStartInside, n = clip.length; i < n; ++i) {
2200     clip[i].e = entry = !entry;
2201   }
2202
2203   var start = subject[0],
2204       points,
2205       point;
2206   while (1) {
2207     // Find first unvisited intersection.
2208     var current = start,
2209         isSubject = true;
2210     while (current.v) if ((current = current.n) === start) return;
2211     points = current.z;
2212     listener.lineStart();
2213     do {
2214       current.v = current.o.v = true;
2215       if (current.e) {
2216         if (isSubject) {
2217           for (var i = 0, n = points.length; i < n; ++i) listener.point((point = points[i])[0], point[1]);
2218         } else {
2219           interpolate(current.x, current.n.x, 1, listener);
2220         }
2221         current = current.n;
2222       } else {
2223         if (isSubject) {
2224           points = current.p.z;
2225           for (var i = points.length - 1; i >= 0; --i) listener.point((point = points[i])[0], point[1]);
2226         } else {
2227           interpolate(current.x, current.p.x, -1, listener);
2228         }
2229         current = current.p;
2230       }
2231       current = current.o;
2232       points = current.z;
2233       isSubject = !isSubject;
2234     } while (!current.v);
2235     listener.lineEnd();
2236   }
2237 }
2238
2239 function d3_geo_clipPolygonLinkCircular(array) {
2240   if (!(n = array.length)) return;
2241   var n,
2242       i = 0,
2243       a = array[0],
2244       b;
2245   while (++i < n) {
2246     a.n = b = array[i];
2247     b.p = a;
2248     a = b;
2249   }
2250   a.n = b = array[0];
2251   b.p = a;
2252 }
2253
2254 function d3_geo_clipPolygonIntersection(point, points, other, entry) {
2255   this.x = point;
2256   this.z = points;
2257   this.o = other; // another intersection
2258   this.e = entry; // is an entry?
2259   this.v = false; // visited
2260   this.n = this.p = null; // next & previous
2261 }
2262
2263 function d3_geo_clip(pointVisible, clipLine, interpolate, clipStart) {
2264   return function(rotate, listener) {
2265     var line = clipLine(listener),
2266         rotatedClipStart = rotate.invert(clipStart[0], clipStart[1]);
2267
2268     var clip = {
2269       point: point,
2270       lineStart: lineStart,
2271       lineEnd: lineEnd,
2272       polygonStart: function() {
2273         clip.point = pointRing;
2274         clip.lineStart = ringStart;
2275         clip.lineEnd = ringEnd;
2276         segments = [];
2277         polygon = [];
2278       },
2279       polygonEnd: function() {
2280         clip.point = point;
2281         clip.lineStart = lineStart;
2282         clip.lineEnd = lineEnd;
2283
2284         segments = d3.merge(segments);
2285         var clipStartInside = d3_geo_pointInPolygon(rotatedClipStart, polygon);
2286         if (segments.length) {
2287           if (!polygonStarted) listener.polygonStart(), polygonStarted = true;
2288           d3_geo_clipPolygon(segments, d3_geo_clipSort, clipStartInside, interpolate, listener);
2289         } else if (clipStartInside) {
2290           if (!polygonStarted) listener.polygonStart(), polygonStarted = true;
2291           listener.lineStart();
2292           interpolate(null, null, 1, listener);
2293           listener.lineEnd();
2294         }
2295         if (polygonStarted) listener.polygonEnd(), polygonStarted = false;
2296         segments = polygon = null;
2297       },
2298       sphere: function() {
2299         listener.polygonStart();
2300         listener.lineStart();
2301         interpolate(null, null, 1, listener);
2302         listener.lineEnd();
2303         listener.polygonEnd();
2304       }
2305     };
2306
2307     function point(λ, φ) {
2308       var point = rotate(λ, φ);
2309       if (pointVisible(λ = point[0], φ = point[1])) listener.point(λ, φ);
2310     }
2311     function pointLine(λ, φ) {
2312       var point = rotate(λ, φ);
2313       line.point(point[0], point[1]);
2314     }
2315     function lineStart() { clip.point = pointLine; line.lineStart(); }
2316     function lineEnd() { clip.point = point; line.lineEnd(); }
2317
2318     var segments;
2319
2320     var buffer = d3_geo_clipBufferListener(),
2321         ringListener = clipLine(buffer),
2322         polygonStarted = false,
2323         polygon,
2324         ring;
2325
2326     function pointRing(λ, φ) {
2327       ring.push([λ, φ]);
2328       var point = rotate(λ, φ);
2329       ringListener.point(point[0], point[1]);
2330     }
2331
2332     function ringStart() {
2333       ringListener.lineStart();
2334       ring = [];
2335     }
2336
2337     function ringEnd() {
2338       pointRing(ring[0][0], ring[0][1]);
2339       ringListener.lineEnd();
2340
2341       var clean = ringListener.clean(),
2342           ringSegments = buffer.buffer(),
2343           segment,
2344           n = ringSegments.length;
2345
2346       ring.pop();
2347       polygon.push(ring);
2348       ring = null;
2349
2350       if (!n) return;
2351
2352       // No intersections.
2353       if (clean & 1) {
2354         segment = ringSegments[0];
2355         var n = segment.length - 1,
2356             i = -1,
2357             point;
2358         if (n > 0) {
2359           if (!polygonStarted) listener.polygonStart(), polygonStarted = true;
2360           listener.lineStart();
2361           while (++i < n) listener.point((point = segment[i])[0], point[1]);
2362           listener.lineEnd();
2363         }
2364         return;
2365       }
2366
2367       // Rejoin connected segments.
2368       // TODO reuse bufferListener.rejoin()?
2369       if (n > 1 && clean & 2) ringSegments.push(ringSegments.pop().concat(ringSegments.shift()));
2370
2371       segments.push(ringSegments.filter(d3_geo_clipSegmentLength1));
2372     }
2373
2374     return clip;
2375   };
2376 }
2377
2378 function d3_geo_clipSegmentLength1(segment) {
2379   return segment.length > 1;
2380 }
2381
2382 function d3_geo_clipBufferListener() {
2383   var lines = [],
2384       line;
2385   return {
2386     lineStart: function() { lines.push(line = []); },
2387     point: function(λ, φ) { line.push([λ, φ]); },
2388     lineEnd: d3_noop,
2389     buffer: function() {
2390       var buffer = lines;
2391       lines = [];
2392       line = null;
2393       return buffer;
2394     },
2395     rejoin: function() {
2396       if (lines.length > 1) lines.push(lines.pop().concat(lines.shift()));
2397     }
2398   };
2399 }
2400
2401 // Intersection points are sorted along the clip edge. For both antimeridian
2402 // cutting and circle clipping, the same comparison is used.
2403 function d3_geo_clipSort(a, b) {
2404   return ((a = a.x)[0] < 0 ? a[1] - halfπ - ε : halfπ - a[1])
2405        - ((b = b.x)[0] < 0 ? b[1] - halfπ - ε : halfπ - b[1]);
2406 }
2407 // Adds floating point numbers with twice the normal precision.
2408 // Reference: J. R. Shewchuk, Adaptive Precision Floating-Point Arithmetic and
2409 // Fast Robust Geometric Predicates, Discrete & Computational Geometry 18(3)
2410 // 305–363 (1997).
2411 // Code adapted from GeographicLib by Charles F. F. Karney,
2412 // http://geographiclib.sourceforge.net/
2413 // See lib/geographiclib/LICENSE for details.
2414
2415 function d3_adder() {}
2416
2417 d3_adder.prototype = {
2418   s: 0, // rounded value
2419   t: 0, // exact error
2420   add: function(y) {
2421     d3_adderSum(y, this.t, d3_adderTemp);
2422     d3_adderSum(d3_adderTemp.s, this.s, this);
2423     if (this.s) this.t += d3_adderTemp.t;
2424     else this.s = d3_adderTemp.t;
2425   },
2426   reset: function() {
2427     this.s = this.t = 0;
2428   },
2429   valueOf: function() {
2430     return this.s;
2431   }
2432 };
2433
2434 var d3_adderTemp = new d3_adder;
2435
2436 function d3_adderSum(a, b, o) {
2437   var x = o.s = a + b, // a + b
2438       bv = x - a, av = x - bv; // b_virtual & a_virtual
2439   o.t = (a - av) + (b - bv); // a_roundoff + b_roundoff
2440 }
2441
2442 d3.geo.stream = function(object, listener) {
2443   if (object && d3_geo_streamObjectType.hasOwnProperty(object.type)) {
2444     d3_geo_streamObjectType[object.type](object, listener);
2445   } else {
2446     d3_geo_streamGeometry(object, listener);
2447   }
2448 };
2449
2450 function d3_geo_streamGeometry(geometry, listener) {
2451   if (geometry && d3_geo_streamGeometryType.hasOwnProperty(geometry.type)) {
2452     d3_geo_streamGeometryType[geometry.type](geometry, listener);
2453   }
2454 }
2455
2456 var d3_geo_streamObjectType = {
2457   Feature: function(feature, listener) {
2458     d3_geo_streamGeometry(feature.geometry, listener);
2459   },
2460   FeatureCollection: function(object, listener) {
2461     var features = object.features, i = -1, n = features.length;
2462     while (++i < n) d3_geo_streamGeometry(features[i].geometry, listener);
2463   }
2464 };
2465
2466 var d3_geo_streamGeometryType = {
2467   Sphere: function(object, listener) {
2468     listener.sphere();
2469   },
2470   Point: function(object, listener) {
2471     object = object.coordinates;
2472     listener.point(object[0], object[1], object[2]);
2473   },
2474   MultiPoint: function(object, listener) {
2475     var coordinates = object.coordinates, i = -1, n = coordinates.length;
2476     while (++i < n) object = coordinates[i], listener.point(object[0], object[1], object[2]);
2477   },
2478   LineString: function(object, listener) {
2479     d3_geo_streamLine(object.coordinates, listener, 0);
2480   },
2481   MultiLineString: function(object, listener) {
2482     var coordinates = object.coordinates, i = -1, n = coordinates.length;
2483     while (++i < n) d3_geo_streamLine(coordinates[i], listener, 0);
2484   },
2485   Polygon: function(object, listener) {
2486     d3_geo_streamPolygon(object.coordinates, listener);
2487   },
2488   MultiPolygon: function(object, listener) {
2489     var coordinates = object.coordinates, i = -1, n = coordinates.length;
2490     while (++i < n) d3_geo_streamPolygon(coordinates[i], listener);
2491   },
2492   GeometryCollection: function(object, listener) {
2493     var geometries = object.geometries, i = -1, n = geometries.length;
2494     while (++i < n) d3_geo_streamGeometry(geometries[i], listener);
2495   }
2496 };
2497
2498 function d3_geo_streamLine(coordinates, listener, closed) {
2499   var i = -1, n = coordinates.length - closed, coordinate;
2500   listener.lineStart();
2501   while (++i < n) coordinate = coordinates[i], listener.point(coordinate[0], coordinate[1], coordinate[2]);
2502   listener.lineEnd();
2503 }
2504
2505 function d3_geo_streamPolygon(coordinates, listener) {
2506   var i = -1, n = coordinates.length;
2507   listener.polygonStart();
2508   while (++i < n) d3_geo_streamLine(coordinates[i], listener, 1);
2509   listener.polygonEnd();
2510 }
2511
2512 d3.geo.area = function(object) {
2513   d3_geo_areaSum = 0;
2514   d3.geo.stream(object, d3_geo_area);
2515   return d3_geo_areaSum;
2516 };
2517
2518 var d3_geo_areaSum,
2519     d3_geo_areaRingSum = new d3_adder;
2520
2521 var d3_geo_area = {
2522   sphere: function() { d3_geo_areaSum += 4 * π; },
2523   point: d3_noop,
2524   lineStart: d3_noop,
2525   lineEnd: d3_noop,
2526
2527   // Only count area for polygon rings.
2528   polygonStart: function() {
2529     d3_geo_areaRingSum.reset();
2530     d3_geo_area.lineStart = d3_geo_areaRingStart;
2531   },
2532   polygonEnd: function() {
2533     var area = 2 * d3_geo_areaRingSum;
2534     d3_geo_areaSum += area < 0 ? 4 * π + area : area;
2535     d3_geo_area.lineStart = d3_geo_area.lineEnd = d3_geo_area.point = d3_noop;
2536   }
2537 };
2538
2539 function d3_geo_areaRingStart() {
2540   var λ00, φ00, λ0, cosφ0, sinφ0; // start point and previous point
2541
2542   // For the first point, …
2543   d3_geo_area.point = function(λ, φ) {
2544     d3_geo_area.point = nextPoint;
2545     λ0 = (λ00 = λ) * d3_radians, cosφ0 = Math.cos(φ = (φ00 = φ) * d3_radians / 2 + π / 4), sinφ0 = Math.sin(φ);
2546   };
2547
2548   // For subsequent points, …
2549   function nextPoint(λ, φ) {
2550     λ *= d3_radians;
2551     φ = φ * d3_radians / 2 + π / 4; // half the angular distance from south pole
2552
2553     // Spherical excess E for a spherical triangle with vertices: south pole,
2554     // previous point, current point.  Uses a formula derived from Cagnoli’s
2555     // theorem.  See Todhunter, Spherical Trig. (1871), Sec. 103, Eq. (2).
2556     var dλ = λ - λ0,
2557         sdλ = dλ >= 0 ? 1 : -1,
2558         adλ = sdλ * dλ,
2559         cosφ = Math.cos(φ),
2560         sinφ = Math.sin(φ),
2561         k = sinφ0 * sinφ,
2562         u = cosφ0 * cosφ + k * Math.cos(adλ),
2563         v = k * sdλ * Math.sin(adλ);
2564     d3_geo_areaRingSum.add(Math.atan2(v, u));
2565
2566     // Advance the previous points.
2567     λ0 = λ, cosφ0 = cosφ, sinφ0 = sinφ;
2568   }
2569
2570   // For the last point, return to the start.
2571   d3_geo_area.lineEnd = function() {
2572     nextPoint(λ00, φ00);
2573   };
2574 }
2575 // TODO
2576 // cross and scale return new vectors,
2577 // whereas add and normalize operate in-place
2578
2579 function d3_geo_cartesian(spherical) {
2580   var λ = spherical[0],
2581       φ = spherical[1],
2582       cosφ = Math.cos(φ);
2583   return [
2584     cosφ * Math.cos(λ),
2585     cosφ * Math.sin(λ),
2586     Math.sin(φ)
2587   ];
2588 }
2589
2590 function d3_geo_cartesianDot(a, b) {
2591   return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
2592 }
2593
2594 function d3_geo_cartesianCross(a, b) {
2595   return [
2596     a[1] * b[2] - a[2] * b[1],
2597     a[2] * b[0] - a[0] * b[2],
2598     a[0] * b[1] - a[1] * b[0]
2599   ];
2600 }
2601
2602 function d3_geo_cartesianAdd(a, b) {
2603   a[0] += b[0];
2604   a[1] += b[1];
2605   a[2] += b[2];
2606 }
2607
2608 function d3_geo_cartesianScale(vector, k) {
2609   return [
2610     vector[0] * k,
2611     vector[1] * k,
2612     vector[2] * k
2613   ];
2614 }
2615
2616 function d3_geo_cartesianNormalize(d) {
2617   var l = Math.sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2]);
2618   d[0] /= l;
2619   d[1] /= l;
2620   d[2] /= l;
2621 }
2622
2623 function d3_geo_pointInPolygon(point, polygon) {
2624   var meridian = point[0],
2625       parallel = point[1],
2626       meridianNormal = [Math.sin(meridian), -Math.cos(meridian), 0],
2627       polarAngle = 0,
2628       winding = 0;
2629   d3_geo_areaRingSum.reset();
2630
2631   for (var i = 0, n = polygon.length; i < n; ++i) {
2632     var ring = polygon[i],
2633         m = ring.length;
2634     if (!m) continue;
2635     var point0 = ring[0],
2636         λ0 = point0[0],
2637         φ0 = point0[1] / 2 + π / 4,
2638         sinφ0 = Math.sin(φ0),
2639         cosφ0 = Math.cos(φ0),
2640         j = 1;
2641
2642     while (true) {
2643       if (j === m) j = 0;
2644       point = ring[j];
2645       var λ = point[0],
2646           φ = point[1] / 2 + π / 4,
2647           sinφ = Math.sin(φ),
2648           cosφ = Math.cos(φ),
2649           dλ = λ - λ0,
2650           sdλ = dλ >= 0 ? 1 : -1,
2651           adλ = sdλ * dλ,
2652           antimeridian = adλ > π,
2653           k = sinφ0 * sinφ;
2654       d3_geo_areaRingSum.add(Math.atan2(k * sdλ * Math.sin(adλ), cosφ0 * cosφ + k * Math.cos(adλ)));
2655
2656       polarAngle += antimeridian ? dλ + sdλ * τ : dλ;
2657
2658       // Are the longitudes either side of the point's meridian, and are the
2659       // latitudes smaller than the parallel?
2660       if (antimeridian ^ λ0 >= meridian ^ λ >= meridian) {
2661         var arc = d3_geo_cartesianCross(d3_geo_cartesian(point0), d3_geo_cartesian(point));
2662         d3_geo_cartesianNormalize(arc);
2663         var intersection = d3_geo_cartesianCross(meridianNormal, arc);
2664         d3_geo_cartesianNormalize(intersection);
2665         var φarc = (antimeridian ^ dλ >= 0 ? -1 : 1) * d3_asin(intersection[2]);
2666         if (parallel > φarc || parallel === φarc && (arc[0] || arc[1])) {
2667           winding += antimeridian ^ dλ >= 0 ? 1 : -1;
2668         }
2669       }
2670       if (!j++) break;
2671       λ0 = λ, sinφ0 = sinφ, cosφ0 = cosφ, point0 = point;
2672     }
2673   }
2674
2675   // First, determine whether the South pole is inside or outside:
2676   //
2677   // It is inside if:
2678   // * the polygon winds around it in a clockwise direction.
2679   // * the polygon does not (cumulatively) wind around it, but has a negative
2680   //   (counter-clockwise) area.
2681   //
2682   // Second, count the (signed) number of times a segment crosses a meridian
2683   // from the point to the South pole.  If it is zero, then the point is the
2684   // same side as the South pole.
2685
2686   return (polarAngle < -ε || polarAngle < ε && d3_geo_areaRingSum < 0) ^ (winding & 1);
2687 }
2688
2689 var d3_geo_clipAntimeridian = d3_geo_clip(
2690     d3_true,
2691     d3_geo_clipAntimeridianLine,
2692     d3_geo_clipAntimeridianInterpolate,
2693     [-π, -π / 2]);
2694
2695 // Takes a line and cuts into visible segments. Return values:
2696 //   0: there were intersections or the line was empty.
2697 //   1: no intersections.
2698 //   2: there were intersections, and the first and last segments should be
2699 //      rejoined.
2700 function d3_geo_clipAntimeridianLine(listener) {
2701   var λ0 = NaN,
2702       φ0 = NaN,
2703       sλ0 = NaN,
2704       clean; // no intersections
2705
2706   return {
2707     lineStart: function() {
2708       listener.lineStart();
2709       clean = 1;
2710     },
2711     point: function(λ1, φ1) {
2712       var sλ1 = λ1 > 0 ? π : -π,
2713           dλ = abs(λ1 - λ0);
2714       if (abs(dλ - π) < ε) { // line crosses a pole
2715         listener.point(λ0, φ0 = (φ0 + φ1) / 2 > 0 ? halfπ : -halfπ);
2716         listener.point(sλ0, φ0);
2717         listener.lineEnd();
2718         listener.lineStart();
2719         listener.point(sλ1, φ0);
2720         listener.point(λ1, φ0);
2721         clean = 0;
2722       } else if (sλ0 !== sλ1 && dλ >= π) { // line crosses antimeridian
2723         // handle degeneracies
2724         if (abs(λ0 - sλ0) < ε) λ0 -= sλ0 * ε;
2725         if (abs(λ1 - sλ1) < ε) λ1 -= sλ1 * ε;
2726         φ0 = d3_geo_clipAntimeridianIntersect(λ0, φ0, λ1, φ1);
2727         listener.point(sλ0, φ0);
2728         listener.lineEnd();
2729         listener.lineStart();
2730         listener.point(sλ1, φ0);
2731         clean = 0;
2732       }
2733       listener.point(λ0 = λ1, φ0 = φ1);
2734       sλ0 = sλ1;
2735     },
2736     lineEnd: function() {
2737       listener.lineEnd();
2738       λ0 = φ0 = NaN;
2739     },
2740     // if there are intersections, we always rejoin the first and last segments.
2741     clean: function() { return 2 - clean; }
2742   };
2743 }
2744
2745 function d3_geo_clipAntimeridianIntersect(λ0, φ0, λ1, φ1) {
2746   var cosφ0,
2747       cosφ1,
2748       sinλ0_λ1 = Math.sin(λ0 - λ1);
2749   return abs(sinλ0_λ1) > ε
2750       ? Math.atan((Math.sin(φ0) * (cosφ1 = Math.cos(φ1)) * Math.sin(λ1)
2751                  - Math.sin(φ1) * (cosφ0 = Math.cos(φ0)) * Math.sin(λ0))
2752                  / (cosφ0 * cosφ1 * sinλ0_λ1))
2753       : (φ0 + φ1) / 2;
2754 }
2755
2756 function d3_geo_clipAntimeridianInterpolate(from, to, direction, listener) {
2757   var φ;
2758   if (from == null) {
2759     φ = direction * halfπ;
2760     listener.point(-π,  φ);
2761     listener.point( 0,  φ);
2762     listener.point( π,  φ);
2763     listener.point( π,  0);
2764     listener.point( π, -φ);
2765     listener.point( 0, -φ);
2766     listener.point(-π, -φ);
2767     listener.point(-π,  0);
2768     listener.point(-π,  φ);
2769   } else if (abs(from[0] - to[0]) > ε) {
2770     var s = from[0] < to[0] ? π : -π;
2771     φ = direction * s / 2;
2772     listener.point(-s, φ);
2773     listener.point( 0, φ);
2774     listener.point( s, φ);
2775   } else {
2776     listener.point(to[0], to[1]);
2777   }
2778 }
2779
2780 function d3_geo_equirectangular(λ, φ) {
2781   return [λ, φ];
2782 }
2783
2784 (d3.geo.equirectangular = function() {
2785   return d3_geo_projection(d3_geo_equirectangular);
2786 }).raw = d3_geo_equirectangular.invert = d3_geo_equirectangular;
2787
2788 d3.geo.rotation = function(rotate) {
2789   rotate = d3_geo_rotation(rotate[0] % 360 * d3_radians, rotate[1] * d3_radians, rotate.length > 2 ? rotate[2] * d3_radians : 0);
2790
2791   function forward(coordinates) {
2792     coordinates = rotate(coordinates[0] * d3_radians, coordinates[1] * d3_radians);
2793     return coordinates[0] *= d3_degrees, coordinates[1] *= d3_degrees, coordinates;
2794   }
2795
2796   forward.invert = function(coordinates) {
2797     coordinates = rotate.invert(coordinates[0] * d3_radians, coordinates[1] * d3_radians);
2798     return coordinates[0] *= d3_degrees, coordinates[1] *= d3_degrees, coordinates;
2799   };
2800
2801   return forward;
2802 };
2803
2804 function d3_geo_identityRotation(λ, φ) {
2805   return [λ > π ? λ - τ : λ < -π ? λ + τ : λ, φ];
2806 }
2807
2808 d3_geo_identityRotation.invert = d3_geo_equirectangular;
2809
2810 // Note: |δλ| must be < 2π
2811 function d3_geo_rotation(δλ, δφ, δγ) {
2812   return δλ ? (δφ || δγ ? d3_geo_compose(d3_geo_rotationλ(δλ), d3_geo_rotationφγ(δφ, δγ))
2813     : d3_geo_rotationλ(δλ))
2814     : (δφ || δγ ? d3_geo_rotationφγ(δφ, δγ)
2815     : d3_geo_identityRotation);
2816 }
2817
2818 function d3_geo_forwardRotationλ(δλ) {
2819   return function(λ, φ) {
2820     return λ += δλ, [λ > π ? λ - τ : λ < -π ? λ + τ : λ, φ];
2821   };
2822 }
2823
2824 function d3_geo_rotationλ(δλ) {
2825   var rotation = d3_geo_forwardRotationλ(δλ);
2826   rotation.invert = d3_geo_forwardRotationλ(-δλ);
2827   return rotation;
2828 }
2829
2830 function d3_geo_rotationφγ(δφ, δγ) {
2831   var cosδφ = Math.cos(δφ),
2832       sinδφ = Math.sin(δφ),
2833       cosδγ = Math.cos(δγ),
2834       sinδγ = Math.sin(δγ);
2835
2836   function rotation(λ, φ) {
2837     var cosφ = Math.cos(φ),
2838         x = Math.cos(λ) * cosφ,
2839         y = Math.sin(λ) * cosφ,
2840         z = Math.sin(φ),
2841         k = z * cosδφ + x * sinδφ;
2842     return [
2843       Math.atan2(y * cosδγ - k * sinδγ, x * cosδφ - z * sinδφ),
2844       d3_asin(k * cosδγ + y * sinδγ)
2845     ];
2846   }
2847
2848   rotation.invert = function(λ, φ) {
2849     var cosφ = Math.cos(φ),
2850         x = Math.cos(λ) * cosφ,
2851         y = Math.sin(λ) * cosφ,
2852         z = Math.sin(φ),
2853         k = z * cosδγ - y * sinδγ;
2854     return [
2855       Math.atan2(y * cosδγ + z * sinδγ, x * cosδφ + k * sinδφ),
2856       d3_asin(k * cosδφ - x * sinδφ)
2857     ];
2858   };
2859
2860   return rotation;
2861 }
2862
2863 d3.geo.circle = function() {
2864   var origin = [0, 0],
2865       angle,
2866       precision = 6,
2867       interpolate;
2868
2869   function circle() {
2870     var center = typeof origin === "function" ? origin.apply(this, arguments) : origin,
2871         rotate = d3_geo_rotation(-center[0] * d3_radians, -center[1] * d3_radians, 0).invert,
2872         ring = [];
2873
2874     interpolate(null, null, 1, {
2875       point: function(x, y) {
2876         ring.push(x = rotate(x, y));
2877         x[0] *= d3_degrees, x[1] *= d3_degrees;
2878       }
2879     });
2880
2881     return {type: "Polygon", coordinates: [ring]};
2882   }
2883
2884   circle.origin = function(x) {
2885     if (!arguments.length) return origin;
2886     origin = x;
2887     return circle;
2888   };
2889
2890   circle.angle = function(x) {
2891     if (!arguments.length) return angle;
2892     interpolate = d3_geo_circleInterpolate((angle = +x) * d3_radians, precision * d3_radians);
2893     return circle;
2894   };
2895
2896   circle.precision = function(_) {
2897     if (!arguments.length) return precision;
2898     interpolate = d3_geo_circleInterpolate(angle * d3_radians, (precision = +_) * d3_radians);
2899     return circle;
2900   };
2901
2902   return circle.angle(90);
2903 };
2904
2905 // Interpolates along a circle centered at [0°, 0°], with a given radius and
2906 // precision.
2907 function d3_geo_circleInterpolate(radius, precision) {
2908   var cr = Math.cos(radius),
2909       sr = Math.sin(radius);
2910   return function(from, to, direction, listener) {
2911     var step = direction * precision;
2912     if (from != null) {
2913       from = d3_geo_circleAngle(cr, from);
2914       to = d3_geo_circleAngle(cr, to);
2915       if (direction > 0 ? from < to: from > to) from += direction * τ;
2916     } else {
2917       from = radius + direction * τ;
2918       to = radius - .5 * step;
2919     }
2920     for (var point, t = from; direction > 0 ? t > to : t < to; t -= step) {
2921       listener.point((point = d3_geo_spherical([
2922         cr,
2923         -sr * Math.cos(t),
2924         -sr * Math.sin(t)
2925       ]))[0], point[1]);
2926     }
2927   };
2928 }
2929
2930 // Signed angle of a cartesian point relative to [cr, 0, 0].
2931 function d3_geo_circleAngle(cr, point) {
2932   var a = d3_geo_cartesian(point);
2933   a[0] -= cr;
2934   d3_geo_cartesianNormalize(a);
2935   var angle = d3_acos(-a[1]);
2936   return ((-a[2] < 0 ? -angle : angle) + 2 * Math.PI - ε) % (2 * Math.PI);
2937 }
2938
2939 // Clip features against a small circle centered at [0°, 0°].
2940 function d3_geo_clipCircle(radius) {
2941   var cr = Math.cos(radius),
2942       smallRadius = cr > 0,
2943       notHemisphere = abs(cr) > ε, // TODO optimise for this common case
2944       interpolate = d3_geo_circleInterpolate(radius, 6 * d3_radians);
2945
2946   return d3_geo_clip(visible, clipLine, interpolate, smallRadius ? [0, -radius] : [-π, radius - π]);
2947
2948   function visible(λ, φ) {
2949     return Math.cos(λ) * Math.cos(φ) > cr;
2950   }
2951
2952   // Takes a line and cuts into visible segments. Return values used for
2953   // polygon clipping:
2954   //   0: there were intersections or the line was empty.
2955   //   1: no intersections.
2956   //   2: there were intersections, and the first and last segments should be
2957   //      rejoined.
2958   function clipLine(listener) {
2959     var point0, // previous point
2960         c0, // code for previous point
2961         v0, // visibility of previous point
2962         v00, // visibility of first point
2963         clean; // no intersections
2964     return {
2965       lineStart: function() {
2966         v00 = v0 = false;
2967         clean = 1;
2968       },
2969       point: function(λ, φ) {
2970         var point1 = [λ, φ],
2971             point2,
2972             v = visible(λ, φ),
2973             c = smallRadius
2974               ? v ? 0 : code(λ, φ)
2975               : v ? code(λ + (λ < 0 ? π : -π), φ) : 0;
2976         if (!point0 && (v00 = v0 = v)) listener.lineStart();
2977         // Handle degeneracies.
2978         // TODO ignore if not clipping polygons.
2979         if (v !== v0) {
2980           point2 = intersect(point0, point1);
2981           if (d3_geo_sphericalEqual(point0, point2) || d3_geo_sphericalEqual(point1, point2)) {
2982             point1[0] += ε;
2983             point1[1] += ε;
2984             v = visible(point1[0], point1[1]);
2985           }
2986         }
2987         if (v !== v0) {
2988           clean = 0;
2989           if (v) {
2990             // outside going in
2991             listener.lineStart();
2992             point2 = intersect(point1, point0);
2993             listener.point(point2[0], point2[1]);
2994           } else {
2995             // inside going out
2996             point2 = intersect(point0, point1);
2997             listener.point(point2[0], point2[1]);
2998             listener.lineEnd();
2999           }
3000           point0 = point2;
3001         } else if (notHemisphere && point0 && smallRadius ^ v) {
3002           var t;
3003           // If the codes for two points are different, or are both zero,
3004           // and there this segment intersects with the small circle.
3005           if (!(c & c0) && (t = intersect(point1, point0, true))) {
3006             clean = 0;
3007             if (smallRadius) {
3008               listener.lineStart();
3009               listener.point(t[0][0], t[0][1]);
3010               listener.point(t[1][0], t[1][1]);
3011               listener.lineEnd();
3012             } else {
3013               listener.point(t[1][0], t[1][1]);
3014               listener.lineEnd();
3015               listener.lineStart();
3016               listener.point(t[0][0], t[0][1]);
3017             }
3018           }
3019         }
3020         if (v && (!point0 || !d3_geo_sphericalEqual(point0, point1))) {
3021           listener.point(point1[0], point1[1]);
3022         }
3023         point0 = point1, v0 = v, c0 = c;
3024       },
3025       lineEnd: function() {
3026         if (v0) listener.lineEnd();
3027         point0 = null;
3028       },
3029       // Rejoin first and last segments if there were intersections and the first
3030       // and last points were visible.
3031       clean: function() { return clean | ((v00 && v0) << 1); }
3032     };
3033   }
3034
3035   // Intersects the great circle between a and b with the clip circle.
3036   function intersect(a, b, two) {
3037     var pa = d3_geo_cartesian(a),
3038         pb = d3_geo_cartesian(b);
3039
3040     // We have two planes, n1.p = d1 and n2.p = d2.
3041     // Find intersection line p(t) = c1 n1 + c2 n2 + t (n1 ⨯ n2).
3042     var n1 = [1, 0, 0], // normal
3043         n2 = d3_geo_cartesianCross(pa, pb),
3044         n2n2 = d3_geo_cartesianDot(n2, n2),
3045         n1n2 = n2[0], // d3_geo_cartesianDot(n1, n2),
3046         determinant = n2n2 - n1n2 * n1n2;
3047
3048     // Two polar points.
3049     if (!determinant) return !two && a;
3050
3051     var c1 =  cr * n2n2 / determinant,
3052         c2 = -cr * n1n2 / determinant,
3053         n1xn2 = d3_geo_cartesianCross(n1, n2),
3054         A = d3_geo_cartesianScale(n1, c1),
3055         B = d3_geo_cartesianScale(n2, c2);
3056     d3_geo_cartesianAdd(A, B);
3057
3058     // Solve |p(t)|^2 = 1.
3059     var u = n1xn2,
3060         w = d3_geo_cartesianDot(A, u),
3061         uu = d3_geo_cartesianDot(u, u),
3062         t2 = w * w - uu * (d3_geo_cartesianDot(A, A) - 1);
3063
3064     if (t2 < 0) return;
3065
3066     var t = Math.sqrt(t2),
3067         q = d3_geo_cartesianScale(u, (-w - t) / uu);
3068     d3_geo_cartesianAdd(q, A);
3069     q = d3_geo_spherical(q);
3070     if (!two) return q;
3071
3072     // Two intersection points.
3073     var λ0 = a[0],
3074         λ1 = b[0],
3075         φ0 = a[1],
3076         φ1 = b[1],
3077         z;
3078     if (λ1 < λ0) z = λ0, λ0 = λ1, λ1 = z;
3079     var δλ = λ1 - λ0,
3080         polar = abs(δλ - π) < ε,
3081         meridian = polar || δλ < ε;
3082
3083     if (!polar && φ1 < φ0) z = φ0, φ0 = φ1, φ1 = z;
3084
3085     // Check that the first point is between a and b.
3086     if (meridian
3087         ? polar
3088           ? φ0 + φ1 > 0 ^ q[1] < (abs(q[0] - λ0) < ε ? φ0 : φ1)
3089           : φ0 <= q[1] && q[1] <= φ1
3090         : δλ > π ^ (λ0 <= q[0] && q[0] <= λ1)) {
3091       var q1 = d3_geo_cartesianScale(u, (-w + t) / uu);
3092       d3_geo_cartesianAdd(q1, A);
3093       return [q, d3_geo_spherical(q1)];
3094     }
3095   }
3096
3097   // Generates a 4-bit vector representing the location of a point relative to
3098   // the small circle's bounding box.
3099   function code(λ, φ) {
3100     var r = smallRadius ? radius : π - radius,
3101         code = 0;
3102     if (λ < -r) code |= 1; // left
3103     else if (λ > r) code |= 2; // right
3104     if (φ < -r) code |= 4; // below
3105     else if (φ > r) code |= 8; // above
3106     return code;
3107   }
3108 }
3109
3110 // Liang–Barsky line clipping.
3111 function d3_geom_clipLine(x0, y0, x1, y1) {
3112   return function(line) {
3113     var a = line.a,
3114         b = line.b,
3115         ax = a.x,
3116         ay = a.y,
3117         bx = b.x,
3118         by = b.y,
3119         t0 = 0,
3120         t1 = 1,
3121         dx = bx - ax,
3122         dy = by - ay,
3123         r;
3124
3125     r = x0 - ax;
3126     if (!dx && r > 0) return;
3127     r /= dx;
3128     if (dx < 0) {
3129       if (r < t0) return;
3130       if (r < t1) t1 = r;
3131     } else if (dx > 0) {
3132       if (r > t1) return;
3133       if (r > t0) t0 = r;
3134     }
3135
3136     r = x1 - ax;
3137     if (!dx && r < 0) return;
3138     r /= dx;
3139     if (dx < 0) {
3140       if (r > t1) return;
3141       if (r > t0) t0 = r;
3142     } else if (dx > 0) {
3143       if (r < t0) return;
3144       if (r < t1) t1 = r;
3145     }
3146
3147     r = y0 - ay;
3148     if (!dy && r > 0) return;
3149     r /= dy;
3150     if (dy < 0) {
3151       if (r < t0) return;
3152       if (r < t1) t1 = r;
3153     } else if (dy > 0) {
3154       if (r > t1) return;
3155       if (r > t0) t0 = r;
3156     }
3157
3158     r = y1 - ay;
3159     if (!dy && r < 0) return;
3160     r /= dy;
3161     if (dy < 0) {
3162       if (r > t1) return;
3163       if (r > t0) t0 = r;
3164     } else if (dy > 0) {
3165       if (r < t0) return;
3166       if (r < t1) t1 = r;
3167     }
3168
3169     if (t0 > 0) line.a = {x: ax + t0 * dx, y: ay + t0 * dy};
3170     if (t1 < 1) line.b = {x: ax + t1 * dx, y: ay + t1 * dy};
3171     return line;
3172   };
3173 }
3174
3175 var d3_geo_clipExtentMAX = 1e9;
3176
3177 d3.geo.clipExtent = function() {
3178   var x0, y0, x1, y1,
3179       stream,
3180       clip,
3181       clipExtent = {
3182         stream: function(output) {
3183           if (stream) stream.valid = false;
3184           stream = clip(output);
3185           stream.valid = true; // allow caching by d3.geo.path
3186           return stream;
3187         },
3188         extent: function(_) {
3189           if (!arguments.length) return [[x0, y0], [x1, y1]];
3190           clip = d3_geo_clipExtent(x0 = +_[0][0], y0 = +_[0][1], x1 = +_[1][0], y1 = +_[1][1]);
3191           if (stream) stream.valid = false, stream = null;
3192           return clipExtent;
3193         }
3194       };
3195   return clipExtent.extent([[0, 0], [960, 500]]);
3196 };
3197
3198 function d3_geo_clipExtent(x0, y0, x1, y1) {
3199   return function(listener) {
3200     var listener_ = listener,
3201         bufferListener = d3_geo_clipBufferListener(),
3202         clipLine = d3_geom_clipLine(x0, y0, x1, y1),
3203         segments,
3204         polygon,
3205         ring;
3206
3207     var clip = {
3208       point: point,
3209       lineStart: lineStart,
3210       lineEnd: lineEnd,
3211       polygonStart: function() {
3212         listener = bufferListener;
3213         segments = [];
3214         polygon = [];
3215         clean = true;
3216       },
3217       polygonEnd: function() {
3218         listener = listener_;
3219         segments = d3.merge(segments);
3220         var clipStartInside = insidePolygon([x0, y1]),
3221             inside = clean && clipStartInside,
3222             visible = segments.length;
3223         if (inside || visible) {
3224           listener.polygonStart();
3225           if (inside) {
3226             listener.lineStart();
3227             interpolate(null, null, 1, listener);
3228             listener.lineEnd();
3229           }
3230           if (visible) {
3231             d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener);
3232           }
3233           listener.polygonEnd();
3234         }
3235         segments = polygon = ring = null;
3236       }
3237     };
3238
3239     function insidePolygon(p) {
3240       var wn = 0, // the winding number counter
3241           n = polygon.length,
3242           y = p[1];
3243
3244       for (var i = 0; i < n; ++i) {
3245         for (var j = 1, v = polygon[i], m = v.length, a = v[0], b; j < m; ++j) {
3246           b = v[j];
3247           if (a[1] <= y) {
3248             if (b[1] >  y && d3_cross2d(a, b, p) > 0) ++wn;
3249           } else {
3250             if (b[1] <= y && d3_cross2d(a, b, p) < 0) --wn;
3251           }
3252           a = b;
3253         }
3254       }
3255       return wn !== 0;
3256     }
3257
3258     function interpolate(from, to, direction, listener) {
3259       var a = 0, a1 = 0;
3260       if (from == null ||
3261           (a = corner(from, direction)) !== (a1 = corner(to, direction)) ||
3262           comparePoints(from, to) < 0 ^ direction > 0) {
3263         do {
3264           listener.point(a === 0 || a === 3 ? x0 : x1, a > 1 ? y1 : y0);
3265         } while ((a = (a + direction + 4) % 4) !== a1);
3266       } else {
3267         listener.point(to[0], to[1]);
3268       }
3269     }
3270
3271     function pointVisible(x, y) {
3272       return x0 <= x && x <= x1 && y0 <= y && y <= y1;
3273     }
3274
3275     function point(x, y) {
3276       if (pointVisible(x, y)) listener.point(x, y);
3277     }
3278
3279     var x__, y__, v__, // first point
3280         x_, y_, v_, // previous point
3281         first,
3282         clean;
3283
3284     function lineStart() {
3285       clip.point = linePoint;
3286       if (polygon) polygon.push(ring = []);
3287       first = true;
3288       v_ = false;
3289       x_ = y_ = NaN;
3290     }
3291
3292     function lineEnd() {
3293       // TODO rather than special-case polygons, simply handle them separately.
3294       // Ideally, coincident intersection points should be jittered to avoid
3295       // clipping issues.
3296       if (segments) {
3297         linePoint(x__, y__);
3298         if (v__ && v_) bufferListener.rejoin();
3299         segments.push(bufferListener.buffer());
3300       }
3301       clip.point = point;
3302       if (v_) listener.lineEnd();
3303     }
3304
3305     function linePoint(x, y) {
3306       x = Math.max(-d3_geo_clipExtentMAX, Math.min(d3_geo_clipExtentMAX, x));
3307       y = Math.max(-d3_geo_clipExtentMAX, Math.min(d3_geo_clipExtentMAX, y));
3308       var v = pointVisible(x, y);
3309       if (polygon) ring.push([x, y]);
3310       if (first) {
3311         x__ = x, y__ = y, v__ = v;
3312         first = false;
3313         if (v) {
3314           listener.lineStart();
3315           listener.point(x, y);
3316         }
3317       } else {
3318         if (v && v_) listener.point(x, y);
3319         else {
3320           var l = {a: {x: x_, y: y_}, b: {x: x, y: y}};
3321           if (clipLine(l)) {
3322             if (!v_) {
3323               listener.lineStart();
3324               listener.point(l.a.x, l.a.y);
3325             }
3326             listener.point(l.b.x, l.b.y);
3327             if (!v) listener.lineEnd();
3328             clean = false;
3329           } else if (v) {
3330             listener.lineStart();
3331             listener.point(x, y);
3332             clean = false;
3333           }
3334         }
3335       }
3336       x_ = x, y_ = y, v_ = v;
3337     }
3338
3339     return clip;
3340   };
3341
3342   function corner(p, direction) {
3343     return abs(p[0] - x0) < ε ? direction > 0 ? 0 : 3
3344         : abs(p[0] - x1) < ε ? direction > 0 ? 2 : 1
3345         : abs(p[1] - y0) < ε ? direction > 0 ? 1 : 0
3346         : direction > 0 ? 3 : 2; // abs(p[1] - y1) < ε
3347   }
3348
3349   function compare(a, b) {
3350     return comparePoints(a.x, b.x);
3351   }
3352
3353   function comparePoints(a, b) {
3354     var ca = corner(a, 1),
3355         cb = corner(b, 1);
3356     return ca !== cb ? ca - cb
3357         : ca === 0 ? b[1] - a[1]
3358         : ca === 1 ? a[0] - b[0]
3359         : ca === 2 ? a[1] - b[1]
3360         : b[0] - a[0];
3361   }
3362 }
3363 function d3_geo_compose(a, b) {
3364
3365   function compose(x, y) {
3366     return x = a(x, y), b(x[0], x[1]);
3367   }
3368
3369   if (a.invert && b.invert) compose.invert = function(x, y) {
3370     return x = b.invert(x, y), x && a.invert(x[0], x[1]);
3371   };
3372
3373   return compose;
3374 }
3375
3376 function d3_geo_conic(projectAt) {
3377   var φ0 = 0,
3378       φ1 = π / 3,
3379       m = d3_geo_projectionMutator(projectAt),
3380       p = m(φ0, φ1);
3381
3382   p.parallels = function(_) {
3383     if (!arguments.length) return [φ0 / π * 180, φ1 / π * 180];
3384     return m(φ0 = _[0] * π / 180, φ1 = _[1] * π / 180);
3385   };
3386
3387   return p;
3388 }
3389
3390 function d3_geo_conicEqualArea(φ0, φ1) {
3391   var sinφ0 = Math.sin(φ0),
3392       n = (sinφ0 + Math.sin(φ1)) / 2,
3393       C = 1 + sinφ0 * (2 * n - sinφ0),
3394       ρ0 = Math.sqrt(C) / n;
3395
3396   function forward(λ, φ) {
3397     var ρ = Math.sqrt(C - 2 * n * Math.sin(φ)) / n;
3398     return [
3399       ρ * Math.sin(λ *= n),
3400       ρ0 - ρ * Math.cos(λ)
3401     ];
3402   }
3403
3404   forward.invert = function(x, y) {
3405     var ρ0_y = ρ0 - y;
3406     return [
3407       Math.atan2(x, ρ0_y) / n,
3408       d3_asin((C - (x * x + ρ0_y * ρ0_y) * n * n) / (2 * n))
3409     ];
3410   };
3411
3412   return forward;
3413 }
3414
3415 (d3.geo.conicEqualArea = function() {
3416   return d3_geo_conic(d3_geo_conicEqualArea);
3417 }).raw = d3_geo_conicEqualArea;
3418
3419 // ESRI:102003
3420 d3.geo.albers = function() {
3421   return d3.geo.conicEqualArea()
3422       .rotate([96, 0])
3423       .center([-.6, 38.7])
3424       .parallels([29.5, 45.5])
3425       .scale(1070);
3426 };
3427
3428 // A composite projection for the United States, configured by default for
3429 // 960×500. Also works quite well at 960×600 with scale 1285. The set of
3430 // standard parallels for each region comes from USGS, which is published here:
3431 // http://egsc.usgs.gov/isb/pubs/MapProjections/projections.html#albers
3432 d3.geo.albersUsa = function() {
3433   var lower48 = d3.geo.albers();
3434
3435   // EPSG:3338
3436   var alaska = d3.geo.conicEqualArea()
3437       .rotate([154, 0])
3438       .center([-2, 58.5])
3439       .parallels([55, 65]);
3440
3441   // ESRI:102007
3442   var hawaii = d3.geo.conicEqualArea()
3443       .rotate([157, 0])
3444       .center([-3, 19.9])
3445       .parallels([8, 18]);
3446
3447   var point,
3448       pointStream = {point: function(x, y) { point = [x, y]; }},
3449       lower48Point,
3450       alaskaPoint,
3451       hawaiiPoint;
3452
3453   function albersUsa(coordinates) {
3454     var x = coordinates[0], y = coordinates[1];
3455     point = null;
3456     (lower48Point(x, y), point)
3457         || (alaskaPoint(x, y), point)
3458         || hawaiiPoint(x, y);
3459     return point;
3460   }
3461
3462   albersUsa.invert = function(coordinates) {
3463     var k = lower48.scale(),
3464         t = lower48.translate(),
3465         x = (coordinates[0] - t[0]) / k,
3466         y = (coordinates[1] - t[1]) / k;
3467     return (y >= .120 && y < .234 && x >= -.425 && x < -.214 ? alaska
3468         : y >= .166 && y < .234 && x >= -.214 && x < -.115 ? hawaii
3469         : lower48).invert(coordinates);
3470   };
3471
3472   // A naïve multi-projection stream.
3473   // The projections must have mutually exclusive clip regions on the sphere,
3474   // as this will avoid emitting interleaving lines and polygons.
3475   albersUsa.stream = function(stream) {
3476     var lower48Stream = lower48.stream(stream),
3477         alaskaStream = alaska.stream(stream),
3478         hawaiiStream = hawaii.stream(stream);
3479     return {
3480       point: function(x, y) {
3481         lower48Stream.point(x, y);
3482         alaskaStream.point(x, y);
3483         hawaiiStream.point(x, y);
3484       },
3485       sphere: function() {
3486         lower48Stream.sphere();
3487         alaskaStream.sphere();
3488         hawaiiStream.sphere();
3489       },
3490       lineStart: function() {
3491         lower48Stream.lineStart();
3492         alaskaStream.lineStart();
3493         hawaiiStream.lineStart();
3494       },
3495       lineEnd: function() {
3496         lower48Stream.lineEnd();
3497         alaskaStream.lineEnd();
3498         hawaiiStream.lineEnd();
3499       },
3500       polygonStart: function() {
3501         lower48Stream.polygonStart();
3502         alaskaStream.polygonStart();
3503         hawaiiStream.polygonStart();
3504       },
3505       polygonEnd: function() {
3506         lower48Stream.polygonEnd();
3507         alaskaStream.polygonEnd();
3508         hawaiiStream.polygonEnd();
3509       }
3510     };
3511   };
3512
3513   albersUsa.precision = function(_) {
3514     if (!arguments.length) return lower48.precision();
3515     lower48.precision(_);
3516     alaska.precision(_);
3517     hawaii.precision(_);
3518     return albersUsa;
3519   };
3520
3521   albersUsa.scale = function(_) {
3522     if (!arguments.length) return lower48.scale();
3523     lower48.scale(_);
3524     alaska.scale(_ * .35);
3525     hawaii.scale(_);
3526     return albersUsa.translate(lower48.translate());
3527   };
3528
3529   albersUsa.translate = function(_) {
3530     if (!arguments.length) return lower48.translate();
3531     var k = lower48.scale(), x = +_[0], y = +_[1];
3532
3533     lower48Point = lower48
3534         .translate(_)
3535         .clipExtent([[x - .455 * k, y - .238 * k], [x + .455 * k, y + .238 * k]])
3536         .stream(pointStream).point;
3537
3538     alaskaPoint = alaska
3539         .translate([x - .307 * k, y + .201 * k])
3540         .clipExtent([[x - .425 * k + ε, y + .120 * k + ε], [x - .214 * k - ε, y + .234 * k - ε]])
3541         .stream(pointStream).point;
3542
3543     hawaiiPoint = hawaii
3544         .translate([x - .205 * k, y + .212 * k])
3545         .clipExtent([[x - .214 * k + ε, y + .166 * k + ε], [x - .115 * k - ε, y + .234 * k - ε]])
3546         .stream(pointStream).point;
3547
3548     return albersUsa;
3549   };
3550
3551   return albersUsa.scale(1070);
3552 };
3553
3554 d3.geo.bounds = (function() {
3555   var λ0, φ0, λ1, φ1, // bounds
3556       λ_, // previous λ-coordinate
3557       λ__, φ__, // first point
3558       p0, // previous 3D point
3559       dλSum,
3560       ranges,
3561       range;
3562
3563   var bound = {
3564     point: point,
3565     lineStart: lineStart,
3566     lineEnd: lineEnd,
3567
3568     polygonStart: function() {
3569       bound.point = ringPoint;
3570       bound.lineStart = ringStart;
3571       bound.lineEnd = ringEnd;
3572       dλSum = 0;
3573       d3_geo_area.polygonStart();
3574     },
3575     polygonEnd: function() {
3576       d3_geo_area.polygonEnd();
3577       bound.point = point;
3578       bound.lineStart = lineStart;
3579       bound.lineEnd = lineEnd;
3580       if (d3_geo_areaRingSum < 0) λ0 = -(λ1 = 180), φ0 = -(φ1 = 90);
3581       else if (dλSum > ε) φ1 = 90;
3582       else if (dλSum < -ε) φ0 = -90;
3583       range[0] = λ0, range[1] = λ1;
3584     }
3585   };
3586
3587   function point(λ, φ) {
3588     ranges.push(range = [λ0 = λ, λ1 = λ]);
3589     if (φ < φ0) φ0 = φ;
3590     if (φ > φ1) φ1 = φ;
3591   }
3592
3593   function linePoint(λ, φ) {
3594     var p = d3_geo_cartesian([λ * d3_radians, φ * d3_radians]);
3595     if (p0) {
3596       var normal = d3_geo_cartesianCross(p0, p),
3597           equatorial = [normal[1], -normal[0], 0],
3598           inflection = d3_geo_cartesianCross(equatorial, normal);
3599       d3_geo_cartesianNormalize(inflection);
3600       inflection = d3_geo_spherical(inflection);
3601       var dλ = λ - λ_,
3602           s = dλ > 0 ? 1 : -1,
3603           λi = inflection[0] * d3_degrees * s,
3604           antimeridian = abs(dλ) > 180;
3605       if (antimeridian ^ (s * λ_ < λi && λi < s * λ)) {
3606         var φi = inflection[1] * d3_degrees;
3607         if (φi > φ1) φ1 = φi;
3608       } else if (λi = (λi + 360) % 360 - 180, antimeridian ^ (s * λ_ < λi && λi < s * λ)) {
3609         var φi = -inflection[1] * d3_degrees;
3610         if (φi < φ0) φ0 = φi;
3611       } else {
3612         if (φ < φ0) φ0 = φ;
3613         if (φ > φ1) φ1 = φ;
3614       }
3615       if (antimeridian) {
3616         if (λ < λ_) {
3617           if (angle(λ0, λ) > angle(λ0, λ1)) λ1 = λ;
3618         } else {
3619           if (angle(λ, λ1) > angle(λ0, λ1)) λ0 = λ;
3620         }
3621       } else {
3622         if (λ1 >= λ0) {
3623           if (λ < λ0) λ0 = λ;
3624           if (λ > λ1) λ1 = λ;
3625         } else {
3626           if (λ > λ_) {
3627             if (angle(λ0, λ) > angle(λ0, λ1)) λ1 = λ;
3628           } else {
3629             if (angle(λ, λ1) > angle(λ0, λ1)) λ0 = λ;
3630           }
3631         }
3632       }
3633     } else {
3634       point(λ, φ);
3635     }
3636     p0 = p, λ_ = λ;
3637   }
3638
3639   function lineStart() { bound.point = linePoint; }
3640   function lineEnd() {
3641     range[0] = λ0, range[1] = λ1;
3642     bound.point = point;
3643     p0 = null;
3644   }
3645
3646   function ringPoint(λ, φ) {
3647     if (p0) {
3648       var dλ = λ - λ_;
3649       dλSum += abs(dλ) > 180 ? dλ + (dλ > 0 ? 360 : -360) : dλ;
3650     } else λ__ = λ, φ__ = φ;
3651     d3_geo_area.point(λ, φ);
3652     linePoint(λ, φ);
3653   }
3654
3655   function ringStart() {
3656     d3_geo_area.lineStart();
3657   }
3658
3659   function ringEnd() {
3660     ringPoint(λ__, φ__);
3661     d3_geo_area.lineEnd();
3662     if (abs(dλSum) > ε) λ0 = -(λ1 = 180);
3663     range[0] = λ0, range[1] = λ1;
3664     p0 = null;
3665   }
3666
3667   // Finds the left-right distance between two longitudes.
3668   // This is almost the same as (λ1 - λ0 + 360°) % 360°, except that we want
3669   // the distance between ±180° to be 360°.
3670   function angle(λ0, λ1) { return (λ1 -= λ0) < 0 ? λ1 + 360 : λ1; }
3671
3672   function compareRanges(a, b) { return a[0] - b[0]; }
3673
3674   function withinRange(x, range) {
3675     return range[0] <= range[1] ? range[0] <= x && x <= range[1] : x < range[0] || range[1] < x;
3676   }
3677
3678   return function(feature) {
3679     φ1 = λ1 = -(λ0 = φ0 = Infinity);
3680     ranges = [];
3681
3682     d3.geo.stream(feature, bound);
3683
3684     var n = ranges.length;
3685     if (n) {
3686       // First, sort ranges by their minimum longitudes.
3687       ranges.sort(compareRanges);
3688
3689       // Then, merge any ranges that overlap.
3690       for (var i = 1, a = ranges[0], b, merged = [a]; i < n; ++i) {
3691         b = ranges[i];
3692         if (withinRange(b[0], a) || withinRange(b[1], a)) {
3693           if (angle(a[0], b[1]) > angle(a[0], a[1])) a[1] = b[1];
3694           if (angle(b[0], a[1]) > angle(a[0], a[1])) a[0] = b[0];
3695         } else {
3696           merged.push(a = b);
3697         }
3698       }
3699
3700       // Finally, find the largest gap between the merged ranges.
3701       // The final bounding box will be the inverse of this gap.
3702       var best = -Infinity, dλ;
3703       for (var n = merged.length - 1, i = 0, a = merged[n], b; i <= n; a = b, ++i) {
3704         b = merged[i];
3705         if ((dλ = angle(a[1], b[0])) > best) best = dλ, λ0 = b[0], λ1 = a[1];
3706       }
3707     }
3708     ranges = range = null;
3709
3710     return λ0 === Infinity || φ0 === Infinity
3711         ? [[NaN, NaN], [NaN, NaN]]
3712         : [[λ0, φ0], [λ1, φ1]];
3713   };
3714 })();
3715
3716 d3.geo.centroid = function(object) {
3717   d3_geo_centroidW0 = d3_geo_centroidW1 =
3718   d3_geo_centroidX0 = d3_geo_centroidY0 = d3_geo_centroidZ0 =
3719   d3_geo_centroidX1 = d3_geo_centroidY1 = d3_geo_centroidZ1 =
3720   d3_geo_centroidX2 = d3_geo_centroidY2 = d3_geo_centroidZ2 = 0;
3721   d3.geo.stream(object, d3_geo_centroid);
3722
3723   var x = d3_geo_centroidX2,
3724       y = d3_geo_centroidY2,
3725       z = d3_geo_centroidZ2,
3726       m = x * x + y * y + z * z;
3727
3728   // If the area-weighted centroid is undefined, fall back to length-weighted centroid.
3729   if (m < ε2) {
3730     x = d3_geo_centroidX1, y = d3_geo_centroidY1, z = d3_geo_centroidZ1;
3731     // If the feature has zero length, fall back to arithmetic mean of point vectors.
3732     if (d3_geo_centroidW1 < ε) x = d3_geo_centroidX0, y = d3_geo_centroidY0, z = d3_geo_centroidZ0;
3733     m = x * x + y * y + z * z;
3734     // If the feature still has an undefined centroid, then return.
3735     if (m < ε2) return [NaN, NaN];
3736   }
3737
3738   return [Math.atan2(y, x) * d3_degrees, d3_asin(z / Math.sqrt(m)) * d3_degrees];
3739 };
3740
3741 var d3_geo_centroidW0,
3742     d3_geo_centroidW1,
3743     d3_geo_centroidX0,
3744     d3_geo_centroidY0,
3745     d3_geo_centroidZ0,
3746     d3_geo_centroidX1,
3747     d3_geo_centroidY1,
3748     d3_geo_centroidZ1,
3749     d3_geo_centroidX2,
3750     d3_geo_centroidY2,
3751     d3_geo_centroidZ2;
3752
3753 var d3_geo_centroid = {
3754   sphere: d3_noop,
3755   point: d3_geo_centroidPoint,
3756   lineStart: d3_geo_centroidLineStart,
3757   lineEnd: d3_geo_centroidLineEnd,
3758   polygonStart: function() {
3759     d3_geo_centroid.lineStart = d3_geo_centroidRingStart;
3760   },
3761   polygonEnd: function() {
3762     d3_geo_centroid.lineStart = d3_geo_centroidLineStart;
3763   }
3764 };
3765
3766 // Arithmetic mean of Cartesian vectors.
3767 function d3_geo_centroidPoint(λ, φ) {
3768   λ *= d3_radians;
3769   var cosφ = Math.cos(φ *= d3_radians);
3770   d3_geo_centroidPointXYZ(cosφ * Math.cos(λ), cosφ * Math.sin(λ), Math.sin(φ));
3771 }
3772
3773 function d3_geo_centroidPointXYZ(x, y, z) {
3774   ++d3_geo_centroidW0;
3775   d3_geo_centroidX0 += (x - d3_geo_centroidX0) / d3_geo_centroidW0;
3776   d3_geo_centroidY0 += (y - d3_geo_centroidY0) / d3_geo_centroidW0;
3777   d3_geo_centroidZ0 += (z - d3_geo_centroidZ0) / d3_geo_centroidW0;
3778 }
3779
3780 function d3_geo_centroidLineStart() {
3781   var x0, y0, z0; // previous point
3782
3783   d3_geo_centroid.point = function(λ, φ) {
3784     λ *= d3_radians;
3785     var cosφ = Math.cos(φ *= d3_radians);
3786     x0 = cosφ * Math.cos(λ);
3787     y0 = cosφ * Math.sin(λ);
3788     z0 = Math.sin(φ);
3789     d3_geo_centroid.point = nextPoint;
3790     d3_geo_centroidPointXYZ(x0, y0, z0);
3791   };
3792
3793   function nextPoint(λ, φ) {
3794     λ *= d3_radians;
3795     var cosφ = Math.cos(φ *= d3_radians),
3796         x = cosφ * Math.cos(λ),
3797         y = cosφ * Math.sin(λ),
3798         z = Math.sin(φ),
3799         w = Math.atan2(
3800           Math.sqrt((w = y0 * z - z0 * y) * w + (w = z0 * x - x0 * z) * w + (w = x0 * y - y0 * x) * w),
3801           x0 * x + y0 * y + z0 * z);
3802     d3_geo_centroidW1 += w;
3803     d3_geo_centroidX1 += w * (x0 + (x0 = x));
3804     d3_geo_centroidY1 += w * (y0 + (y0 = y));
3805     d3_geo_centroidZ1 += w * (z0 + (z0 = z));
3806     d3_geo_centroidPointXYZ(x0, y0, z0);
3807   }
3808 }
3809
3810 function d3_geo_centroidLineEnd() {
3811   d3_geo_centroid.point = d3_geo_centroidPoint;
3812 }
3813
3814 // See J. E. Brock, The Inertia Tensor for a Spherical Triangle,
3815 // J. Applied Mechanics 42, 239 (1975).
3816 function d3_geo_centroidRingStart() {
3817   var λ00, φ00, // first point
3818       x0, y0, z0; // previous point
3819
3820   d3_geo_centroid.point = function(λ, φ) {
3821     λ00 = λ, φ00 = φ;
3822     d3_geo_centroid.point = nextPoint;
3823     λ *= d3_radians;
3824     var cosφ = Math.cos(φ *= d3_radians);
3825     x0 = cosφ * Math.cos(λ);
3826     y0 = cosφ * Math.sin(λ);
3827     z0 = Math.sin(φ);
3828     d3_geo_centroidPointXYZ(x0, y0, z0);
3829   };
3830
3831   d3_geo_centroid.lineEnd = function() {
3832     nextPoint(λ00, φ00);
3833     d3_geo_centroid.lineEnd = d3_geo_centroidLineEnd;
3834     d3_geo_centroid.point = d3_geo_centroidPoint;
3835   };
3836
3837   function nextPoint(λ, φ) {
3838     λ *= d3_radians;
3839     var cosφ = Math.cos(φ *= d3_radians),
3840         x = cosφ * Math.cos(λ),
3841         y = cosφ * Math.sin(λ),
3842         z = Math.sin(φ),
3843         cx = y0 * z - z0 * y,
3844         cy = z0 * x - x0 * z,
3845         cz = x0 * y - y0 * x,
3846         m = Math.sqrt(cx * cx + cy * cy + cz * cz),
3847         u = x0 * x + y0 * y + z0 * z,
3848         v = m && -d3_acos(u) / m, // area weight
3849         w = Math.atan2(m, u); // line weight
3850     d3_geo_centroidX2 += v * cx;
3851     d3_geo_centroidY2 += v * cy;
3852     d3_geo_centroidZ2 += v * cz;
3853     d3_geo_centroidW1 += w;
3854     d3_geo_centroidX1 += w * (x0 + (x0 = x));
3855     d3_geo_centroidY1 += w * (y0 + (y0 = y));
3856     d3_geo_centroidZ1 += w * (z0 + (z0 = z));
3857     d3_geo_centroidPointXYZ(x0, y0, z0);
3858   }
3859 }
3860
3861 // TODO Unify this code with d3.geom.polygon area?
3862
3863 var d3_geo_pathAreaSum, d3_geo_pathAreaPolygon, d3_geo_pathArea = {
3864   point: d3_noop,
3865   lineStart: d3_noop,
3866   lineEnd: d3_noop,
3867
3868   // Only count area for polygon rings.
3869   polygonStart: function() {
3870     d3_geo_pathAreaPolygon = 0;
3871     d3_geo_pathArea.lineStart = d3_geo_pathAreaRingStart;
3872   },
3873   polygonEnd: function() {
3874     d3_geo_pathArea.lineStart = d3_geo_pathArea.lineEnd = d3_geo_pathArea.point = d3_noop;
3875     d3_geo_pathAreaSum += abs(d3_geo_pathAreaPolygon / 2);
3876   }
3877 };
3878
3879 function d3_geo_pathAreaRingStart() {
3880   var x00, y00, x0, y0;
3881
3882   // For the first point, …
3883   d3_geo_pathArea.point = function(x, y) {
3884     d3_geo_pathArea.point = nextPoint;
3885     x00 = x0 = x, y00 = y0 = y;
3886   };
3887
3888   // For subsequent points, …
3889   function nextPoint(x, y) {
3890     d3_geo_pathAreaPolygon += y0 * x - x0 * y;
3891     x0 = x, y0 = y;
3892   }
3893
3894   // For the last point, return to the start.
3895   d3_geo_pathArea.lineEnd = function() {
3896     nextPoint(x00, y00);
3897   };
3898 }
3899
3900 var d3_geo_pathBoundsX0,
3901     d3_geo_pathBoundsY0,
3902     d3_geo_pathBoundsX1,
3903     d3_geo_pathBoundsY1;
3904
3905 var d3_geo_pathBounds = {
3906   point: d3_geo_pathBoundsPoint,
3907   lineStart: d3_noop,
3908   lineEnd: d3_noop,
3909   polygonStart: d3_noop,
3910   polygonEnd: d3_noop
3911 };
3912
3913 function d3_geo_pathBoundsPoint(x, y) {
3914   if (x < d3_geo_pathBoundsX0) d3_geo_pathBoundsX0 = x;
3915   if (x > d3_geo_pathBoundsX1) d3_geo_pathBoundsX1 = x;
3916   if (y < d3_geo_pathBoundsY0) d3_geo_pathBoundsY0 = y;
3917   if (y > d3_geo_pathBoundsY1) d3_geo_pathBoundsY1 = y;
3918 }
3919 function d3_geo_pathBuffer() {
3920   var pointCircle = d3_geo_pathBufferCircle(4.5),
3921       buffer = [];
3922
3923   var stream = {
3924     point: point,
3925
3926     // While inside a line, override point to moveTo then lineTo.
3927     lineStart: function() { stream.point = pointLineStart; },
3928     lineEnd: lineEnd,
3929
3930     // While inside a polygon, override lineEnd to closePath.
3931     polygonStart: function() { stream.lineEnd = lineEndPolygon; },
3932     polygonEnd: function() { stream.lineEnd = lineEnd; stream.point = point; },
3933
3934     pointRadius: function(_) {
3935       pointCircle = d3_geo_pathBufferCircle(_);
3936       return stream;
3937     },
3938
3939     result: function() {
3940       if (buffer.length) {
3941         var result = buffer.join("");
3942         buffer = [];
3943         return result;
3944       }
3945     }
3946   };
3947
3948   function point(x, y) {
3949     buffer.push("M", x, ",", y, pointCircle);
3950   }
3951
3952   function pointLineStart(x, y) {
3953     buffer.push("M", x, ",", y);
3954     stream.point = pointLine;
3955   }
3956
3957   function pointLine(x, y) {
3958     buffer.push("L", x, ",", y);
3959   }
3960
3961   function lineEnd() {
3962     stream.point = point;
3963   }
3964
3965   function lineEndPolygon() {
3966     buffer.push("Z");
3967   }
3968
3969   return stream;
3970 }
3971
3972 function d3_geo_pathBufferCircle(radius) {
3973   return "m0," + radius
3974       + "a" + radius + "," + radius + " 0 1,1 0," + -2 * radius
3975       + "a" + radius + "," + radius + " 0 1,1 0," + 2 * radius
3976       + "z";
3977 }
3978
3979 // TODO Unify this code with d3.geom.polygon centroid?
3980 // TODO Enforce positive area for exterior, negative area for interior?
3981
3982 var d3_geo_pathCentroid = {
3983   point: d3_geo_pathCentroidPoint,
3984
3985   // For lines, weight by length.
3986   lineStart: d3_geo_pathCentroidLineStart,
3987   lineEnd: d3_geo_pathCentroidLineEnd,
3988
3989   // For polygons, weight by area.
3990   polygonStart: function() {
3991     d3_geo_pathCentroid.lineStart = d3_geo_pathCentroidRingStart;
3992   },
3993   polygonEnd: function() {
3994     d3_geo_pathCentroid.point = d3_geo_pathCentroidPoint;
3995     d3_geo_pathCentroid.lineStart = d3_geo_pathCentroidLineStart;
3996     d3_geo_pathCentroid.lineEnd = d3_geo_pathCentroidLineEnd;
3997   }
3998 };
3999
4000 function d3_geo_pathCentroidPoint(x, y) {
4001   d3_geo_centroidX0 += x;
4002   d3_geo_centroidY0 += y;
4003   ++d3_geo_centroidZ0;
4004 }
4005
4006 function d3_geo_pathCentroidLineStart() {
4007   var x0, y0;
4008
4009   d3_geo_pathCentroid.point = function(x, y) {
4010     d3_geo_pathCentroid.point = nextPoint;
4011     d3_geo_pathCentroidPoint(x0 = x, y0 = y);
4012   };
4013
4014   function nextPoint(x, y) {
4015     var dx = x - x0, dy = y - y0, z = Math.sqrt(dx * dx + dy * dy);
4016     d3_geo_centroidX1 += z * (x0 + x) / 2;
4017     d3_geo_centroidY1 += z * (y0 + y) / 2;
4018     d3_geo_centroidZ1 += z;
4019     d3_geo_pathCentroidPoint(x0 = x, y0 = y);
4020   }
4021 }
4022
4023 function d3_geo_pathCentroidLineEnd() {
4024   d3_geo_pathCentroid.point = d3_geo_pathCentroidPoint;
4025 }
4026
4027 function d3_geo_pathCentroidRingStart() {
4028   var x00, y00, x0, y0;
4029
4030   // For the first point, …
4031   d3_geo_pathCentroid.point = function(x, y) {
4032     d3_geo_pathCentroid.point = nextPoint;
4033     d3_geo_pathCentroidPoint(x00 = x0 = x, y00 = y0 = y);
4034   };
4035
4036   // For subsequent points, …
4037   function nextPoint(x, y) {
4038     var dx = x - x0, dy = y - y0, z = Math.sqrt(dx * dx + dy * dy);
4039     d3_geo_centroidX1 += z * (x0 + x) / 2;
4040     d3_geo_centroidY1 += z * (y0 + y) / 2;
4041     d3_geo_centroidZ1 += z;
4042
4043     z = y0 * x - x0 * y;
4044     d3_geo_centroidX2 += z * (x0 + x);
4045     d3_geo_centroidY2 += z * (y0 + y);
4046     d3_geo_centroidZ2 += z * 3;
4047     d3_geo_pathCentroidPoint(x0 = x, y0 = y);
4048   }
4049
4050   // For the last point, return to the start.
4051   d3_geo_pathCentroid.lineEnd = function() {
4052     nextPoint(x00, y00);
4053   };
4054 }
4055
4056 function d3_geo_pathContext(context) {
4057   var pointRadius = 4.5;
4058
4059   var stream = {
4060     point: point,
4061
4062     // While inside a line, override point to moveTo then lineTo.
4063     lineStart: function() { stream.point = pointLineStart; },
4064     lineEnd: lineEnd,
4065
4066     // While inside a polygon, override lineEnd to closePath.
4067     polygonStart: function() { stream.lineEnd = lineEndPolygon; },
4068     polygonEnd: function() { stream.lineEnd = lineEnd; stream.point = point; },
4069
4070     pointRadius: function(_) {
4071       pointRadius = _;
4072       return stream;
4073     },
4074
4075     result: d3_noop
4076   };
4077
4078   function point(x, y) {
4079     context.moveTo(x, y);
4080     context.arc(x, y, pointRadius, 0, τ);
4081   }
4082
4083   function pointLineStart(x, y) {
4084     context.moveTo(x, y);
4085     stream.point = pointLine;
4086   }
4087
4088   function pointLine(x, y) {
4089     context.lineTo(x, y);
4090   }
4091
4092   function lineEnd() {
4093     stream.point = point;
4094   }
4095
4096   function lineEndPolygon() {
4097     context.closePath();
4098   }
4099
4100   return stream;
4101 }
4102
4103 function d3_geo_resample(project) {
4104   var δ2 = .5, // precision, px²
4105       cosMinDistance = Math.cos(30 * d3_radians), // cos(minimum angular distance)
4106       maxDepth = 16;
4107
4108   function resample(stream) {
4109     return (maxDepth ? resampleRecursive : resampleNone)(stream);
4110   }
4111
4112   function resampleNone(stream) {
4113     return d3_geo_transformPoint(stream, function(x, y) {
4114       x = project(x, y);
4115       stream.point(x[0], x[1]);
4116     });
4117   }
4118
4119   function resampleRecursive(stream) {
4120     var λ00, φ00, x00, y00, a00, b00, c00, // first point
4121         λ0, x0, y0, a0, b0, c0; // previous point
4122
4123     var resample = {
4124       point: point,
4125       lineStart: lineStart,
4126       lineEnd: lineEnd,
4127       polygonStart: function() { stream.polygonStart(); resample.lineStart = ringStart; },
4128       polygonEnd: function() { stream.polygonEnd(); resample.lineStart = lineStart; }
4129     };
4130
4131     function point(x, y) {
4132       x = project(x, y);
4133       stream.point(x[0], x[1]);
4134     }
4135
4136     function lineStart() {
4137       x0 = NaN;
4138       resample.point = linePoint;
4139       stream.lineStart();
4140     }
4141
4142     function linePoint(λ, φ) {
4143       var c = d3_geo_cartesian([λ, φ]), p = project(λ, φ);
4144       resampleLineTo(x0, y0, λ0, a0, b0, c0, x0 = p[0], y0 = p[1], λ0 = λ, a0 = c[0], b0 = c[1], c0 = c[2], maxDepth, stream);
4145       stream.point(x0, y0);
4146     }
4147
4148     function lineEnd() {
4149       resample.point = point;
4150       stream.lineEnd();
4151     }
4152
4153     function ringStart() {
4154       lineStart();
4155       resample.point = ringPoint;
4156       resample.lineEnd = ringEnd;
4157     }
4158
4159     function ringPoint(λ, φ) {
4160       linePoint(λ00 = λ, φ00 = φ), x00 = x0, y00 = y0, a00 = a0, b00 = b0, c00 = c0;
4161       resample.point = linePoint;
4162     }
4163
4164     function ringEnd() {
4165       resampleLineTo(x0, y0, λ0, a0, b0, c0, x00, y00, λ00, a00, b00, c00, maxDepth, stream);
4166       resample.lineEnd = lineEnd;
4167       lineEnd();
4168     }
4169
4170     return resample;
4171   }
4172
4173   function resampleLineTo(x0, y0, λ0, a0, b0, c0, x1, y1, λ1, a1, b1, c1, depth, stream) {
4174     var dx = x1 - x0,
4175         dy = y1 - y0,
4176         d2 = dx * dx + dy * dy;
4177     if (d2 > 4 * δ2 && depth--) {
4178       var a = a0 + a1,
4179           b = b0 + b1,
4180           c = c0 + c1,
4181           m = Math.sqrt(a * a + b * b + c * c),
4182           φ2 = Math.asin(c /= m),
4183           λ2 = abs(abs(c) - 1) < ε || abs(λ0 - λ1) < ε ? (λ0 + λ1) / 2 : Math.atan2(b, a),
4184           p = project(λ2, φ2),
4185           x2 = p[0],
4186           y2 = p[1],
4187           dx2 = x2 - x0,
4188           dy2 = y2 - y0,
4189           dz = dy * dx2 - dx * dy2;
4190       if (dz * dz / d2 > δ2 // perpendicular projected distance
4191           || abs((dx * dx2 + dy * dy2) / d2 - .5) > .3 // midpoint close to an end
4192           || a0 * a1 + b0 * b1 + c0 * c1 < cosMinDistance) { // angular distance
4193         resampleLineTo(x0, y0, λ0, a0, b0, c0, x2, y2, λ2, a /= m, b /= m, c, depth, stream);
4194         stream.point(x2, y2);
4195         resampleLineTo(x2, y2, λ2, a, b, c, x1, y1, λ1, a1, b1, c1, depth, stream);
4196       }
4197     }
4198   }
4199
4200   resample.precision = function(_) {
4201     if (!arguments.length) return Math.sqrt(δ2);
4202     maxDepth = (δ2 = _ * _) > 0 && 16;
4203     return resample;
4204   };
4205
4206   return resample;
4207 }
4208
4209 d3.geo.path = function() {
4210   var pointRadius = 4.5,
4211       projection,
4212       context,
4213       projectStream,
4214       contextStream,
4215       cacheStream;
4216
4217   function path(object) {
4218     if (object) {
4219       if (typeof pointRadius === "function") contextStream.pointRadius(+pointRadius.apply(this, arguments));
4220       if (!cacheStream || !cacheStream.valid) cacheStream = projectStream(contextStream);
4221       d3.geo.stream(object, cacheStream);
4222     }
4223     return contextStream.result();
4224   }
4225
4226   path.area = function(object) {
4227     d3_geo_pathAreaSum = 0;
4228     d3.geo.stream(object, projectStream(d3_geo_pathArea));
4229     return d3_geo_pathAreaSum;
4230   };
4231
4232   path.centroid = function(object) {
4233     d3_geo_centroidX0 = d3_geo_centroidY0 = d3_geo_centroidZ0 =
4234     d3_geo_centroidX1 = d3_geo_centroidY1 = d3_geo_centroidZ1 =
4235     d3_geo_centroidX2 = d3_geo_centroidY2 = d3_geo_centroidZ2 = 0;
4236     d3.geo.stream(object, projectStream(d3_geo_pathCentroid));
4237     return d3_geo_centroidZ2 ? [d3_geo_centroidX2 / d3_geo_centroidZ2, d3_geo_centroidY2 / d3_geo_centroidZ2]
4238         : d3_geo_centroidZ1 ? [d3_geo_centroidX1 / d3_geo_centroidZ1, d3_geo_centroidY1 / d3_geo_centroidZ1]
4239         : d3_geo_centroidZ0 ? [d3_geo_centroidX0 / d3_geo_centroidZ0, d3_geo_centroidY0 / d3_geo_centroidZ0]
4240         : [NaN, NaN];
4241   };
4242
4243   path.bounds = function(object) {
4244     d3_geo_pathBoundsX1 = d3_geo_pathBoundsY1 = -(d3_geo_pathBoundsX0 = d3_geo_pathBoundsY0 = Infinity);
4245     d3.geo.stream(object, projectStream(d3_geo_pathBounds));
4246     return [[d3_geo_pathBoundsX0, d3_geo_pathBoundsY0], [d3_geo_pathBoundsX1, d3_geo_pathBoundsY1]];
4247   };
4248
4249   path.projection = function(_) {
4250     if (!arguments.length) return projection;
4251     projectStream = (projection = _) ? _.stream || d3_geo_pathProjectStream(_) : d3_identity;
4252     return reset();
4253   };
4254
4255   path.context = function(_) {
4256     if (!arguments.length) return context;
4257     contextStream = (context = _) == null ? new d3_geo_pathBuffer : new d3_geo_pathContext(_);
4258     if (typeof pointRadius !== "function") contextStream.pointRadius(pointRadius);
4259     return reset();
4260   };
4261
4262   path.pointRadius = function(_) {
4263     if (!arguments.length) return pointRadius;
4264     pointRadius = typeof _ === "function" ? _ : (contextStream.pointRadius(+_), +_);
4265     return path;
4266   };
4267
4268   function reset() {
4269     cacheStream = null;
4270     return path;
4271   }
4272
4273   return path.projection(d3.geo.albersUsa()).context(null);
4274 };
4275
4276 function d3_geo_pathProjectStream(project) {
4277   var resample = d3_geo_resample(function(x, y) { return project([x * d3_degrees, y * d3_degrees]); });
4278   return function(stream) { return d3_geo_projectionRadians(resample(stream)); };
4279 }
4280
4281 d3.geo.transform = function(methods) {
4282   return {
4283     stream: function(stream) {
4284       var transform = new d3_geo_transform(stream);
4285       for (var k in methods) transform[k] = methods[k];
4286       return transform;
4287     }
4288   };
4289 };
4290
4291 function d3_geo_transform(stream) {
4292   this.stream = stream;
4293 }
4294
4295 d3_geo_transform.prototype = {
4296   point: function(x, y) { this.stream.point(x, y); },
4297   sphere: function() { this.stream.sphere(); },
4298   lineStart: function() { this.stream.lineStart(); },
4299   lineEnd: function() { this.stream.lineEnd(); },
4300   polygonStart: function() { this.stream.polygonStart(); },
4301   polygonEnd: function() { this.stream.polygonEnd(); }
4302 };
4303
4304 function d3_geo_transformPoint(stream, point) {
4305   return {
4306     point: point,
4307     sphere: function() { stream.sphere(); },
4308     lineStart: function() { stream.lineStart(); },
4309     lineEnd: function() { stream.lineEnd(); },
4310     polygonStart: function() { stream.polygonStart(); },
4311     polygonEnd: function() { stream.polygonEnd(); },
4312   };
4313 }
4314
4315 d3.geo.projection = d3_geo_projection;
4316 d3.geo.projectionMutator = d3_geo_projectionMutator;
4317
4318 function d3_geo_projection(project) {
4319   return d3_geo_projectionMutator(function() { return project; })();
4320 }
4321
4322 function d3_geo_projectionMutator(projectAt) {
4323   var project,
4324       rotate,
4325       projectRotate,
4326       projectResample = d3_geo_resample(function(x, y) { x = project(x, y); return [x[0] * k + δx, δy - x[1] * k]; }),
4327       k = 150, // scale
4328       x = 480, y = 250, // translate
4329       λ = 0, φ = 0, // center
4330       δλ = 0, δφ = 0, δγ = 0, // rotate
4331       δx, δy, // center
4332       preclip = d3_geo_clipAntimeridian,
4333       postclip = d3_identity,
4334       clipAngle = null,
4335       clipExtent = null,
4336       stream;
4337
4338   function projection(point) {
4339     point = projectRotate(point[0] * d3_radians, point[1] * d3_radians);
4340     return [point[0] * k + δx, δy - point[1] * k];
4341   }
4342
4343   function invert(point) {
4344     point = projectRotate.invert((point[0] - δx) / k, (δy - point[1]) / k);
4345     return point && [point[0] * d3_degrees, point[1] * d3_degrees];
4346   }
4347
4348   projection.stream = function(output) {
4349     if (stream) stream.valid = false;
4350     stream = d3_geo_projectionRadians(preclip(rotate, projectResample(postclip(output))));
4351     stream.valid = true; // allow caching by d3.geo.path
4352     return stream;
4353   };
4354
4355   projection.clipAngle = function(_) {
4356     if (!arguments.length) return clipAngle;
4357     preclip = _ == null ? (clipAngle = _, d3_geo_clipAntimeridian) : d3_geo_clipCircle((clipAngle = +_) * d3_radians);
4358     return invalidate();
4359   };
4360
4361   projection.clipExtent = function(_) {
4362     if (!arguments.length) return clipExtent;
4363     clipExtent = _;
4364     postclip = _ ? d3_geo_clipExtent(_[0][0], _[0][1], _[1][0], _[1][1]) : d3_identity;
4365     return invalidate();
4366   };
4367
4368   projection.scale = function(_) {
4369     if (!arguments.length) return k;
4370     k = +_;
4371     return reset();
4372   };
4373
4374   projection.translate = function(_) {
4375     if (!arguments.length) return [x, y];
4376     x = +_[0];
4377     y = +_[1];
4378     return reset();
4379   };
4380
4381   projection.center = function(_) {
4382     if (!arguments.length) return [λ * d3_degrees, φ * d3_degrees];
4383     λ = _[0] % 360 * d3_radians;
4384     φ = _[1] % 360 * d3_radians;
4385     return reset();
4386   };
4387
4388   projection.rotate = function(_) {
4389     if (!arguments.length) return [δλ * d3_degrees, δφ * d3_degrees, δγ * d3_degrees];
4390     δλ = _[0] % 360 * d3_radians;
4391     δφ = _[1] % 360 * d3_radians;
4392     δγ = _.length > 2 ? _[2] % 360 * d3_radians : 0;
4393     return reset();
4394   };
4395
4396   d3.rebind(projection, projectResample, "precision");
4397
4398   function reset() {
4399     projectRotate = d3_geo_compose(rotate = d3_geo_rotation(δλ, δφ, δγ), project);
4400     var center = project(λ, φ);
4401     δx = x - center[0] * k;
4402     δy = y + center[1] * k;
4403     return invalidate();
4404   }
4405
4406   function invalidate() {
4407     if (stream) stream.valid = false, stream = null;
4408     return projection;
4409   }
4410
4411   return function() {
4412     project = projectAt.apply(this, arguments);
4413     projection.invert = project.invert && invert;
4414     return reset();
4415   };
4416 }
4417
4418 function d3_geo_projectionRadians(stream) {
4419   return d3_geo_transformPoint(stream, function(x, y) {
4420     stream.point(x * d3_radians, y * d3_radians);
4421   });
4422 }
4423
4424 function d3_geo_mercator(λ, φ) {
4425   return [λ, Math.log(Math.tan(π / 4 + φ / 2))];
4426 }
4427
4428 d3_geo_mercator.invert = function(x, y) {
4429   return [x, 2 * Math.atan(Math.exp(y)) - halfπ];
4430 };
4431
4432 function d3_geo_mercatorProjection(project) {
4433   var m = d3_geo_projection(project),
4434       scale = m.scale,
4435       translate = m.translate,
4436       clipExtent = m.clipExtent,
4437       clipAuto;
4438
4439   m.scale = function() {
4440     var v = scale.apply(m, arguments);
4441     return v === m ? (clipAuto ? m.clipExtent(null) : m) : v;
4442   };
4443
4444   m.translate = function() {
4445     var v = translate.apply(m, arguments);
4446     return v === m ? (clipAuto ? m.clipExtent(null) : m) : v;
4447   };
4448
4449   m.clipExtent = function(_) {
4450     var v = clipExtent.apply(m, arguments);
4451     if (v === m) {
4452       if (clipAuto = _ == null) {
4453         var k = π * scale(), t = translate();
4454         clipExtent([[t[0] - k, t[1] - k], [t[0] + k, t[1] + k]]);
4455       }
4456     } else if (clipAuto) {
4457       v = null;
4458     }
4459     return v;
4460   };
4461
4462   return m.clipExtent(null);
4463 }
4464
4465 (d3.geo.mercator = function() {
4466   return d3_geo_mercatorProjection(d3_geo_mercator);
4467 }).raw = d3_geo_mercator;
4468 d3.geom = {};
4469
4470 d3.geom.polygon = function(coordinates) {
4471   d3_subclass(coordinates, d3_geom_polygonPrototype);
4472   return coordinates;
4473 };
4474
4475 var d3_geom_polygonPrototype = d3.geom.polygon.prototype = [];
4476
4477 d3_geom_polygonPrototype.area = function() {
4478   var i = -1,
4479       n = this.length,
4480       a,
4481       b = this[n - 1],
4482       area = 0;
4483
4484   while (++i < n) {
4485     a = b;
4486     b = this[i];
4487     area += a[1] * b[0] - a[0] * b[1];
4488   }
4489
4490   return area * .5;
4491 };
4492
4493 d3_geom_polygonPrototype.centroid = function(k) {
4494   var i = -1,
4495       n = this.length,
4496       x = 0,
4497       y = 0,
4498       a,
4499       b = this[n - 1],
4500       c;
4501
4502   if (!arguments.length) k = -1 / (6 * this.area());
4503
4504   while (++i < n) {
4505     a = b;
4506     b = this[i];
4507     c = a[0] * b[1] - b[0] * a[1];
4508     x += (a[0] + b[0]) * c;
4509     y += (a[1] + b[1]) * c;
4510   }
4511
4512   return [x * k, y * k];
4513 };
4514
4515 // The Sutherland-Hodgman clipping algorithm.
4516 // Note: requires the clip polygon to be counterclockwise and convex.
4517 d3_geom_polygonPrototype.clip = function(subject) {
4518   var input,
4519       closed = d3_geom_polygonClosed(subject),
4520       i = -1,
4521       n = this.length - d3_geom_polygonClosed(this),
4522       j,
4523       m,
4524       a = this[n - 1],
4525       b,
4526       c,
4527       d;
4528
4529   while (++i < n) {
4530     input = subject.slice();
4531     subject.length = 0;
4532     b = this[i];
4533     c = input[(m = input.length - closed) - 1];
4534     j = -1;
4535     while (++j < m) {
4536       d = input[j];
4537       if (d3_geom_polygonInside(d, a, b)) {
4538         if (!d3_geom_polygonInside(c, a, b)) {
4539           subject.push(d3_geom_polygonIntersect(c, d, a, b));
4540         }
4541         subject.push(d);
4542       } else if (d3_geom_polygonInside(c, a, b)) {
4543         subject.push(d3_geom_polygonIntersect(c, d, a, b));
4544       }
4545       c = d;
4546     }
4547     if (closed) subject.push(subject[0]);
4548     a = b;
4549   }
4550
4551   return subject;
4552 };
4553
4554 function d3_geom_polygonInside(p, a, b) {
4555   return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
4556 }
4557
4558 // Intersect two infinite lines cd and ab.
4559 function d3_geom_polygonIntersect(c, d, a, b) {
4560   var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3,
4561       y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3,
4562       ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
4563   return [x1 + ua * x21, y1 + ua * y21];
4564 }
4565
4566 // Returns true if the polygon is closed.
4567 function d3_geom_polygonClosed(coordinates) {
4568   var a = coordinates[0],
4569       b = coordinates[coordinates.length - 1];
4570   return !(a[0] - b[0] || a[1] - b[1]);
4571 }
4572 function d3_geom_pointX(d) {
4573   return d[0];
4574 }
4575
4576 function d3_geom_pointY(d) {
4577   return d[1];
4578 }
4579
4580 /**
4581  * Computes the 2D convex hull of a set of points using Graham's scanning
4582  * algorithm. The algorithm has been implemented as described in Cormen,
4583  * Leiserson, and Rivest's Introduction to Algorithms. The running time of
4584  * this algorithm is O(n log n), where n is the number of input points.
4585  *
4586  * @param vertices [[x1, y1], [x2, y2], …]
4587  * @returns polygon [[x1, y1], [x2, y2], …]
4588  */
4589 d3.geom.hull = function(vertices) {
4590   var x = d3_geom_pointX,
4591       y = d3_geom_pointY;
4592
4593   if (arguments.length) return hull(vertices);
4594
4595   function hull(data) {
4596     if (data.length < 3) return [];
4597
4598     var fx = d3_functor(x),
4599         fy = d3_functor(y),
4600         n = data.length,
4601         vertices, // TODO use parallel arrays
4602         plen = n - 1,
4603         points = [],
4604         stack = [],
4605         d,
4606         i, j, h = 0, x1, y1, x2, y2, u, v, a, sp;
4607
4608     if (fx === d3_geom_pointX && y === d3_geom_pointY) vertices = data;
4609     else for (i = 0, vertices = []; i < n; ++i) {
4610       vertices.push([+fx.call(this, d = data[i], i), +fy.call(this, d, i)]);
4611     }
4612
4613     // find the starting ref point: leftmost point with the minimum y coord
4614     for (i = 1; i < n; ++i) {
4615       if (vertices[i][1] < vertices[h][1]
4616           || vertices[i][1] == vertices[h][1]
4617           && vertices[i][0] < vertices[h][0]) h = i;
4618     }
4619
4620     // calculate polar angles from ref point and sort
4621     for (i = 0; i < n; ++i) {
4622       if (i === h) continue;
4623       y1 = vertices[i][1] - vertices[h][1];
4624       x1 = vertices[i][0] - vertices[h][0];
4625       points.push({angle: Math.atan2(y1, x1), index: i});
4626     }
4627     points.sort(function(a, b) { return a.angle - b.angle; });
4628
4629     // toss out duplicate angles
4630     a = points[0].angle;
4631     v = points[0].index;
4632     u = 0;
4633     for (i = 1; i < plen; ++i) {
4634       j = points[i].index;
4635       if (a == points[i].angle) {
4636         // keep angle for point most distant from the reference
4637         x1 = vertices[v][0] - vertices[h][0];
4638         y1 = vertices[v][1] - vertices[h][1];
4639         x2 = vertices[j][0] - vertices[h][0];
4640         y2 = vertices[j][1] - vertices[h][1];
4641         if (x1 * x1 + y1 * y1 >= x2 * x2 + y2 * y2) {
4642           points[i].index = -1;
4643           continue;
4644         } else {
4645           points[u].index = -1;
4646         }
4647       }
4648       a = points[i].angle;
4649       u = i;
4650       v = j;
4651     }
4652
4653     // initialize the stack
4654     stack.push(h);
4655     for (i = 0, j = 0; i < 2; ++j) {
4656       if (points[j].index > -1) {
4657         stack.push(points[j].index);
4658         i++;
4659       }
4660     }
4661     sp = stack.length;
4662
4663     // do graham's scan
4664     for (; j < plen; ++j) {
4665       if (points[j].index < 0) continue; // skip tossed out points
4666       while (!d3_geom_hullCCW(stack[sp - 2], stack[sp - 1], points[j].index, vertices)) {
4667         --sp;
4668       }
4669       stack[sp++] = points[j].index;
4670     }
4671
4672     // construct the hull
4673     var poly = [];
4674     for (i = sp - 1; i >= 0; --i) poly.push(data[stack[i]]);
4675     return poly;
4676   }
4677
4678   hull.x = function(_) {
4679     return arguments.length ? (x = _, hull) : x;
4680   };
4681
4682   hull.y = function(_) {
4683     return arguments.length ? (y = _, hull) : y;
4684   };
4685
4686   return hull;
4687 };
4688
4689 // are three points in counter-clockwise order?
4690 function d3_geom_hullCCW(i1, i2, i3, v) {
4691   var t, a, b, c, d, e, f;
4692   t = v[i1]; a = t[0]; b = t[1];
4693   t = v[i2]; c = t[0]; d = t[1];
4694   t = v[i3]; e = t[0]; f = t[1];
4695   return (f - b) * (c - a) - (d - b) * (e - a) > 0;
4696 }
4697
4698 var d3_ease_default = function() { return d3_identity; };
4699
4700 var d3_ease = d3.map({
4701   linear: d3_ease_default,
4702   poly: d3_ease_poly,
4703   quad: function() { return d3_ease_quad; },
4704   cubic: function() { return d3_ease_cubic; },
4705   sin: function() { return d3_ease_sin; },
4706   exp: function() { return d3_ease_exp; },
4707   circle: function() { return d3_ease_circle; },
4708   elastic: d3_ease_elastic,
4709   back: d3_ease_back,
4710   bounce: function() { return d3_ease_bounce; }
4711 });
4712
4713 var d3_ease_mode = d3.map({
4714   "in": d3_identity,
4715   "out": d3_ease_reverse,
4716   "in-out": d3_ease_reflect,
4717   "out-in": function(f) { return d3_ease_reflect(d3_ease_reverse(f)); }
4718 });
4719
4720 d3.ease = function(name) {
4721   var i = name.indexOf("-"),
4722       t = i >= 0 ? name.substring(0, i) : name,
4723       m = i >= 0 ? name.substring(i + 1) : "in";
4724   t = d3_ease.get(t) || d3_ease_default;
4725   m = d3_ease_mode.get(m) || d3_identity;
4726   return d3_ease_clamp(m(t.apply(null, d3_arraySlice.call(arguments, 1))));
4727 };
4728
4729 function d3_ease_clamp(f) {
4730   return function(t) {
4731     return t <= 0 ? 0 : t >= 1 ? 1 : f(t);
4732   };
4733 }
4734
4735 function d3_ease_reverse(f) {
4736   return function(t) {
4737     return 1 - f(1 - t);
4738   };
4739 }
4740
4741 function d3_ease_reflect(f) {
4742   return function(t) {
4743     return .5 * (t < .5 ? f(2 * t) : (2 - f(2 - 2 * t)));
4744   };
4745 }
4746
4747 function d3_ease_quad(t) {
4748   return t * t;
4749 }
4750
4751 function d3_ease_cubic(t) {
4752   return t * t * t;
4753 }
4754
4755 // Optimized clamp(reflect(poly(3))).
4756 function d3_ease_cubicInOut(t) {
4757   if (t <= 0) return 0;
4758   if (t >= 1) return 1;
4759   var t2 = t * t, t3 = t2 * t;
4760   return 4 * (t < .5 ? t3 : 3 * (t - t2) + t3 - .75);
4761 }
4762
4763 function d3_ease_poly(e) {
4764   return function(t) {
4765     return Math.pow(t, e);
4766   };
4767 }
4768
4769 function d3_ease_sin(t) {
4770   return 1 - Math.cos(t * halfπ);
4771 }
4772
4773 function d3_ease_exp(t) {
4774   return Math.pow(2, 10 * (t - 1));
4775 }
4776
4777 function d3_ease_circle(t) {
4778   return 1 - Math.sqrt(1 - t * t);
4779 }
4780
4781 function d3_ease_elastic(a, p) {
4782   var s;
4783   if (arguments.length < 2) p = 0.45;
4784   if (arguments.length) s = p / τ * Math.asin(1 / a);
4785   else a = 1, s = p / 4;
4786   return function(t) {
4787     return 1 + a * Math.pow(2, -10 * t) * Math.sin((t - s) * τ / p);
4788   };
4789 }
4790
4791 function d3_ease_back(s) {
4792   if (!s) s = 1.70158;
4793   return function(t) {
4794     return t * t * ((s + 1) * t - s);
4795   };
4796 }
4797
4798 function d3_ease_bounce(t) {
4799   return t < 1 / 2.75 ? 7.5625 * t * t
4800       : t < 2 / 2.75 ? 7.5625 * (t -= 1.5 / 2.75) * t + .75
4801       : t < 2.5 / 2.75 ? 7.5625 * (t -= 2.25 / 2.75) * t + .9375
4802       : 7.5625 * (t -= 2.625 / 2.75) * t + .984375;
4803 }
4804
4805 function d3_transition(groups, id) {
4806   d3_subclass(groups, d3_transitionPrototype);
4807
4808   groups.id = id; // Note: read-only!
4809
4810   return groups;
4811 }
4812
4813 var d3_transitionPrototype = [],
4814     d3_transitionId = 0,
4815     d3_transitionInheritId,
4816     d3_transitionInherit;
4817
4818 d3_transitionPrototype.call = d3_selectionPrototype.call;