Voronoi study 🧽
My take on Voronoi diagrams using Delaunay triangulation.
(A look into debugging this thing: Voronoi study 🧽 (variation) and Voronoi study 🧽 (variation))
Log in to post a comment.
const seed = 10000; //min=10000 max=99999 step=1
const n = 200; //min=4 max=600 step=1
const padding = 0; //min=0 max=90 step=1
const mirrorEdges = 1; //min=0 max=1 step=1 (No, Yes)
const dSources = 0; //min=0 max=1 step=1 (No, Yes)
const dVoronoiLines = 1; //min=0 max=1 step=1 (No, Yes)
const drawMode = 1; //min=0 max=1 step=1 (dDelaunayX, dPolygonX)
const dDelaunayPoints = 0; //min=0 max=1 step=1 (No, Yes)
const dDelaunayCircles = 0; //min=0 max=1 step=1 (No, Yes)
const dDelaunayTriangles = 0; //min=0 max=1 step=1 (No, Yes)
const dPolygonShrink = .9; //min=0 max=1.5 step=.1
const dPolygonArtBorder = 5; //min=0 max=30 step=1
const dPolygonArtShape = 2; //min=2 max=10 step=1 (Circle, Triangle, Square, Pentagon, Hexagon, Heptagon, Octagon, Nonagon, Decagon)
const dPolygonHatching = 1; //min=0 max=5 step=1 (None, Random, Circular gradient, Circular gradient inverted, Gradient, Inverted gradient)
const dPolygonHatchDir = 0; //min=0 max=2 step=1 (Random, Centralized, Centralized othogonal)
const dPolygonHatchMin = .31; //min=.01 max=1.6 step=.05
const dPolygonHatchMax = .51; //min=.01 max=1.6 step=.05
const dPolygonBackground = 0; //min=0 max=2 step=1 (None, Gradient up, Gradient down)
const debug = false;
const dPolygonHatchMaxc = Math.max(dPolygonHatchMin, dPolygonHatchMax);
// You can find the Turtle API reference here: https://turtletoy.net/syntax
Canvas.setpenopacity(1);
// Global code will be evaluated once.
const turtle = new Turtle();
const polygons = new Polygons();
function normalize2(a) { const length = len2(a); return scale2(a,length<0.0001?1:1/length); }
function len2(a) { return Math.sqrt(lensq2(a)); }
function lensq2(a) { return dot2(a,a); }
function rot2(a) { return [Math.cos(a), -Math.sin(a), Math.sin(a), Math.cos(a)]; }
function trans2(m, a) { return [m[0]*a[0]+m[2]*a[1], m[1]*a[0]+m[3]*a[1]]; }
function scale2(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 dist2(a,b) { return Math.hypot(...sub2(a,b)); }
function lerp2(a,b,t) { return [a[0]*(1-t)+b[0]*t,a[1]*(1-t)+b[1]*t]; }
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 mulf2(v, f) { return scale2(v,f); }
function multiply2(a2x2, a) { return [(a[0]*a2x2[0])+(a[1]*a2x2[1]),(a[0]*a2x2[2])+(a[1]*a2x2[3])]; }
function segment_intersect2(a,b,d,c, inclusive = true) {
const e=(c[1]-d[1])*(b[0]-a[0])-(c[0]-d[0])*(b[1]-a[1]);
if(0==e)return false;
c=((c[0]-d[0])*(a[1]-d[1])-(c[1]-d[1])*(a[0]-d[0]))/e;
d=((b[0]-a[0])*(a[1]-d[1])-(b[1]-a[1])*(a[0]-d[0]))/e;
const t = inclusive? 0<=c&&1>=c&&0<=d&&1>=d: 0<c&&1>c&&0<d&&1>d;
return t?[a[0]+c*(b[0]-a[0]),a[1]+c*(b[1]-a[1])]:false;
}
function eq2(a,b) { return a[0]==b[0]&&a[1]==b[1]; }
// Seedable random number generator by David Bau: http://davidbau.com/archives/2010/01/30/random_seeds_coded_hints_and_quintillions.html
!function(a,b,c,d,e,f,g,h,i){function j(a){var b,c=a.length,e=this,f=0,g=e.i=e.j=0,h=e.S=[];for(c||(a=[c++]);d>f;)h[f]=f++;for(f=0;d>f;f++)h[f]=h[g=s&g+a[f%c]+(b=h[f])],h[g]=b;(e.g=function(a){for(var b,c=0,f=e.i,g=e.j,h=e.S;a--;)b=h[f=s&f+1],c=c*d+h[s&(h[f]=h[g=s&g+b])+(h[g]=b)];return e.i=f,e.j=g,c})(d)}function k(a,b){var c,d=[],e=typeof a;if(b&&"object"==e)for(c in a)try{d.push(k(a[c],b-1))}catch(f){}return d.length?d:"string"==e?a:a+"\0"}function l(a,b){for(var c,d=a+"",e=0;e<d.length;)b[s&e]=s&(c^=19*b[s&e])+d.charCodeAt(e++);return n(b)}function m(c){try{return o?n(o.randomBytes(d)):(a.crypto.getRandomValues(c=new Uint8Array(d)),n(c))}catch(e){return[+new Date,a,(c=a.navigator)&&c.plugins,a.screen,n(b)]}}function n(a){return String.fromCharCode.apply(0,a)}var o,p=c.pow(d,e),q=c.pow(2,f),r=2*q,s=d-1,t=c["seed"+i]=function(a,f,g){var h=[];f=1==f?{entropy:!0}:f||{};var o=l(k(f.entropy?[a,n(b)]:null==a?m():a,3),h),s=new j(h);return l(n(s.S),b),(f.pass||g||function(a,b,d){return d?(c[i]=a,b):a})(function(){for(var a=s.g(e),b=p,c=0;q>a;)a=(a+c)*d,b*=d,c=s.g(1);for(;a>=r;)a/=2,b/=2,c>>>=1;return(a+c)/b},o,"global"in f?f.global:this==c)};if(l(c[i](),b),g&&g.exports){g.exports=t;try{o=require("crypto")}catch(u){}}else h&&h.amd&&h(function(){return t})}(this,[],Math,256,6,52,"object"==typeof module&&module,"function"==typeof define&&define,"random");
Math.seedrandom('anything here' + seed);
// Add a seed in seedrandom, then Math.random will use this seed
const randomPoint = () => [2*Math.random()*(100-padding)-(100-padding),2*Math.random()*(100-padding)-(100-padding)];
//We start with one randomly chosen point in our points list
const pts = [randomPoint()];
//While there are not yet a certain number of points chosen
while(pts.length < n) {
//add a point to the list
pts.push(
//using [length] candidate points
Array.apply(null,{length: 10})
//which are random points
.map(i => randomPoint())
//then add a distance to that candidate
.map(i => [i[0], i[1], pts.map(j => [j[0], j[1], dist2(i, j)])
//so that it is the smallest distance from the
//candidate to any of the already chosen points
.reduce((prev, current) => (current[2] < prev[2])? current: prev, [0,0,500])[2]
])
//then pick the candidate that has the largest minimum distance from the group of candidates
.reduce((prev, current) => (current[2] > prev[2])? current: prev, [0,0,0])
//and remove the distance before promoting the candidate
.filter((i, k) => k < 2)
);
}
/*
turtle.jump([0,-100]);
turtle.goto([0, 100]);
turtle.jump([-100, 0]);
turtle.goto([100, 0]);
*/
/////////----------------- TEST CASES ------------------////////
//two outside circles
//const pts = [[0, -20], [70, 0], [0, 20], [-60, 20], [0, 50]];
//one inside circle, outside hull
//const pts = [[0, -20], [70, 0], [-30, 50], [30, 50]];
//one inside circle outside another, outside hull
//const pts = [[0, -10], [50, 0], [0, 25], [-50, 50], [25, 34]];
//point inside triangle, once circle
//const pts = [[0, -20], [70, 0], [0, 20], [25, 0]];
//point inside triangle, two circles
//const pts = [[0, -20], [70, 0], [0, 20], [25, 0], [20, 10]];
//point on a non-shared edge
//const pts = [[0, 50], [50, 50], [0, -50], [0,0]];
//point on a non-shared edge, but in 'another' circle
//const pts = [[20, -70], [70, 0], [0, 0], [20, 30]];
//pts.push(add2(pts[0], scale2(sub2(pts[1], pts[0]), .8)));
//point on a shared edge
//const pts = [[20, -70], [70, 0], [0, 0], [20, 30], [30, 0]];
//point on a shared edge and in 'another' circle
//const pts = [[20, -70], [70, 0], [0, 0], [20, 30], [0, 20], [30, 0]];
/////////----------------- END TEST CASES ------------------////////
class DelaunayTriangulation {
constructor(pts) {
if(pts.length < 3) {
throw new Error('What u do?');
}
this.points = pts.filter((i, k) => k < 3);
this.log('init points 1, 2, 3', ...this.points);
this.circles = [];
this.convexHullEdges = [[0, 1], [1, 2], [0, 2]];
this.addCircle(0, 1, 2);
pts.filter((i, k) => k > 2).forEach(i => this.add(i));
}
log(...msg) {
if(debug) {
console.log(...msg);
}
}
addCircle(...idxs) {
this.circles.push(this.getCircle(...idxs));
return this.circles.length - 1;
}
getCircle(...idxs) {
if(idxs.length != 3) throw new Error('Expecting 3 arguments at getCircle()');
idxs.sort();
const cc = this.getSmallestCircumscribedCircleCenter(...idxs.map(i => this.points[i]));
const r = lensq2(sub2(cc, this.points[idxs[0]]));
return [cc, r, [...idxs]];
}
// https://en.wikipedia.org/wiki/Circumscribed_circle#Cartesian_coordinates_2
getSmallestCircumscribedCircleCenter(pt1, pt2, pt3) {
const D = 2 * (
(pt1[0] * (pt2[1] - pt3[1])) +
(pt2[0] * (pt3[1] - pt1[1])) +
(pt3[0] * (pt1[1] - pt2[1]))
);
return [(
((pt1[0]**2 + pt1[1]**2) * (pt2[1] - pt3[1])) +
((pt2[0]**2 + pt2[1]**2) * (pt3[1] - pt1[1])) +
((pt3[0]**2 + pt3[1]**2) * (pt1[1] - pt2[1]))
) / D,
(
((pt1[0]**2 + pt1[1]**2) * (pt3[0] - pt2[0])) +
((pt2[0]**2 + pt2[1]**2) * (pt1[0] - pt3[0])) +
((pt3[0]**2 + pt3[1]**2) * (pt2[0] - pt1[0]))
) / D
];
}
// https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle#2049593
isPointContainedInTriangle(trianglePointIndices, pt) {
const sign = (p1, p2, p3) => (p1[0]-p3[0]) * (p2[1]-p3[1]) - (p2[0]-p3[0]) * (p1[1]-p3[1]);
const d = trianglePointIndices.map(i => this.points[i]).map((p, idx, src) => sign(pt, p, src[(idx+1)%src.length]));
return !(d.reduce((p, c) => p || (c < 0), false) && d.reduce((p, c) => p || (c > 0), false));
}
drawTriangles(t) {
//const edges = this.circles.map((c, i) => [c[2][i], c[2][(i+1)%3]]);
this.circles.forEach(c => {
const edges = c[2].map((p, i) => [p, c[2][(i+1)%3]]).map(e => [e, this.edgeIsPartOfConvexHull(e)]);
edges.forEach(e => {
const pts = [this.points[e[0][0]], this.points[e[0][1]]];
t.jump(pts[0]); t.goto(pts[1]);
if(e[1]) {
[[1, 0], [0, 1], [-1, 0], [0, -1]].map(i => scale2(i, .2)).forEach(d => {
t.jump(add2(pts[0], d));
t.goto(add2(pts[1], d));
});
}
})
});
}
drawCircles(t) {
this.circles.forEach(c => {
t.jump(c[0][0], c[0][1] - Math.sqrt(c[1]));
t.circle(Math.sqrt(c[1]));
});
}
drawPoints(t) {
this.circles.forEach(c => {
drawPoint(t, c[0], .5);
});
}
edgeIsPartOfConvexHull(edge) {
edge = edge[0] < edge[1]? [edge[0], edge[1]]: [edge[1], edge[0]];//sort();
return this.convexHullEdges.filter(che => eq2(che, edge)).length > 0;
}
add(pt) {
const arrayIntersection = (array1, array2) => array1.filter(value => array2.includes(value));
const arrayDifference = (array1, array2) => array1.filter(value => !array2.includes(value)).concat(array2.filter(value => !array1.includes(value)));
const flip = (idx1, idx2) => {
const intersect = arrayIntersection(this.circles[idx1][2], this.circles[idx2][2])
const uniques = [
arrayDifference(this.circles[idx1][2], intersect)[0],
arrayDifference(this.circles[idx2][2], intersect)[0]
];
this.circles[idx1] = this.getCircle(intersect[0], ...uniques);
this.circles[idx2] = this.getCircle(intersect[1], ...uniques);
return this.edgeIsPartOfConvexHull(intersect);
}
//add the point to the list
this.points.push(pt);
let convexHullUpdateNeeded = false;
const inCircleIndices = this.circles.map((i, idx) => [idx, i]).filter(c => lensq2(sub2(c[1][0], pt)) <= c[1][1]).map(i => i[0]);
const inTriangleIndices = inCircleIndices.filter(c => this.isPointContainedInTriangle(this.circles[c][2], pt));
if(inTriangleIndices.length == 0) {
//the new point is outside of circles and by definition outside convex hull
// find convexhull edges that are not connecting to p that intersect pt-p
// and if there are, return false (exclude that point)
const connectToPoints = this.points.filter((p, pIdx) => this.convexHullEdges
.filter(che => che[0] != pIdx && che[1] != pIdx)
.filter(che => false !== segment_intersect2(pt, p, this.points[che[0]], this.points[che[1]])).length === 0
).map(i => this.points.indexOf(i));
//so because the new point is outside circles we can just add it to all convex hull edges where their points are all in the connectToPoints
//get the combinations (length 2) of all points to connect to internally sorted by index in this.points
const possibleEdges = connectToPoints.flatMap((i, idx) =>
connectToPoints.filter((ii, iidx) => iidx > idx).map(ii => [i, ii])
);
//get all convex hull edges associated with the points (valid combinations)
const hullEdges = this.convexHullEdges.filter(i => possibleEdges.filter(ii => eq2(ii, i)).length > 0);
//create new circles for every new triangle
hullEdges.forEach((he, idx) => {
this.addCircle(...he, this.points.length - 1);
});
convexHullUpdateNeeded = true;
} else {
//is the point on an edge?
const edge = [[0, 1], [1, 2], [0, 2]].map(i =>
[this.circles[inTriangleIndices[0]][2][i[0]], this.circles[inTriangleIndices[0]][2][i[1]]]
).filter(edge => len2(sub2(this.points[edge[0]], this.points[edge[1]]))
==
len2(sub2(this.points[edge[0]], this.points[this.points.length - 1])) +
len2(sub2(this.points[edge[1]], this.points[this.points.length - 1]))
);
const onEdge = edge.length == 0? false: (
edge[0][0] < edge[0][1]? [edge[0][0], edge[0][1]]: [edge[0][1], edge[0][0]]
);
if(onEdge === false) {
[[0, 1], [1, 2], [0, 2]].map(i =>
[this.circles[inTriangleIndices[0]][2][i[0]], this.circles[inTriangleIndices[0]][2][i[1]], this.points.length - 1]
).forEach((i, k) => {
k == 0? this.circles[inTriangleIndices[0]] = this.getCircle(...i): this.addCircle(...i);
});
} else {
convexHullUpdateNeeded = this.edgeIsPartOfConvexHull(onEdge);
inTriangleIndices.forEach(iti => {
const unique = arrayDifference(this.circles[iti][2], onEdge)[0];
this.circles[iti] = this.getCircle(onEdge[0], unique, this.points.length - 1);
this.addCircle(onEdge[1], unique, this.points.length - 1);
});
}
}
while (true) {
const inCircleIdxs = this.circles.map((i, idx) => [idx, i]).filter(c => lensq2(sub2(c[1][0], pt)) <= c[1][1]).map(i => i[0]);
const ownCircleIdxs = this.circles.map((i, idx) => [idx, i]).filter(i => i[1][2].includes(this.points.length - 1)).map(i => i[0]);
const otherCircleIdxs = inCircleIdxs.filter(i => !ownCircleIdxs.includes(i));
if(otherCircleIdxs.length == 0) break;
otherCircleIdxs.forEach(c => {
const commonCircleIndex = ownCircleIdxs
.map(i => [i, arrayIntersection(this.circles[i][2], this.circles[c][2])])
.filter(i => i[1].length == 2)[0];
if(commonCircleIndex === undefined) return;
//switch triangles
convexHullUpdateNeeded = flip(c, commonCircleIndex[0]) || convexHullUpdateNeeded;
});
};
this.log('added point ' + this.points.length, this.points[this.points.length - 1]);
//reset the convex hull
if(convexHullUpdateNeeded) {
this.refreshConvexHull();
}
}
refreshConvexHull() {
//get all the edges from triangles;
const edges = this.circles.flatMap(c => [[c[2][0], c[2][1]], [c[2][1], c[2][2]], [c[2][0],c[2][2]]]).map(i => i[0] < i[1]? [i[0], i[1]]: [i[1], i[0]]);
//see which are shared
const duplicates = edges.filter((e, i) => edges.filter((ee, ii) => ii > i && eq2(ee, e)).length > 0);
//the ones that are not shared make up the hull
this.convexHullEdges = edges.filter(e => duplicates.filter(d => eq2(e, d)).length == 0).map(e => e[0] < e[1]? [e[0], e[1]]: [e[1], e[0]]);
}
finalize(width, height) {
//get the unique points that are part of the convex hull
const pts = this.points.filter(
(p, i) => this.convexHullEdges.flatMap(i => i)
.filter((p, ii, s) => s.indexOf(p) === ii).includes(i)
);
//add those points mirrored in the edges of the canvas
[
...pts.filter(p => p[0] < 0).map(p => [-p[0] - width - 5, p[1]]), //mirror left
...pts.filter(p => p[0] > 0).map(p => [-p[0] + width + 5, p[1]]), //mirror right
...pts.filter(p => p[1] < 0).map(p => [p[0], -p[1] - height - 5]), //mirror top
...pts.filter(p => p[1] > 0).map(p => [p[0], -p[1] + height + 5]), //mirror bottom
].forEach(p => this.add(p));
}
}
const drawPoint = (t, p, r = 1) => { t.jump(p[0], p[1] - (r/2)); t.circle(r); }
class VoronoiDiagram {
constructor(delaunayTriangulation) {
this.dt = delaunayTriangulation;
this.dtMap = this.dt.circles.
map(c => [c[0], [[0, 1], [1, 2], [0, 2]].map(vte => [c[2][vte[0]], c[2][vte[1]]])]);
}
draw(t) {
this.dtMap.forEach((s, ks) => {
this.dtMap
.filter((c, kc) => kc < ks) // not the same as source or previous
.filter(c => //find any edge of c[2] in s[2]
c[1].filter(cc => s[1].filter(ss => eq2(ss, cc)).length > 0).length > 0
)
.forEach(c => {
t.jump(s[0]);
t.goto(c[0]);
})
});
}
getPolygonPoints(withPointIndex = false) {
const arrayIntersection = (array1, array2) => array1.filter(value => array2.includes(value));
//find all circles associated with each point [[pointIndex, [circles]], ...]
const circlesPerPoint = this.dt.points.map(
(p, i) => [i, this.dt.circles.filter(c => c[2].includes(i))]
).filter(p => p[1].length > 2); // for a complete polygon, it should at least have 3 edges
//find all indices of circles that have a completed polygon
// e.g. from the first circle, find circles that have an edge in common until the last one connects to the first one again
// in other words, each circle should have two other circles that each have a Delaunay Triangle edge in common with it
const pointIndicesWithFullVoronoiPolygon = circlesPerPoint.map(cpp => [cpp[0], cpp[1].map(cs =>
cpp[1].filter(cppc => arrayIntersection(cs[2], cppc[2]).length == 2).length == 2
).reduce((p, c) => p && c, true)]).filter(c => c[1] == true).map(c => c[0]);
// then order the points in such a way that that the path 'rotates' around the source point.
return circlesPerPoint.filter(p => pointIndicesWithFullVoronoiPolygon.includes(p[0])).map(p => {
return [p[0], p[1].map(c => [c[0], Math.atan2(...sub2(c[0], this.dt.points[p[0]]))])
.sort((a, b) => a[1] < b[1]? -1: 1)
.map(c => c[0])];
}).map(p => withPointIndex? p: p[1]);
}
}
const tri = new DelaunayTriangulation(pts);
if(mirrorEdges) tri.finalize(200, 200);
const vd = new VoronoiDiagram(tri);
const modClip = (val, lowerBound, upperBound) => { const diff = upperBound - lowerBound; while(val < lowerBound) val += diff; while(val > upperBound) val -= diff; return val; }
const regularPolygonPoint = (theta, polygonEdgeCount) => scale2([Math.cos(theta * Math.PI * 2), Math.sin(theta * Math.PI * 2)], Math.cos(Math.PI / polygonEdgeCount) / Math.cos(modClip(theta * Math.PI * 2, 0, Math.PI * 2 / polygonEdgeCount) - (Math.PI / polygonEdgeCount)))
if(drawMode === 0) {
if(dDelaunayTriangles) tri.drawTriangles(turtle);
if(dDelaunayPoints) tri.drawPoints(turtle);
if(dDelaunayCircles) tri.drawCircles(turtle);
if(dVoronoiLines) vd.draw(turtle);
if(dSources) pts.forEach(i => drawPoint(turtle, i));
} else if(drawMode == 1) {
if(dPolygonArtBorder > 0) {
[
[91, 92],
[93, 95],
[96, 99],
[100, 400 + dPolygonArtBorder],
].map(i => i.map(ii => ii - dPolygonArtBorder)).forEach(r => {
const pts = [];
const max = dPolygonArtShape == 2? 120: dPolygonArtShape;
r.forEach((rr, rrIdx) => {
Array.from({length: max + 1}).forEach((d, j) => {
let pt;
switch(dPolygonArtShape) {
case 2:
const u = (-rrIdx * 2) + 1;
pt = [rr * Math.sin(u * 2 * Math.PI * j / max),
rr * Math.cos(u * 2 * Math.PI * j / max)];
break;
default:
pt = scale2(regularPolygonPoint(j/max, dPolygonArtShape), rr);
}
pts.push([pt[0], pt[1]]);
turtle[j==0?'jump':'goto']([pt[0], pt[1]]);
});
});
const p = polygons.create();
p.addPoints(...pts);
polygons.draw(turtle, p);
});
}
if(dSources) pts.forEach(pt => {
const p = polygons.create();
p.addPoints(...Array.from({length: 15}).map((p, i, a) => [.8 * Math.sin(2 * Math.PI * i / a.length), .8 * Math.cos(2 * Math.PI * i / a.length),]).map(i => add2(pt, i)));
p.addHatching(0, .3);
polygons.draw(turtle, p);
});
vd.getPolygonPoints(true).forEach(pts => {
const p = polygons.create();
if(dPolygonShrink > 0) {
let shrunkPts = pts[1].map((p, i, a) =>
add2(p,
scale2(normalize2(
add2(
normalize2(sub2(pts[1][(i-1+a.length)%a.length], p)),
normalize2(sub2(pts[1][(i+1)%a.length], p))
)
), dPolygonShrink)
)
);
//the shrunken points may intersect now... that needs clearing.
//for now, a naive check if edges from adjacent points intersect at the same point
for(let i = 0; shrunkPts.length > 3 && i < shrunkPts.length; i++) {
const iTarget = (i - 1 + shrunkPts.length) % shrunkPts.length;
const next = (i + 1) % shrunkPts.length;
const nextTarget = (i + 2) % shrunkPts.length;
const intersect = segment_intersect2(shrunkPts[i], shrunkPts[iTarget], shrunkPts[next], shrunkPts[nextTarget], false);
if(intersect !== false) {
shrunkPts[i] = intersect;
shrunkPts.splice(next, 1);
}
}
p.addPoints(...shrunkPts);
} else {
p.addPoints(...pts[1]);
}
if(dPolygonHatching) {
let hatchDistance = .15;
let hatchDirection = 0;
switch(dPolygonHatching) {
case 1:
hatchDistance = dPolygonHatchMin + (Math.random() * (dPolygonHatchMaxc - dPolygonHatchMin));
break;
case 2:
case 3:
const maxx = ((100 - dPolygonArtBorder) * 2**.5)**2;
hatchDistance = dPolygonHatchMin + (
(dPolygonHatching == 2? lensq2(vd.dt.points[pts[0]]) / maxx: 1 - (lensq2(vd.dt.points[pts[0]]) / maxx))
* (dPolygonHatchMaxc - dPolygonHatchMin)
);
break;
case 4:
case 5:
const maxxx = 200;
hatchDistance = dPolygonHatchMin + (
(dPolygonHatching == 4? (vd.dt.points[pts[0]][1] + 100) / maxxx: 1 - ((vd.dt.points[pts[0]][1] + 100) / maxxx) )
* (dPolygonHatchMaxc - dPolygonHatchMin)
);
break;
default:
}
switch(dPolygonHatchDir) {
case 0:
hatchDirection = Math.random() * Math.PI;
break;
case 1:
hatchDirection += Math.PI / 2;
case 2:
hatchDirection += Math.atan2(...vd.dt.points[pts[0]]);
}
p.addHatching(hatchDirection, hatchDistance)
}
if(dVoronoiLines) p.addOutline();
polygons.draw(turtle, p);
});
if(dPolygonBackground) {
const grad = 75;
for(let i = 1; i <= grad; i++) {
const pp = polygons.create();
pp.addPoints(
[-100, 100 - (i * 200 / grad)], [100, 100 - (i * 200 / grad)],
[100, 100], [-100, 100]
);
pp.addHatching(1, dPolygonHatchMin + (
(dPolygonBackground == 1? (i/grad): 1 - (i/grad))
* (dPolygonHatchMaxc - dPolygonHatchMin)
));
polygons.draw(turtle, pp);
}
}
}
// The walk function will be called until it returns false.
function walk(i) {
return false;
}
////////////////////////////////////////////////////////////////
// Polygon Clipping utility code - Created by Reinder Nijhoff 2019
// (Polygon binning by Lionel Lemarie 2021)
// https://turtletoy.net/turtle/a5befa1f8d
////////////////////////////////////////////////////////////////
function Polygons(){const t=[],s=25,e=Array.from({length:s**2},t=>[]),n=class{constructor(){this.cp=[],this.dp=[],this.aabb=[]}addPoints(...t){let s=1e5,e=-1e5,n=1e5,h=-1e5;(this.cp=[...this.cp,...t]).forEach(t=>{s=Math.min(s,t[0]),e=Math.max(e,t[0]),n=Math.min(n,t[1]),h=Math.max(h,t[1])}),this.aabb=[s,n,e,h]}addSegments(...t){t.forEach(t=>this.dp.push(t))}addOutline(){for(let t=0,s=this.cp.length;t<s;t++)this.dp.push(this.cp[t],this.cp[(t+1)%s])}draw(t){for(let s=0,e=this.dp.length;s<e;s+=2)t.jump(this.dp[s]),t.goto(this.dp[s+1])}addHatching(t,s){const e=new n;e.cp.push([-1e5,-1e5],[1e5,-1e5],[1e5,1e5],[-1e5,1e5]);const h=Math.sin(t)*s,o=Math.cos(t)*s,a=200*Math.sin(t),i=200*Math.cos(t);for(let t=.5;t<150/s;t++)e.dp.push([h*t+i,o*t-a],[h*t-i,o*t+a]),e.dp.push([-h*t+i,-o*t-a],[-h*t-i,-o*t+a]);e.boolean(this,!1),this.dp=[...this.dp,...e.dp]}inside(t){let s=0;for(let e=0,n=this.cp.length;e<n;e++)this.segment_intersect(t,[.1,-1e3],this.cp[e],this.cp[(e+1)%n])&&s++;return 1&s}boolean(t,s=!0){const e=[];for(let n=0,h=this.dp.length;n<h;n+=2){const h=this.dp[n],o=this.dp[n+1],a=[];for(let s=0,e=t.cp.length;s<e;s++){const n=this.segment_intersect(h,o,t.cp[s],t.cp[(s+1)%e]);!1!==n&&a.push(n)}if(0===a.length)s===!t.inside(h)&&e.push(h,o);else{a.push(h,o);const n=o[0]-h[0],i=o[1]-h[1];a.sort((t,s)=>(t[0]-h[0])*n+(t[1]-h[1])*i-(s[0]-h[0])*n-(s[1]-h[1])*i);for(let n=0;n<a.length-1;n++)(a[n][0]-a[n+1][0])**2+(a[n][1]-a[n+1][1])**2>=.001&&s===!t.inside([(a[n][0]+a[n+1][0])/2,(a[n][1]+a[n+1][1])/2])&&e.push(a[n],a[n+1])}}return(this.dp=e).length>0}segment_intersect(t,s,e,n){const h=(n[1]-e[1])*(s[0]-t[0])-(n[0]-e[0])*(s[1]-t[1]);if(0===h)return!1;const o=((n[0]-e[0])*(t[1]-e[1])-(n[1]-e[1])*(t[0]-e[0]))/h,a=((s[0]-t[0])*(t[1]-e[1])-(s[1]-t[1])*(t[0]-e[0]))/h;return o>=0&&o<=1&&a>=0&&a<=1&&[t[0]+o*(s[0]-t[0]),t[1]+o*(s[1]-t[1])]}};return{list:()=>t,create:()=>new n,draw:(n,h,o=!0)=>{reducedPolygonList=function(n){const h={},o=200/s;for(var a=0;a<s;a++){const c=a*o-100,r=[0,c,200,c+o];if(!(n[3]<r[1]||n[1]>r[3]))for(var i=0;i<s;i++){const c=i*o-100;r[0]=c,r[2]=c+o,n[0]>r[2]||n[2]<r[0]||e[i+a*s].forEach(s=>{const e=t[s];n[3]<e.aabb[1]||n[1]>e.aabb[3]||n[0]>e.aabb[2]||n[2]<e.aabb[0]||(h[s]=1)})}}return Array.from(Object.keys(h),s=>t[s])}(h.aabb);for(let t=0;t<reducedPolygonList.length&&h.boolean(reducedPolygonList[t]);t++);h.draw(n),o&&function(n){t.push(n);const h=t.length-1,o=200/s;e.forEach((t,e)=>{const a=e%s*o-100,i=(e/s|0)*o-100,c=[a,i,a+o,i+o];c[3]<n.aabb[1]||c[1]>n.aabb[3]||c[0]>n.aabb[2]||c[2]<n.aabb[0]||t.push(h)})}(h)}}}