bmershon/.block

## .block
license: gpl-3.0
height: 600

## README.md

      
    Raw
  

              README.md
            
          
    Testing Mike Bostock's Sutherland-Hodgman clipping implementation.
The scissors implementation of a scissors-congruence between two polygons of equal area suffers from numerical instability in the clipping stage of the pipeline. The current implementation of clipping simply clips two collections of polygons against one another.
This example demonstrates areas where new vertices are created while highlighting areas where floating-point precision issues may arise.
Note that the clipping polygon must be convex for Sutherland-Hodgman to work correctly. Move the control points by dragging them.

  
## d3-polygon-clip.js
// Version 0.0.0. Copyright 2017 Mike Bostock.
(function (global, factory) {
  typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
  typeof define === 'function' && define.amd ? define(['exports'], factory) :
  (factory((global.d3 = global.d3 || {})));
}(this, function (exports) { 'use strict';

  // Clips the specified subject polygon to the specified clip polygon;
  // requires the clip polygon to be counterclockwise and convex.
  // https://en.wikipedia.org/wiki/Sutherland–Hodgman_algorithm
  exports.polygonClip = function(clip, subject) {
    var input,
        closed = polygonClosed(subject),
        i = -1,
        n = clip.length - polygonClosed(clip),
        j,
        m,
        a = clip[n - 1],
        b,
        c,
        d;

    while (++i < n) {
      input = subject.slice();
      subject.length = 0;
      b = clip[i];
      c = input[(m = input.length - closed) - 1];
      j = -1;
      while (++j < m) {
        d = input[j];
        if (polygonInside(d, a, b)) {
          if (!polygonInside(c, a, b)) {
            subject.push(polygonIntersect(c, d, a, b));
          }
          subject.push(d);
        } else if (polygonInside(c, a, b)) {
          subject.push(polygonIntersect(c, d, a, b));
        }
        c = d;
      }
      if (closed) subject.push(subject[0]);
      a = b;
    }

    return subject;
  };

  function polygonInside(p, a, b) {
    return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
  }

  // Intersect two infinite lines cd and ab.
  function polygonIntersect(c, d, a, b) {
    var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3,
        y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3,
        ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
    return [x1 + ua * x21, y1 + ua * y21];
  }

  // Returns true if the polygon is closed.
  function polygonClosed(coordinates) {
    var a = coordinates[0],
        b = coordinates[coordinates.length - 1];
    return !(a[0] - b[0] || a[1] - b[1]);
  }

  Object.defineProperty(exports, '__esModule', {value: true});
}));

## index.html
<!DOCTYPE html>
<style>

circle {
  cursor: move;
  fill: #fff;
  stroke: #000;
  stroke-width: 1px;
}

circle.active {
  stroke: #000;
  stroke-width: 2px;
}

path.clip {
  fill: rgba(0, 0, 0, 0.3);
  stroke-dasharray: 5, 5;
  stroke: #000;
  stroke-width: 2px;
}

path.subject {
  fill: #8fbbda;
  stroke: #000;
  stroke-width: 2px;
}

path.clipped {
  fill: #000;
  stroke: #000;
  stroke-width: 2px;
}

</style>
<svg width="960" height="600"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="d3-polygon-clip.js"></script>
<script>

var svg = d3.select("svg"),
    width = svg.attr("width"),
    height = svg.attr("height");

// Counter-clockwise orientation.
var clip = [[width / 2, height / 5],
            [width / 5, 3 * height / 5],
            [3 * width / 5, 3 * height / 5]];

// Counter-clockwise orientation.
var subject = [[100, 400], [480, 550], [700, 400], [860, 100], [200, 250]];

// d3.polygonClip modifies the input subject. Clone it first.
var clipped = d3.polygonClip(clip, polygonClone(subject));

var subjectPolygon = svg.append("path")
    .attr("class", "subject")
    .datum(subject);

var clippedPolygon = svg.append("path")
    .attr("class", "clipped")
    .datum(clipped);

var clipPolygon = svg.append("path")
    .datum(clip)
    .attr("class", "clip");

// Control points for the clip polygon.
var circle = svg.selectAll("circle")
  .data(clip);

var origin = [0, 0];

circle.enter()
  .append("circle")
    .attr("r", 9)
    .attr("cx", function(d) { return d[0]; })
    .attr("cy", function(d) { return d[1]; })
    .call(d3.drag()
        .on("start", dragstarted)
        .on("drag", dragged)
        .on("end", dragended));

update();

// Redraw polygons in response to control point movement.
function update() {
  // Ensure clip polygon has counter-clockwise orientation.
  if (!ccw(clip)) clip.reverse();

  clipPolygon.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
  subjectPolygon.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
  clippedPolygon.datum(d3.polygonClip(clip, polygonClone(subject)));
  clippedPolygon.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
}

function dragstarted(d) {
  d3.select(this).classed("active", true);
  update();
}

function dragged(d) {
  d3.select(this)
      .attr("cx", d[0] = d3.event.x)
      .attr("cy", d[1] = d3.event.y);
  update();
}

function dragended(d, i) {
  d3.select(this).classed("active", false);
  update();
}

function polygonClone(polygon) {
  var cloned = [],
      i,
      n;

  for (i = 0, n = polygon.length; i < n; i++) {
    cloned.push([polygon[i][0], polygon[i][1]]);
  }

  return cloned;
}

// Returns true of the given polygon has counter-clockwise orientation.
function ccw(polygon) {
  function polygonInside(p, a, b) {
    // Use cross product to determine orientation.
    return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
  }

  return polygonInside(d3.polygonCentroid(polygon), polygon[0], polygon[1]);
}

</script>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	// Version 0.0.0. Copyright 2017 Mike Bostock.
	(function (global, factory) {
	typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
	typeof define === 'function' && define.amd ? define(['exports'], factory) :
	(factory((global.d3 = global.d3 \|\| {})));
	}(this, function (exports) { 'use strict';

	// Clips the specified subject polygon to the specified clip polygon;
	// requires the clip polygon to be counterclockwise and convex.
	// https://en.wikipedia.org/wiki/Sutherland–Hodgman_algorithm
	exports.polygonClip = function(clip, subject) {
	var input,
	closed = polygonClosed(subject),
	i = -1,
	n = clip.length - polygonClosed(clip),
	j,
	m,
	a = clip[n - 1],
	b,
	c,
	d;

	while (++i < n) {
	input = subject.slice();
	subject.length = 0;
	b = clip[i];
	c = input[(m = input.length - closed) - 1];
	j = -1;
	while (++j < m) {
	d = input[j];
	if (polygonInside(d, a, b)) {
	if (!polygonInside(c, a, b)) {
	subject.push(polygonIntersect(c, d, a, b));
	}
	subject.push(d);
	} else if (polygonInside(c, a, b)) {
	subject.push(polygonIntersect(c, d, a, b));
	}
	c = d;
	}
	if (closed) subject.push(subject[0]);
	a = b;
	}

	return subject;
	};

	function polygonInside(p, a, b) {
	return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
	}

	// Intersect two infinite lines cd and ab.
	function polygonIntersect(c, d, a, b) {
	var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3,
	y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3,
	ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
	return [x1 + ua * x21, y1 + ua * y21];
	}

	// Returns true if the polygon is closed.
	function polygonClosed(coordinates) {
	var a = coordinates[0],
	b = coordinates[coordinates.length - 1];
	return !(a[0] - b[0] \|\| a[1] - b[1]);
	}

	Object.defineProperty(exports, '__esModule', {value: true});
	}));
	<!DOCTYPE html>
	<style>

	circle {
	cursor: move;
	fill: #fff;
	stroke: #000;
	stroke-width: 1px;
	}

	circle.active {
	stroke: #000;
	stroke-width: 2px;
	}

	path.clip {
	fill: rgba(0, 0, 0, 0.3);
	stroke-dasharray: 5, 5;
	stroke: #000;
	stroke-width: 2px;
	}

	path.subject {
	fill: #8fbbda;
	stroke: #000;
	stroke-width: 2px;
	}

	path.clipped {
	fill: #000;
	stroke: #000;
	stroke-width: 2px;
	}

	</style>
	<svg width="960" height="600"></svg>
	<script src="https://d3js.org/d3.v4.min.js"></script>
	<script src="d3-polygon-clip.js"></script>
	<script>

	var svg = d3.select("svg"),
	width = svg.attr("width"),
	height = svg.attr("height");

	// Counter-clockwise orientation.
	var clip = [[width / 2, height / 5],
	[width / 5, 3 * height / 5],
	[3 * width / 5, 3 * height / 5]];

	// Counter-clockwise orientation.
	var subject = [[100, 400], [480, 550], [700, 400], [860, 100], [200, 250]];

	// d3.polygonClip modifies the input subject. Clone it first.
	var clipped = d3.polygonClip(clip, polygonClone(subject));

	var subjectPolygon = svg.append("path")
	.attr("class", "subject")
	.datum(subject);

	var clippedPolygon = svg.append("path")
	.attr("class", "clipped")
	.datum(clipped);

	var clipPolygon = svg.append("path")
	.datum(clip)
	.attr("class", "clip");

	// Control points for the clip polygon.
	var circle = svg.selectAll("circle")
	.data(clip);

	var origin = [0, 0];

	circle.enter()
	.append("circle")
	.attr("r", 9)
	.attr("cx", function(d) { return d[0]; })
	.attr("cy", function(d) { return d[1]; })
	.call(d3.drag()
	.on("start", dragstarted)
	.on("drag", dragged)
	.on("end", dragended));

	update();

	// Redraw polygons in response to control point movement.
	function update() {
	// Ensure clip polygon has counter-clockwise orientation.
	if (!ccw(clip)) clip.reverse();

	clipPolygon.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
	subjectPolygon.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
	clippedPolygon.datum(d3.polygonClip(clip, polygonClone(subject)));
	clippedPolygon.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
	}

	function dragstarted(d) {
	d3.select(this).classed("active", true);
	update();
	}

	function dragged(d) {
	d3.select(this)
	.attr("cx", d[0] = d3.event.x)
	.attr("cy", d[1] = d3.event.y);
	update();
	}

	function dragended(d, i) {
	d3.select(this).classed("active", false);
	update();
	}

	function polygonClone(polygon) {
	var cloned = [],
	i,
	n;

	for (i = 0, n = polygon.length; i < n; i++) {
	cloned.push([polygon[i][0], polygon[i][1]]);
	}

	return cloned;
	}

	// Returns true of the given polygon has counter-clockwise orientation.
	function ccw(polygon) {
	function polygonInside(p, a, b) {
	// Use cross product to determine orientation.
	return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
	}

	return polygonInside(d3.polygonCentroid(polygon), polygon[0], polygon[1]);
	}

	</script>