Upload 6270 files

4083225 verified 6 months ago

5.05 kB

import {abs, epsilon} from "../math.js";
import clipBuffer from "./buffer.js";
import clipLine from "./line.js";
import clipRejoin from "./rejoin.js";
import {merge} from "d3-array";

var clipMax = 1e9, clipMin = -clipMax;

// TODO Use d3-polygon’s polygonContains here for the ring check?
// TODO Eliminate duplicate buffering in clipBuffer and polygon.push?

export default function clipRectangle(x0, y0, x1, y1) {

  function visible(x, y) {
    return x0 <= x && x <= x1 && y0 <= y && y <= y1;
  }

  function interpolate(from, to, direction, stream) {
    var a = 0, a1 = 0;
    if (from == null
        || (a = corner(from, direction)) !== (a1 = corner(to, direction))
        || comparePoint(from, to) < 0 ^ direction > 0) {
      do stream.point(a === 0 || a === 3 ? x0 : x1, a > 1 ? y1 : y0);
      while ((a = (a + direction + 4) % 4) !== a1);
    } else {
      stream.point(to[0], to[1]);
    }
  }

  function corner(p, direction) {
    return abs(p[0] - x0) < epsilon ? direction > 0 ? 0 : 3
        : abs(p[0] - x1) < epsilon ? direction > 0 ? 2 : 1
        : abs(p[1] - y0) < epsilon ? direction > 0 ? 1 : 0
        : direction > 0 ? 3 : 2; // abs(p[1] - y1) < epsilon
  }

  function compareIntersection(a, b) {
    return comparePoint(a.x, b.x);
  }

  function comparePoint(a, b) {
    var ca = corner(a, 1),
        cb = corner(b, 1);
    return ca !== cb ? ca - cb
        : ca === 0 ? b[1] - a[1]
        : ca === 1 ? a[0] - b[0]
        : ca === 2 ? a[1] - b[1]
        : b[0] - a[0];
  }

  return function(stream) {
    var activeStream = stream,
        bufferStream = clipBuffer(),
        segments,
        polygon,
        ring,
        x__, y__, v__, // first point
        x_, y_, v_, // previous point
        first,
        clean;

    var clipStream = {
      point: point,
      lineStart: lineStart,
      lineEnd: lineEnd,
      polygonStart: polygonStart,
      polygonEnd: polygonEnd
    };

    function point(x, y) {
      if (visible(x, y)) activeStream.point(x, y);
    }

    function polygonInside() {
      var winding = 0;

      for (var i = 0, n = polygon.length; i < n; ++i) {
        for (var ring = polygon[i], j = 1, m = ring.length, point = ring[0], a0, a1, b0 = point[0], b1 = point[1]; j < m; ++j) {
          a0 = b0, a1 = b1, point = ring[j], b0 = point[0], b1 = point[1];
          if (a1 <= y1) { if (b1 > y1 && (b0 - a0) * (y1 - a1) > (b1 - a1) * (x0 - a0)) ++winding; }
          else { if (b1 <= y1 && (b0 - a0) * (y1 - a1) < (b1 - a1) * (x0 - a0)) --winding; }
        }
      }

      return winding;
    }

    // Buffer geometry within a polygon and then clip it en masse.
    function polygonStart() {
      activeStream = bufferStream, segments = [], polygon = [], clean = true;
    }

    function polygonEnd() {
      var startInside = polygonInside(),
          cleanInside = clean && startInside,
          visible = (segments = merge(segments)).length;
      if (cleanInside || visible) {
        stream.polygonStart();
        if (cleanInside) {
          stream.lineStart();
          interpolate(null, null, 1, stream);
          stream.lineEnd();
        }
        if (visible) {
          clipRejoin(segments, compareIntersection, startInside, interpolate, stream);
        }
        stream.polygonEnd();
      }
      activeStream = stream, segments = polygon = ring = null;
    }

    function lineStart() {
      clipStream.point = linePoint;
      if (polygon) polygon.push(ring = []);
      first = true;
      v_ = false;
      x_ = y_ = NaN;
    }

    // TODO rather than special-case polygons, simply handle them separately.
    // Ideally, coincident intersection points should be jittered to avoid
    // clipping issues.
    function lineEnd() {
      if (segments) {
        linePoint(x__, y__);
        if (v__ && v_) bufferStream.rejoin();
        segments.push(bufferStream.result());
      }
      clipStream.point = point;
      if (v_) activeStream.lineEnd();
    }

    function linePoint(x, y) {
      var v = visible(x, y);
      if (polygon) ring.push([x, y]);
      if (first) {
        x__ = x, y__ = y, v__ = v;
        first = false;
        if (v) {
          activeStream.lineStart();
          activeStream.point(x, y);
        }
      } else {
        if (v && v_) activeStream.point(x, y);
        else {
          var a = [x_ = Math.max(clipMin, Math.min(clipMax, x_)), y_ = Math.max(clipMin, Math.min(clipMax, y_))],
              b = [x = Math.max(clipMin, Math.min(clipMax, x)), y = Math.max(clipMin, Math.min(clipMax, y))];
          if (clipLine(a, b, x0, y0, x1, y1)) {
            if (!v_) {
              activeStream.lineStart();
              activeStream.point(a[0], a[1]);
            }
            activeStream.point(b[0], b[1]);
            if (!v) activeStream.lineEnd();
            clean = false;
          } else if (v) {
            activeStream.lineStart();
            activeStream.point(x, y);
            clean = false;
          }
        }
      }
      x_ = x, y_ = y, v_ = v;
    }

    return clipStream;
  };
}

	import {abs, epsilon} from "../math.js";
	import clipBuffer from "./buffer.js";
	import clipLine from "./line.js";
	import clipRejoin from "./rejoin.js";
	import {merge} from "d3-array";

	var clipMax = 1e9, clipMin = -clipMax;

	// TODO Use d3-polygon’s polygonContains here for the ring check?
	// TODO Eliminate duplicate buffering in clipBuffer and polygon.push?

	export default function clipRectangle(x0, y0, x1, y1) {

	function visible(x, y) {
	return x0 <= x && x <= x1 && y0 <= y && y <= y1;
	}

	function interpolate(from, to, direction, stream) {
	var a = 0, a1 = 0;
	if (from == null
	\|\| (a = corner(from, direction)) !== (a1 = corner(to, direction))
	\|\| comparePoint(from, to) < 0 ^ direction > 0) {
	do stream.point(a === 0 \|\| a === 3 ? x0 : x1, a > 1 ? y1 : y0);
	while ((a = (a + direction + 4) % 4) !== a1);
	} else {
	stream.point(to[0], to[1]);
	}
	}

	function corner(p, direction) {
	return abs(p[0] - x0) < epsilon ? direction > 0 ? 0 : 3
	: abs(p[0] - x1) < epsilon ? direction > 0 ? 2 : 1
	: abs(p[1] - y0) < epsilon ? direction > 0 ? 1 : 0
	: direction > 0 ? 3 : 2; // abs(p[1] - y1) < epsilon
	}

	function compareIntersection(a, b) {
	return comparePoint(a.x, b.x);
	}

	function comparePoint(a, b) {
	var ca = corner(a, 1),
	cb = corner(b, 1);
	return ca !== cb ? ca - cb
	: ca === 0 ? b[1] - a[1]
	: ca === 1 ? a[0] - b[0]
	: ca === 2 ? a[1] - b[1]
	: b[0] - a[0];
	}

	return function(stream) {
	var activeStream = stream,
	bufferStream = clipBuffer(),
	segments,
	polygon,
	ring,
	x__, y__, v__, // first point
	x_, y_, v_, // previous point
	first,
	clean;

	var clipStream = {
	point: point,
	lineStart: lineStart,
	lineEnd: lineEnd,
	polygonStart: polygonStart,
	polygonEnd: polygonEnd
	};

	function point(x, y) {
	if (visible(x, y)) activeStream.point(x, y);
	}

	function polygonInside() {
	var winding = 0;

	for (var i = 0, n = polygon.length; i < n; ++i) {
	for (var ring = polygon[i], j = 1, m = ring.length, point = ring[0], a0, a1, b0 = point[0], b1 = point[1]; j < m; ++j) {
	a0 = b0, a1 = b1, point = ring[j], b0 = point[0], b1 = point[1];
	if (a1 <= y1) { if (b1 > y1 && (b0 - a0) * (y1 - a1) > (b1 - a1) * (x0 - a0)) ++winding; }
	else { if (b1 <= y1 && (b0 - a0) * (y1 - a1) < (b1 - a1) * (x0 - a0)) --winding; }
	}
	}

	return winding;
	}

	// Buffer geometry within a polygon and then clip it en masse.
	function polygonStart() {
	activeStream = bufferStream, segments = [], polygon = [], clean = true;
	}

	function polygonEnd() {
	var startInside = polygonInside(),
	cleanInside = clean && startInside,
	visible = (segments = merge(segments)).length;
	if (cleanInside \|\| visible) {
	stream.polygonStart();
	if (cleanInside) {
	stream.lineStart();
	interpolate(null, null, 1, stream);
	stream.lineEnd();
	}
	if (visible) {
	clipRejoin(segments, compareIntersection, startInside, interpolate, stream);
	}
	stream.polygonEnd();
	}
	activeStream = stream, segments = polygon = ring = null;
	}

	function lineStart() {
	clipStream.point = linePoint;
	if (polygon) polygon.push(ring = []);
	first = true;
	v_ = false;
	x_ = y_ = NaN;
	}

	// TODO rather than special-case polygons, simply handle them separately.
	// Ideally, coincident intersection points should be jittered to avoid
	// clipping issues.
	function lineEnd() {
	if (segments) {
	linePoint(x__, y__);
	if (v__ && v_) bufferStream.rejoin();
	segments.push(bufferStream.result());
	}
	clipStream.point = point;
	if (v_) activeStream.lineEnd();
	}

	function linePoint(x, y) {
	var v = visible(x, y);
	if (polygon) ring.push([x, y]);
	if (first) {
	x__ = x, y__ = y, v__ = v;
	first = false;
	if (v) {
	activeStream.lineStart();
	activeStream.point(x, y);
	}
	} else {
	if (v && v_) activeStream.point(x, y);
	else {
	var a = [x_ = Math.max(clipMin, Math.min(clipMax, x_)), y_ = Math.max(clipMin, Math.min(clipMax, y_))],
	b = [x = Math.max(clipMin, Math.min(clipMax, x)), y = Math.max(clipMin, Math.min(clipMax, y))];
	if (clipLine(a, b, x0, y0, x1, y1)) {
	if (!v_) {
	activeStream.lineStart();
	activeStream.point(a[0], a[1]);
	}
	activeStream.point(b[0], b[1]);
	if (!v) activeStream.lineEnd();
	clean = false;
	} else if (v) {
	activeStream.lineStart();
	activeStream.point(x, y);
	clean = false;
	}
	}
	}
	x_ = x, y_ = y, v_ = v;
	}

	return clipStream;
	};
	}