import “../math/trigonometry”; import “spherical”;
// General spherical polygon clipping algorithm: takes a polygon, cuts it into // visible line segments and rejoins the segments by interpolating along the // clip edge. function d3_geo_clipPolygon(segments, compare, inside, interpolate, listener) {
var subject = [], clip = []; segments.forEach(function(segment) { if ((n = segment.length - 1) <= 0) return; var n, p0 = segment[0], p1 = segment[n]; // If the first and last points of a segment are coincident, then treat as // a closed ring. // TODO if all rings are closed, then the winding order of the exterior // ring should be checked. if (d3_geo_sphericalEqual(p0, p1)) { listener.lineStart(); for (var i = 0; i < n; ++i) listener.point((p0 = segment[i])[0], p0[1]); listener.lineEnd(); return; } var a = {point: p0, points: segment, other: null, visited: false, entry: true, subject: true}, b = {point: p0, points: [p0], other: a, visited: false, entry: false, subject: false}; a.other = b; subject.push(a); clip.push(b); a = {point: p1, points: [p1], other: null, visited: false, entry: false, subject: true}; b = {point: p1, points: [p1], other: a, visited: false, entry: true, subject: false}; a.other = b; subject.push(a); clip.push(b); }); clip.sort(compare); d3_geo_clipPolygonLinkCircular(subject); d3_geo_clipPolygonLinkCircular(clip); if (!subject.length) return; if (inside) for (var i = 1, e = !inside(clip[0].point), n = clip.length; i < n; ++i) { clip[i].entry = (e = !e); } var start = subject[0], current, points, point; while (1) { // Find first unvisited intersection. current = start; while (current.visited) if ((current = current.next) === start) return; points = current.points; listener.lineStart(); do { current.visited = current.other.visited = true; if (current.entry) { if (current.subject) { for (var i = 0; i < points.length; i++) listener.point((point = points[i])[0], point[1]); } else { interpolate(current.point, current.next.point, 1, listener); } current = current.next; } else { if (current.subject) { points = current.prev.points; for (var i = points.length; --i >= 0;) listener.point((point = points[i])[0], point[1]); } else { interpolate(current.point, current.prev.point, -1, listener); } current = current.prev; } current = current.other; points = current.points; } while (!current.visited); listener.lineEnd(); }
}
function d3_geo_clipPolygonLinkCircular(array) {
if (!(n = array.length)) return; var n, i = 0, a = array[0], b; while (++i < n) { a.next = b = array[i]; b.prev = a; a = b; } a.next = b = array[0]; b.prev = a;
}