JurgenNoise 🗯️

I tried to implement my own noise generator.

I start with adding the 4 corners of the area I want to cover to the population with some padding. Then I add n points to it in a more or less uniform way: each iteration I add the one point from 10 random candidates that has the largest distance to its nearest point already in the population. I apply Delaunay triangulation to the population and give each vertice a random value [0,1>. Then the grid is set.

To calculate the value for any point, the value is interpolated from the values of the vertices that make up the triangle it hits.

```const entropy = 250; //min=0 max=750 step=1
const showDebug = 0; //min=0 max=1 step=1 (No, Yes)
const ptsPerRow = 70; //min=10 max=100 step=1
const ptLength = 1.3 //min=.2 max=5 step=.1

const boundary = 120;
const debug = showDebug == 1;

// 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 jn = new JurgenNoise(entropy, [-boundary, -boundary], [boundary, boundary])

Array.from({length: entropy - 1}).forEach(v => jn.increaseEntropy());

if(debug) jn.showTriangles(turtle);

// The walk function will be called until it returns false.
function walk(i) {
const x = ((i % ptsPerRow) + .5) * (200/ptsPerRow) - 100;
const y = (((i / ptsPerRow) | 0) + .5) * (200/ptsPerRow) - 100;

const pt = [x, y];

turtle.jump(pt);
turtle.goto(add2(pt, trans2(rot2(2 * Math.PI * jn.getValueAt(pt)), [0, (200/ptsPerRow) * ptLength])));

return i < ptsPerRow**2 - 1;
}

function JurgenNoise(density, leftTop = [-150, -150], rightBottom = [150, 150], rnd = Math.random) {
class JurgenNoise {
constructor(density, leftTop = [-150, -150], rightBottom = [150, 150]) {
this.upd = new UniformPointDistributor(leftTop, rightBottom);
this.updIterator = this.upd.getPointIterator();
const startPts = [
[...leftTop, rnd()],
[rightBottom[0], leftTop[1], rnd()],
[...rightBottom, rnd()],
[leftTop[0], rightBottom[1], rnd()],
//...Array.from({length:40}).map((v, i, a) => [
//    100 * Math.SQRT2 * Math.sin(i * 2 * Math.PI / a.length) + Math.random(),
//    100 * Math.SQRT2 * Math.cos(i * 2 * Math.PI / a.length) + Math.random(),
//    rnd()
//])
];
this.dt = new DelaunayTriangulation(startPts);
}
showTriangles(turtle) {
this.dt.drawTriangles(turtle);
}
increaseEntropy() {
this.dt.add( this.updIterator.next().value.map((v,i) => i < 2? v: rnd()) );
}
getValueAt(pt) {
const [a, b, c] = this.dt.getTriangleFor(pt);
const [a_b_Part, c_cPt_PartAbs, aipt] = intersect_info2(a, sub2(b, a), c, sub2(pt, c));
const [b_c_Part, a_aPt_PartAbs, bipt] = intersect_info2(b, sub2(c, b), a, sub2(pt, a));
const [c_a_Part, b_bPt_PartAbs, cipt] = intersect_info2(c, sub2(a, c), b, sub2(pt, b));
return ((1-(1/a_aPt_PartAbs)) * a[2]) +
((1-(1/b_bPt_PartAbs)) * b[2]) +
((1-(1/c_cPt_PartAbs)) * c[2]);
}
}
return new JurgenNoise(density, leftTop, rightBottom);
}

////////////////////////////////////////////////////////////////
// Uniform Point Distribution code - Created by Jurgen Westerhof 2023
////////////////////////////////////////////////////////////////
function UniformPointDistributor(leftTop = [-100, -100], rightBottom = [100, 100]) {
class UniformPointDistributor {
constructor(leftTop = [-100, -100], rightBottom = [100, 100]) {
this.leftTop = leftTop;
this.rightBottom = rightBottom;
this.width = rightBottom[0]-leftTop[0];
this.height = rightBottom[1]-leftTop[1];
this.maxDist = (this.width**2+this.height**2)**.5;
this.pts = [];
}

*getPointIterator(radiusFunction = null, candidates = 20, maxTries = 1000) {

const randomPoint = () => [Math.random()*this.width+this.leftTop[0],Math.random()*this.height+this.leftTop[1]];

yield this.pts[this.pts.length - 1];

while(true) {
let pt = [0,0,-1];
let tries = 0;
while(pt[2] < 0 && tries < maxTries) {
tries++;
//using [length] candidate points
pt = Array.from({length: candidates})
//which are random points
.map(i => randomPoint())
//then add the distance to that candidate minus the radius of each point it is compared to
.map(i => [i[0], i[1], this.pts.map(j => [j[0], j[1], Math.hypot(i[0]-j[0], i[1]-j[1]) - j[2]])
//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,this.maxDist])[2]
])
//then pick the candidate that has the largest minimum distance from the group of candidates
.reduce((prev, current) => prev == null? current: ((current[2] > prev[2])? current: prev), null)
//and set the 3rd position to its own radius instead of the distance to the nearest point
.map((v, i, arr) => i < 2? v: radiusFunction(arr[0], arr[1], v))
////and remove the distance before promoting the candidate
//.filter((i, k) => k < 2)
}
if(tries == maxTries) return false;
//add a point to the list
this.pts.push(pt);
yield pt;
}
}
this.pts.push(pt);
}
}
return new UniformPointDistributor(leftTop, rightBottom);
}

function approx1(a,b,delta=0.0001) { return -delta < a-b && a-b < delta }

////////////////////////////////////////////////////////////////
// 2D Vector Math utility code - Created by several Turtletoy users
////////////////////////////////////////////////////////////////
function norm2(a) { return scale2(a, 1/len2(a)); }
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 mul2(a, b) { return [a[0]*b[0], a[1]*b[1]]; }
function scale2(a, s) { return [a[0]*s,a[1]*s]; }
function lerp2(a,b,t) { return [a[0]*(1-t) + b[0]*t, a[1]*(1-t) + b[1]*t]; }
function lenSq2(a) { return a[0]**2+a[1]**2; }
function len2(a) { return Math.sqrt(lenSq2(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]]; } //Matrix(2x1) x Matrix(2x2)
function dist2(a,b) { return Math.hypot(...sub2(a,b)); }
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 multiply2(a2x2, a) { return [(a[0]*a2x2[0])+(a[1]*a2x2[1]),(a[0]*a2x2[2])+(a[1]*a2x2[3])]; } //Matrix(2x2) x Matrix(1x2)
function intersect_info2(as, ad, bs, bd) {
const d = [bs[0] - as[0], bs[1] - as[1]];
if(det === 0) return false;
const res = [(d[1] * bd[0] - d[0] * bd[1]) / det, (d[1] * ad[0] - d[0] * ad[1]) / det];
}
function intersect_ray2(a, b, c, d) {
const i = intersect_info2(a, b, c, d);
return i === false? i: i[2];
}
function segment_intersect2(a,b,c,d, inclusive = true) {
const i = intersect_info2(a, sub2(b, a), c, sub2(d, c));
if(i === false) return false;
const t = inclusive? 0<=i[0]&&i[0]<=1&&0<=i[1]&&i[1]<=1: 0<i[0]&&i[0]<1&&0<i[1]&&i[1]<1;
return t?i[2]:false;
}
function approx2(a,b,delta=0.0001) { return len2(sub2(a,b)) < delta }
function eq2(a,b) { return a[0]==b[0]&&a[1]==b[1]; }
function clamp2(a, tl, br) { return [Math.max(Math.min(br[0], a[0]), tl[0]), Math.max(Math.min(br[1], a[1]), tl[1])]; }
function nearSq2(test, near, delta = .0001) {
return near[0] - delta < test[0] && test[0] < near[0] + delta &&
near[1] - delta < test[1] && test[1] < near[1] + delta;
}

////////////////////////////////////////////////////////////////
// Start of some path utility code - Created by Jurgen Westerhof 2023
////////////////////////////////////////////////////////////////
function circlePoints(radius, extend = 2 * Math.PI, clockWiseStart = 0, steps = null, includeLast = false) { return [steps == null? (radius*extend+1)|0: steps].map(steps => Array.from({length: steps}).map((v, i, a) => [radius * Math.cos(clockWiseStart + extend*i/(a.length-(includeLast?1:0))), radius * Math.sin(clockWiseStart + extend*i/(a.length-(includeLast?1:0)))])).pop(); }
function pts2Edges(pts) { return pts.map((v, i, a) => [v, a[(i+1)%a.length]]); }
function drawPath(turtle, pts) { return pts.forEach((pt, i) => turtle[i == 0? 'jump':'goto'](pt)); }
function drawTour(turtle, pts) { return drawPath(turtle, pts.concat([pts[0]])); }
function drawPoint(turtle, pt) { return drawTour(turtle, circlePoints(.5).map(p => add2(p, pt))); }
function isInPolygon(edges, pt) { return edges.map(edge => intersect_info2(edge[0], sub2(edge[1], edge[0]), pt, [0, 300])).filter(ii => ii !== false && 0 <= ii[0] && ii[0] <= 1 && 0 < ii[1]).length % 2 == 1; }
function isInVectorTour(vectors, pt) { return vectors.map(v => intersect_info2(...v, pt[0], pt[1])).filter(ii => ii !== false && 0 <= ii[0] && ii[0] < 1 && 0 <= ii[1]).length % 2 == 1; }
function tourToVectors(path) { return path.map((v, i, a) => [v, sub2(a[(i+1)%a.length], v)]); }
function thickLinePaths(from, to, thickness) { return [trans2(rot2(Math.atan2(...sub2(to, from))), [thickness/2, 0])].map(v => [[add2(from, v), add2(to, v)], [sub2(from, v), sub2(to, v)]]).pop();}

////////////////////////////////////////////////////////////////
// Delaunay Triangulation utility code - Created by Jurgen Westerhof 2023
// Known bug: cannot handle more than 3 points on one circle.
//  (e.g. adding a perfect circle with no points in that circle will cause an error)
// https://turtletoy.net/turtle/5d4f95a589
////////////////////////////////////////////////////////////////
function DelaunayTriangulation(pts) {
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]];

pts.filter((i, k) => k > 2).forEach(i => this.add(i));
}
log(...msg) {
if(debug) {
console.log(...msg);
}
}
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 => {
});
}
})
});
}
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;
}
getTriangleFor(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);
}
*/
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) return [];
return this.circles[inTriangleIndices[0]][2].map(idx => this.points[idx]);
}
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) => {
});

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);
});
}
}

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