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.
Log in to post a comment.
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()
//])
];
startPts.forEach(pt => this.upd.addPoint(pt));
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) {
if(radiusFunction == null) radiusFunction = (x, y, maximum) => 0;
const randomPoint = () => [Math.random()*this.width+this.leftTop[0],Math.random()*this.height+this.leftTop[1]];
this.pts.push([randomPoint()].map(pt => [...pt, radiusFunction(...pt)])[0]);
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;
}
}
addPoint(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]];
const det = bd[0] * ad[1] - bd[1] * ad[0];
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];
return [...res, add2(as, scale2(ad, res[0]))];
}
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]];
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;
}
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]);
}
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));
}
}
return new DelaunayTriangulation(pts);
}