Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.