Skip to content

Instantly share code, notes, and snippets.

@mbostock
Created January 23, 2017 18:25
Show Gist options
  • Save mbostock/ece50c027bdf8cc20003a17d93e4f60e to your computer and use it in GitHub Desktop.
Save mbostock/ece50c027bdf8cc20003a17d93e4f60e to your computer and use it in GitHub Desktop.
Polygon Clipping III
license: gpl-3.0
height: 600

If your clip polygon is more complicated than an axis-aligned rectangle, projection.clipExtent as shown previously won’t be sufficient. This example implements Sutherland–Hodgman clipping, which works for any convex clip polygon. Note, however, that this implementation only clips exterior polygon rings; you’ll need to do some additional work to handle any holes.

// 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>
<svg width="960" height="600"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://d3js.org/topojson.v2.min.js"></script>
<script src="d3-polygon-clip.js"></script>
<script>
var clip = [[100, 400], [480, 550], [860, 400], [860, 100], [480, 50], [100, 100]];
var svg = d3.select("svg");
svg.append("path")
.attr("fill", "blue")
.attr("d", "M" + clip.join("L") + "Z");
d3.json("https://d3js.org/us-10m.v1.json", function(error, us) {
if (error) throw error;
var nation = topojson.feature(us, us.objects.nation),
rings = nation.features[0].geometry.coordinates.map(function(rings) { return rings[0]; });
svg.append("g")
.attr("fill", "red")
.selectAll("path")
.data(rings)
.enter().append("path")
.attr("d", function(d) { return "M" + d.join("L"); })
svg.append("g")
.attr("fill", "black")
.attr("stroke", "white")
.selectAll("path")
.data(rings)
.enter().append("path")
.attr("d", function(d) { return "M" + d3.polygonClip(clip, d).join("L"); })
});
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment