import "../core/identity";

import "../core/noop";

import "geo";

import "stream";

import "area";

import "cartesian";

import "spherical";

d3.geo.bounds = (function() {

var λ0, φ0, λ1, φ1, // bounds

λ_, // previous λ-coordinate

λ__, φ__, // first point

p0, // previous 3D point

dλSum,

ranges,

range;

var bound = {

point: point,

lineStart: lineStart,

lineEnd: lineEnd,

polygonStart: function() {

bound.point = ringPoint;

bound.lineStart = ringStart;

bound.lineEnd = ringEnd;

dλSum = 0;

d3_geo_area.polygonStart();

},

polygonEnd: function() {

d3_geo_area.polygonEnd();

bound.point = point;

bound.lineStart = lineStart;

bound.lineEnd = lineEnd;

if (d3_geo_areaRingSum < 0) λ0 = -(λ1 = 180), φ0 = -(φ1 = 90);

else if (dλSum > ε) φ1 = 90;

else if (dλSum < -ε) φ0 = -90;

range[0] = λ0, range[1] = λ1;

}

};

function point(λ, φ) {

ranges.push(range = [λ0 = λ, λ1 = λ]);

if (φ < φ0) φ0 = φ;

if (φ > φ1) φ1 = φ;

}

function linePoint(λ, φ) {

var p = d3_geo_cartesian([λ * d3_radians, φ * d3_radians]);

if (p0) {

var normal = d3_geo_cartesianCross(p0, p),

equatorial = [normal[1], -normal[0], 0],

inflection = d3_geo_cartesianCross(equatorial, normal);

d3_geo_cartesianNormalize(inflection);

inflection = d3_geo_spherical(inflection);

var dλ = λ - λ_,

s = dλ > 0 ? 1 : -1,

λi = inflection[0] * d3_degrees * s,

antimeridian = Math.abs(dλ) > 180;

if (antimeridian ^ (s * λ_ < λi && λi < s * λ)) {

var φi = inflection[1] * d3_degrees;

if (φi > φ1) φ1 = φi;

} else if (λi = (λi + 360) % 360 - 180, antimeridian ^ (s * λ_ < λi && λi < s * λ)) {

var φi = -inflection[1] * d3_degrees;

if (φi < φ0) φ0 = φi;

} else {

if (φ < φ0) φ0 = φ;

if (φ > φ1) φ1 = φ;

}

if (antimeridian) {

if (λ < λ_) {

if (angle(λ0, λ) > angle(λ0, λ1)) λ1 = λ;

} else {

if (angle(λ, λ1) > angle(λ0, λ1)) λ0 = λ;

}

} else {

if (λ1 >= λ0) {

if (λ < λ0) λ0 = λ;

if (λ > λ1) λ1 = λ;

} else {

if (λ > λ_) {

if (angle(λ0, λ) > angle(λ0, λ1)) λ1 = λ;

} else {

if (angle(λ, λ1) > angle(λ0, λ1)) λ0 = λ;

}

}

}

} else {

point(λ, φ);

}

p0 = p, λ_ = λ;

}

function lineStart() { bound.point = linePoint; }

function lineEnd() {

range[0] = λ0, range[1] = λ1;

bound.point = point;

p0 = null;

}

function ringPoint(λ, φ) {

if (p0) {

var dλ = λ - λ_;

dλSum += Math.abs(dλ) > 180 ? dλ + (dλ > 0 ? 360 : -360) : dλ;

} else λ__ = λ, φ__ = φ;

d3_geo_area.point(λ, φ);

linePoint(λ, φ);

}

function ringStart() {

d3_geo_area.lineStart();

}

function ringEnd() {

ringPoint(λ__, φ__);

d3_geo_area.lineEnd();

if (Math.abs(dλSum) > ε) λ0 = -(λ1 = 180);

range[0] = λ0, range[1] = λ1;

p0 = null;

}

// Finds the left-right distance between two longitudes.

// This is almost the same as (λ1 - λ0 + 360°) % 360°, except that we want

// the distance between ±180° to be 360°.

function angle(λ0, λ1) { return (λ1 -= λ0) < 0 ? λ1 + 360 : λ1; }

function compareRanges(a, b) { return a[0] - b[0]; }

function withinRange(x, range) {

return range[0] <= range[1] ? range[0] <= x && x <= range[1] : x < range[0] || range[1] < x;

}

return function(feature) {

φ1 = λ1 = -(λ0 = φ0 = Infinity);

ranges = [];

d3.geo.stream(feature, bound);

var n = ranges.length;

if (n) {

// First, sort ranges by their minimum longitudes.

ranges.sort(compareRanges);

// Then, merge any ranges that overlap.

for (var i = 1, a = ranges[0], b, merged = [a]; i < n; ++i) {

b = ranges[i];

if (withinRange(b[0], a) || withinRange(b[1], a)) {

if (angle(a[0], b[1]) > angle(a[0], a[1])) a[1] = b[1];

if (angle(b[0], a[1]) > angle(a[0], a[1])) a[0] = b[0];

} else {

merged.push(a = b);

}

}

// Finally, find the largest gap between the merged ranges.

// The final bounding box will be the inverse of this gap.

var best = -Infinity, dλ;

for (var n = merged.length - 1, i = 0, a = merged[n], b; i <= n; a = b, ++i) {

b = merged[i];

if ((dλ = angle(a[1], b[0])) > best) best = dλ, λ0 = b[0], λ1 = a[1];

}

}

ranges = range = null;

return λ0 === Infinity || φ0 === Infinity

? [[NaN, NaN], [NaN, NaN]]

: [[λ0, φ0], [λ1, φ1]];

};

})();