Upload 6270 files

4083225 verified 6 months ago

2.77 kB

import pointEqual from "../pointEqual.js";
import {epsilon} from "../math.js";

function Intersection(point, points, other, entry) {
  this.x = point;
  this.z = points;
  this.o = other; // another intersection
  this.e = entry; // is an entry?
  this.v = false; // visited
  this.n = this.p = null; // next & previous
}

// A generalized polygon clipping algorithm: given a polygon that has been cut
// into its visible line segments, and rejoins the segments by interpolating
// along the clip edge.
export default function(segments, compareIntersection, startInside, interpolate, stream) {
  var subject = [],
      clip = [],
      i,
      n;

  segments.forEach(function(segment) {
    if ((n = segment.length - 1) <= 0) return;
    var n, p0 = segment[0], p1 = segment[n], x;

    if (pointEqual(p0, p1)) {
      if (!p0[2] && !p1[2]) {
        stream.lineStart();
        for (i = 0; i < n; ++i) stream.point((p0 = segment[i])[0], p0[1]);
        stream.lineEnd();
        return;
      }
      // handle degenerate cases by moving the point
      p1[0] += 2 * epsilon;
    }

    subject.push(x = new Intersection(p0, segment, null, true));
    clip.push(x.o = new Intersection(p0, null, x, false));
    subject.push(x = new Intersection(p1, segment, null, false));
    clip.push(x.o = new Intersection(p1, null, x, true));
  });

  if (!subject.length) return;

  clip.sort(compareIntersection);
  link(subject);
  link(clip);

  for (i = 0, n = clip.length; i < n; ++i) {
    clip[i].e = startInside = !startInside;
  }

  var start = subject[0],
      points,
      point;

  while (1) {
    // Find first unvisited intersection.
    var current = start,
        isSubject = true;
    while (current.v) if ((current = current.n) === start) return;
    points = current.z;
    stream.lineStart();
    do {
      current.v = current.o.v = true;
      if (current.e) {
        if (isSubject) {
          for (i = 0, n = points.length; i < n; ++i) stream.point((point = points[i])[0], point[1]);
        } else {
          interpolate(current.x, current.n.x, 1, stream);
        }
        current = current.n;
      } else {
        if (isSubject) {
          points = current.p.z;
          for (i = points.length - 1; i >= 0; --i) stream.point((point = points[i])[0], point[1]);
        } else {
          interpolate(current.x, current.p.x, -1, stream);
        }
        current = current.p;
      }
      current = current.o;
      points = current.z;
      isSubject = !isSubject;
    } while (!current.v);
    stream.lineEnd();
  }
}

function link(array) {
  if (!(n = array.length)) return;
  var n,
      i = 0,
      a = array[0],
      b;
  while (++i < n) {
    a.n = b = array[i];
    b.p = a;
    a = b;
  }
  a.n = b = array[0];
  b.p = a;
}

	import pointEqual from "../pointEqual.js";
	import {epsilon} from "../math.js";

	function Intersection(point, points, other, entry) {
	this.x = point;
	this.z = points;
	this.o = other; // another intersection
	this.e = entry; // is an entry?
	this.v = false; // visited
	this.n = this.p = null; // next & previous
	}

	// A generalized polygon clipping algorithm: given a polygon that has been cut
	// into its visible line segments, and rejoins the segments by interpolating
	// along the clip edge.
	export default function(segments, compareIntersection, startInside, interpolate, stream) {
	var subject = [],
	clip = [],
	i,
	n;

	segments.forEach(function(segment) {
	if ((n = segment.length - 1) <= 0) return;
	var n, p0 = segment[0], p1 = segment[n], x;

	if (pointEqual(p0, p1)) {
	if (!p0[2] && !p1[2]) {
	stream.lineStart();
	for (i = 0; i < n; ++i) stream.point((p0 = segment[i])[0], p0[1]);
	stream.lineEnd();
	return;
	}
	// handle degenerate cases by moving the point
	p1[0] += 2 * epsilon;
	}

	subject.push(x = new Intersection(p0, segment, null, true));
	clip.push(x.o = new Intersection(p0, null, x, false));
	subject.push(x = new Intersection(p1, segment, null, false));
	clip.push(x.o = new Intersection(p1, null, x, true));
	});

	if (!subject.length) return;

	clip.sort(compareIntersection);
	link(subject);
	link(clip);

	for (i = 0, n = clip.length; i < n; ++i) {
	clip[i].e = startInside = !startInside;
	}

	var start = subject[0],
	points,
	point;

	while (1) {
	// Find first unvisited intersection.
	var current = start,
	isSubject = true;
	while (current.v) if ((current = current.n) === start) return;
	points = current.z;
	stream.lineStart();
	do {
	current.v = current.o.v = true;
	if (current.e) {
	if (isSubject) {
	for (i = 0, n = points.length; i < n; ++i) stream.point((point = points[i])[0], point[1]);
	} else {
	interpolate(current.x, current.n.x, 1, stream);
	}
	current = current.n;
	} else {
	if (isSubject) {
	points = current.p.z;
	for (i = points.length - 1; i >= 0; --i) stream.point((point = points[i])[0], point[1]);
	} else {
	interpolate(current.x, current.p.x, -1, stream);
	}
	current = current.p;
	}
	current = current.o;
	points = current.z;
	isSubject = !isSubject;
	} while (!current.v);
	stream.lineEnd();
	}
	}

	function link(array) {
	if (!(n = array.length)) return;
	var n,
	i = 0,
	a = array[0],
	b;
	while (++i < n) {
	a.n = b = array[i];
	b.p = a;
	a = b;
	}
	a.n = b = array[0];
	b.p = a;
	}