### Polygon Utility

A collection of functions that can be used to work with polygons.
A polygon is defined by an array of vertices [[x0,y0], [x1,y1], [x2,y2], [x3,y3],...].

#utility #polygons

```// Polygon Utility. Created by Reinder Nijhoff 2022 - @reindernijhoff
//
// https://turtletoy.net/turtle/108305d431
//

let seed = 1; // min=1, max=100, step=1
const drawMode = 0; // min=0, max=1, step=1 (Circles, Polygons)

Canvas.setpenopacity(drawMode == 1 ? 1 : .3);

const turtle = new Turtle();
const ps = [];

// create random polygons
for (let i=0; i<9; i++) {
const w = 50 + 50 * random(), h = 50 + 50 * random(), x = 200 * random() - 100, y = 200 * random() - 100;
// create random polygon p
let p = [[x-w, y-h], [x-w, y+h], [x+w, y+h], [x+w, y-h]];
// split edges. After the split, all edges will have a lenth of ~ 2
p = pSplitEdges(p, 2);
// transform the polygon by adding sin(y) to the x-coordinate of all vertices
p = pTransform(p, c => [c[0] + Math.sin(c[1]*.1)*2, c[1]]);
// smooth polygon
p = pSmooth(p, 50*(random()**2) | 0 + 1);

if (drawMode == 1) {
pDraw(p, turtle);
}

ps.push(p);
}

function walk(i) {
if (drawMode == 1) {
return false;
}

// create a random point
const [x,y] = [Math.random()*200-100, Math.random()*200-100];

let dist = 1000;
let inside = 0;

ps.forEach(p => {
// find minimal distance from point to nearest polygon
dist = Math.min(dist, pDistance(p, [x,y]));

// check if point is inside polygon
if (pPointInPolygon(p, [x,y])) {
inside++;
}
});

// draw a circle with a radius equal to the nearest distance to a polygon
if (Math.random() > 0.5 * Math.sqrt(dist / 25) + (inside % 2 ? .5 : 0)) {
turtle.jump(x, y-dist);
turtle.circle(dist);
}

return i < 20000;
}

function random() {
let r = 1103515245 * (((seed+=12345) >> 1) ^ (seed));
r = 1103515245 * (r ^ (r >> 3));
r = r ^ (r >> 16);
const mod = 1 << 20;
return (r % mod) / mod;
}

////////////////////////////////////////////////////////////////
// Polygon Utility code
// https://turtletoy.net/turtle/108305d431
//
// A collection of functions that can be used to work with polygons.
// A polygon is defined by an array of vertices [v0, v1, v2, v3, ...].
//
////////////////////////////////////////////////////////////////

// draw a polygon p using turtle t
function pDraw(p, t) {
t.jump(p[p.length-1]);
p.forEach(c => t.goto(c));
}

// smooth a polygon by averaging all vertices with its neighbors. Repeat r times.
function pSmooth(p, r=1) {
let smooth = [];

for(;r;r--) {
smooth = [];
for (let i=0; i<p.length; i++) {
const pm = p[(i-1+p.length) % p.length];
const p0 = p[(i+0) % p.length];
const pp = p[(i+1) % p.length];

smooth.push(lrp2(lrp2(pm, pp, .5), p0, 1/3));
}
p = [...smooth];
}
return smooth;
}

// split all edges of polygon in segments with length ~ d
function pSplitEdges(p, d = 2) {
const sub = [];

for (let i=0; i<p.length; i++) {
const p0 = p[(i+0) % p.length];
const p1 = p[(i+1) % p.length];
const l = Math.ceil(dist2(p0, p1)/d);

for (let j=0; j<l; j++) {
sub.push(lrp2(p0, p1, j/l));
}
}

return sub;
}

// expand polygon p with distance d
function pExpand(p, d = 1) {
const lines = [];
const scaled = [];

for (let i=0; i<p.length; i++) {
const i0 = (i+0) % p.length;
const i1 = (i+1) % p.length;

const p0 = p[i0];
const p1 = p[i1];

let   n = nrm2(sub2(p1, p0));
n = [-n[1], n[0]];

lines.push([...n, -dot2(n, sub2(p0, scl2(n, -d)))]);
}

// find intersection points

for (let i=0; i<lines.length; i++) {
const i0 = (i+0) % lines.length;
const i1 = (i+1) % lines.length;

const pp = cross3(lines[i0], lines[i1]);
scaled[i] = Math.abs(pp[2]) < 0.0001 ? add2(p[i], scl2(lines[i], d)) : scl2(pp, 1/pp[2]);
}

return scaled;
}

// calculate bouding box (aabb) of p
function pAABB(p) {
let min = [...p[0]], max = [...p[0]];
p.forEach(c => {
min = [ Math.min(min[0],c[0]), Math.min(min[1],c[1]) ];
max = [ Math.max(max[0],c[0]), Math.max(max[1],c[1]) ];
});
return [min, max];
}

// point in aabb ?
function pointInAABB(p, aabb) {
const [min, max] = aabb;
return min[0] <= p[0] && max[0] >= p[0] && min[1] <= p[1] && max[1] >= p[1];
}

// check if point is inside polygon p
function pPointInPolygon(p, point, aabb = undefined) {
if (aabb && !pointInAABB(point, aabb || pAABB(p))) return false;

let int = 0; // find number of i ntersection points from p to far away
for (let i = 0, l = p.length; i < l; i++) {
if (segmentIntersect(point, [0.1, -1000], p[i], p[(i + 1) % l])) {
int++;
}
}
return int & 1; // if even your outside
}

// check if sphere ([x,y,radius]) is inside polygon p
function pSphereInPolygon(p, sphere, aabb = undefined) {
if (!pPointInPolygon(p, sphere, aabb || pAABB(p))) return false;
return pDistance(p, sphere) > sphere[2];
}

// find distance from point to polygon p
function pDistance(p, point) {
let dist = 100000;
for (let i=0; i<p.length; i++) {
const a = p[i], b = p[(i+1) % p.length];
const ba = sub2(b, a);
const pa = sub2(point, a);
const h = Math.max(0, Math.min(1, dot2(pa,ba)/dot2(ba,ba)));
dist = Math.min(dist, dist2(pa, scl2(ba, h)));
}
return dist;
}

// transform vertices of polygon p by function t
function pTransform(p, t) {
const ret = [];
for (let i=0; i<p.length; i++) {
ret.push(t(p[i]));
}
return ret;
}

//port of http://paulbourke.net/geometry/pointlineplane/Helpers.cs
function segmentIntersect(l1p1, l1p2, l2p1, l2p2) {
const d   = (l2p2[1] - l2p1[1]) * (l1p2[0] - l1p1[0]) - (l2p2[0] - l2p1[0]) * (l1p2[1] - l1p1[1]);
if (d === 0) return false;
const n_a = (l2p2[0] - l2p1[0]) * (l1p1[1] - l2p1[1]) - (l2p2[1] - l2p1[1]) * (l1p1[0] - l2p1[0]);
const n_b = (l1p2[0] - l1p1[0]) * (l1p1[1] - l2p1[1]) - (l1p2[1] - l1p1[1]) * (l1p1[0] - l2p1[0]);
const ua = n_a / d;
const ub = n_b / d;
if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) {
return [l1p1[0] + ua * (l1p2[0] - l1p1[0]), l1p1[1] + ua * (l1p2[1] - l1p1[1])];
}
return false;
}

//
// math functions
//
function scl2(a,b)   { return [a[0]*b, a[1]*b]; }
function add2(a,b)   { return [a[0]+b[0], a[1]+b[1]]; }
function sub2(a,b)   { return [a[0]-b[0], a[1]-b[1]]; }
function dot2(a,b)   { return a[0]*b[0] + a[1]*b[1]; }
function cross2(a,b) { return a[0]*b[1] - a[1]*b[0]; }
function len2(a)     { return Math.sqrt(a[0]**2 + a[1]**2); }
function dist2(a, b) { return len2(sub2(a,b)); }
function nrm2(a)     { return scl2(a, 1/len2(a)); }
function lrp2(b,a,f) { return f = Math.max(0, Math.min(1, f)), [a[0]*f+b[0]*(1-f), a[1]*f+b[1]*(1-f)]; }

function cross3(a, b) { return [a[1]*b[2]-a[2]*b[1], a[2]*b[0]-a[0]*b[2], a[0]*b[1]-a[1]*b[0]]; }
```