File name
Commit message
Commit date
File name
Commit message
Commit date
File name
Commit message
Commit date
File name
Commit message
Commit date
export function polygonClip(clip, subject) {
// Version 0.0.0. Copyright 2017 Mike Bostock.
// 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
// https://observablehq.com/@d3/polygonclip
var input,
closed = polygonClosed(subject),
i = -1,
n = clip.length - polygonClosed(clip),
j,
m,
a = clip[n - 1],
b,
c,
d,
intersection;
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)) {
intersection = polygonIntersect(c, d, a, b);
if (isFinite(intersection[0])) {
subject.push(intersection);
}
}
subject.push(d);
} else if (polygonInside(c, a, b)) {
intersection = polygonIntersect(c, d, a, b);
if (isFinite(intersection[0])) {
subject.push(intersection);
}
}
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.
// Return Infinity if cd and ab colinear
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]);
}