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;

}