-
-
Save JobLeonard/b5dccf0ebacc06f30baf20029f206fb5 to your computer and use it in GitHub Desktop.
Update function
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
constructor(coords) { | |
const n = coords.length >> 1; | |
if (n > 0 && typeof coords[0] !== 'number') throw new Error('Expected coords to contain numbers.'); | |
this.coords = coords; | |
// arrays that will store the triangulation graph | |
const maxTriangles = 2 * n - 5; | |
const triangles = this.triangles = this.trianglesRaw = new Uint32Array(maxTriangles * 3); | |
const halfedges = this.halfedges = this.halfedgesRaw = new Int32Array(maxTriangles * 3); | |
// temporary arrays for tracking the edges of the advancing convex hull | |
this._hashSize = Math.ceil(Math.sqrt(n)); | |
const hullPrev = this.hullPrev = new Uint32Array(n); // edge to prev edge | |
const hullNext = this.hullNext = new Uint32Array(n); // edge to next edge | |
const hullTri = this.hullTri = new Uint32Array(n); // edge to adjacent triangle | |
const hullHash = this.hullHash = new Int32Array(this._hashSize).fill(-1); // angular edge hash | |
// populate an array of point indices; calculate input data bbox | |
const ids = this.ids = new Uint32Array(n); | |
let minX = Infinity; | |
let minY = Infinity; | |
let maxX = -Infinity; | |
let maxY = -Infinity; | |
for (let i = 0; i < n; i++) { | |
const x = coords[2 * i]; | |
const y = coords[2 * i + 1]; | |
if (x < minX) minX = x; | |
if (y < minY) minY = y; | |
if (x > maxX) maxX = x; | |
if (y > maxY) maxY = y; | |
ids[i] = i; | |
} | |
const cx = (minX + maxX) / 2; | |
const cy = (minY + maxY) / 2; | |
let minDist = Infinity; | |
let i0, i1, i2; | |
// pick a seed point close to the center | |
for (let i = 0; i < n; i++) { | |
const d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]); | |
if (d < minDist) { | |
i0 = i; | |
minDist = d; | |
} | |
} | |
const i0x = coords[2 * i0]; | |
const i0y = coords[2 * i0 + 1]; | |
minDist = Infinity; | |
// find the point closest to the seed | |
for (let i = 0; i < n; i++) { | |
if (i === i0) continue; | |
const d = dist(i0x, i0y, coords[2 * i], coords[2 * i + 1]); | |
if (d < minDist && d > 0) { | |
i1 = i; | |
minDist = d; | |
} | |
} | |
let i1x = coords[2 * i1]; | |
let i1y = coords[2 * i1 + 1]; | |
let minRadius = Infinity; | |
// find the third point which forms the smallest circumcircle with the first two | |
for (let i = 0; i < n; i++) { | |
if (i === i0 || i === i1) continue; | |
const r = circumradius(i0x, i0y, i1x, i1y, coords[2 * i], coords[2 * i + 1]); | |
if (r < minRadius) { | |
i2 = i; | |
minRadius = r; | |
} | |
} | |
let i2x = coords[2 * i2]; | |
let i2y = coords[2 * i2 + 1]; | |
if (minRadius === Infinity) { | |
throw new Error('No Delaunay triangulation exists for this input.'); | |
} | |
// swap the order of the seed points for counter-clockwise orientation | |
if (orient(i0x, i0y, i1x, i1y, i2x, i2y)) { | |
const i = i1; | |
const x = i1x; | |
const y = i1y; | |
i1 = i2; | |
i1x = i2x; | |
i1y = i2y; | |
i2 = i; | |
i2x = x; | |
i2y = y; | |
} | |
const center = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y); | |
this._cx = center.x; | |
this._cy = center.y; | |
const dists = this.dists = new Float64Array(n); | |
for (let i = 0; i < n; i++) { | |
dists[i] = dist(coords[2 * i], coords[2 * i + 1], center.x, center.y); | |
} | |
// sort the points by distance from the seed triangle circumcenter | |
quicksort(ids, dists, 0, n - 1); | |
// set up the seed triangle as the starting hull | |
this.hullStart = i0; | |
let hullSize = 3; | |
hullNext[i0] = hullPrev[i2] = i1; | |
hullNext[i1] = hullPrev[i0] = i2; | |
hullNext[i2] = hullPrev[i1] = i0; | |
hullTri[i0] = 0; | |
hullTri[i1] = 1; | |
hullTri[i2] = 2; | |
hullHash[this._hashKey(i0x, i0y)] = i0; | |
hullHash[this._hashKey(i1x, i1y)] = i1; | |
hullHash[this._hashKey(i2x, i2y)] = i2; | |
this.trianglesLen = 0; | |
this._addTriangle(i0, i1, i2, -1, -1, -1); | |
for (let k = 0, xp, yp; k < ids.length; k++) { | |
const i = ids[k]; | |
const x = coords[2 * i]; | |
const y = coords[2 * i + 1]; | |
// skip near-duplicate points | |
if (k > 0 && Math.abs(x - xp) <= EPSILON && Math.abs(y - yp) <= EPSILON) continue; | |
xp = x; | |
yp = y; | |
// skip seed triangle points | |
if (i === i0 || i === i1 || i === i2) continue; | |
// find a visible edge on the convex hull using edge hash | |
let start = 0; | |
for (let j = 0, key = this._hashKey(x, y); j < this._hashSize; j++) { | |
start = hullHash[(key + j) % this._hashSize]; | |
if (start !== -1 && start !== hullNext[start]) break; | |
} | |
start = hullPrev[start]; | |
let e = start, q; | |
while (q = hullNext[e], !orient(x, y, coords[2 * e], coords[2 * e + 1], coords[2 * q], coords[2 * q + 1])) { | |
e = q; | |
if (e === start) { | |
e = -1; | |
break; | |
} | |
} | |
if (e === -1) continue; // likely a near-duplicate point; skip it | |
// add the first triangle from the point | |
let t = this._addTriangle(e, i, hullNext[e], -1, -1, hullTri[e]); | |
// recursively flip triangles from the point until they satisfy the Delaunay condition | |
hullTri[i] = this._legalize(t + 2); | |
hullTri[e] = t; // keep track of boundary triangles on the hull | |
hullSize++; | |
// walk forward through the hull, adding more triangles and flipping recursively | |
let n = hullNext[e]; | |
while (q = hullNext[n], orient(x, y, coords[2 * n], coords[2 * n + 1], coords[2 * q], coords[2 * q + 1])) { | |
t = this._addTriangle(n, i, q, hullTri[i], -1, hullTri[n]); | |
hullTri[i] = this._legalize(t + 2); | |
hullNext[n] = n; // mark as removed | |
hullSize--; | |
n = q; | |
} | |
// walk backward from the other side, adding more triangles and flipping | |
if (e === start) { | |
while (q = hullPrev[e], orient(x, y, coords[2 * q], coords[2 * q + 1], coords[2 * e], coords[2 * e + 1])) { | |
t = this._addTriangle(q, i, e, -1, hullTri[e], hullTri[q]); | |
this._legalize(t + 2); | |
hullTri[q] = t; | |
hullNext[e] = e; // mark as removed | |
hullSize--; | |
e = q; | |
} | |
} | |
// update the hull indices | |
this.hullStart = hullPrev[i] = e; | |
hullNext[e] = hullPrev[n] = i; | |
hullNext[i] = n; | |
// save the two new edges in the hash table | |
hullHash[this._hashKey(x, y)] = i; | |
hullHash[this._hashKey(coords[2 * e], coords[2 * e + 1])] = e; | |
} | |
this.hull = new Uint32Array(hullSize); | |
for (let i = 0, e = this.hullStart; i < hullSize; i++) { | |
this.hull[i] = e; | |
e = hullNext[e]; | |
} | |
// trim typed triangle mesh arrays | |
this.triangles = triangles.subarray(0, this.trianglesLen); | |
this.halfedges = halfedges.subarray(0, this.trianglesLen); | |
} | |
update(coords) { | |
const n = coords.length >> 1; | |
if (n > 0 && typeof coords[0] !== 'number') throw new Error('Expected coords to contain numbers.'); | |
if (this.coords.length !== coords) throw new Error('New coordinates must have the same number of points!'); | |
this.coords = coords; | |
// arrays that will store the triangulation graph | |
// const maxTriangles = 2 * n - 5; | |
const triangles = this.triangles = this.trianglesRaw; | |
const halfedges = this.halfedges = this.halfedgesRaw; | |
triangles.fill(0); | |
halfedges.fill(0); | |
// temporary arrays for tracking the edges of the advancing convex hull | |
this._hashSize = Math.ceil(Math.sqrt(n)); | |
const hullPrev = this.hullPrev; // edge to prev edge | |
const hullNext = this.hullNext; // edge to next edge | |
const hullTri = this.hullTri; // edge to adjacent triangle | |
const hullHash = this.hullHash; // angular edge hash | |
hullPrev.fill(0); | |
hullNext.fill(0); | |
hullTri.fill(0); | |
hullHash.fill(-1) | |
// populate an array of point indices; calculate input data bbox | |
const ids = this.ids; | |
ids.fill(0); | |
let minX = Infinity; | |
let minY = Infinity; | |
let maxX = -Infinity; | |
let maxY = -Infinity; | |
for (let i = 0; i < n; i++) { | |
const x = coords[2 * i]; | |
const y = coords[2 * i + 1]; | |
if (x < minX) minX = x; | |
if (y < minY) minY = y; | |
if (x > maxX) maxX = x; | |
if (y > maxY) maxY = y; | |
ids[i] = i; | |
} | |
const cx = (minX + maxX) / 2; | |
const cy = (minY + maxY) / 2; | |
let minDist = Infinity; | |
let i0, i1, i2; | |
// pick a seed point close to the center | |
for (let i = 0; i < n; i++) { | |
const d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]); | |
if (d < minDist) { | |
i0 = i; | |
minDist = d; | |
} | |
} | |
const i0x = coords[2 * i0]; | |
const i0y = coords[2 * i0 + 1]; | |
minDist = Infinity; | |
// find the point closest to the seed | |
for (let i = 0; i < n; i++) { | |
if (i === i0) continue; | |
const d = dist(i0x, i0y, coords[2 * i], coords[2 * i + 1]); | |
if (d < minDist && d > 0) { | |
i1 = i; | |
minDist = d; | |
} | |
} | |
let i1x = coords[2 * i1]; | |
let i1y = coords[2 * i1 + 1]; | |
let minRadius = Infinity; | |
// find the third point which forms the smallest circumcircle with the first two | |
for (let i = 0; i < n; i++) { | |
if (i === i0 || i === i1) continue; | |
const r = circumradius(i0x, i0y, i1x, i1y, coords[2 * i], coords[2 * i + 1]); | |
if (r < minRadius) { | |
i2 = i; | |
minRadius = r; | |
} | |
} | |
let i2x = coords[2 * i2]; | |
let i2y = coords[2 * i2 + 1]; | |
if (minRadius === Infinity) { | |
throw new Error('No Delaunay triangulation exists for this input.'); | |
} | |
// swap the order of the seed points for counter-clockwise orientation | |
if (orient(i0x, i0y, i1x, i1y, i2x, i2y)) { | |
const i = i1; | |
const x = i1x; | |
const y = i1y; | |
i1 = i2; | |
i1x = i2x; | |
i1y = i2y; | |
i2 = i; | |
i2x = x; | |
i2y = y; | |
} | |
const center = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y); | |
this._cx = center.x; | |
this._cy = center.y; | |
const dists = this.dists; | |
for (let i = 0; i < n; i++) { | |
dists[i] = dist(coords[2 * i], coords[2 * i + 1], center.x, center.y); | |
} | |
// sort the points by distance from the seed triangle circumcenter | |
quicksort(ids, dists, 0, n - 1); | |
// set up the seed triangle as the starting hull | |
this.hullStart = i0; | |
let hullSize = 3; | |
hullNext[i0] = hullPrev[i2] = i1; | |
hullNext[i1] = hullPrev[i0] = i2; | |
hullNext[i2] = hullPrev[i1] = i0; | |
hullTri[i0] = 0; | |
hullTri[i1] = 1; | |
hullTri[i2] = 2; | |
hullHash[this._hashKey(i0x, i0y)] = i0; | |
hullHash[this._hashKey(i1x, i1y)] = i1; | |
hullHash[this._hashKey(i2x, i2y)] = i2; | |
this.trianglesLen = 0; | |
this._addTriangle(i0, i1, i2, -1, -1, -1); | |
for (let k = 0, xp, yp; k < ids.length; k++) { | |
const i = ids[k]; | |
const x = coords[2 * i]; | |
const y = coords[2 * i + 1]; | |
// skip near-duplicate points | |
if (k > 0 && Math.abs(x - xp) <= EPSILON && Math.abs(y - yp) <= EPSILON) continue; | |
xp = x; | |
yp = y; | |
// skip seed triangle points | |
if (i === i0 || i === i1 || i === i2) continue; | |
// find a visible edge on the convex hull using edge hash | |
let start = 0; | |
for (let j = 0, key = this._hashKey(x, y); j < this._hashSize; j++) { | |
start = hullHash[(key + j) % this._hashSize]; | |
if (start !== -1 && start !== hullNext[start]) break; | |
} | |
start = hullPrev[start]; | |
let e = start, q; | |
while (q = hullNext[e], !orient(x, y, coords[2 * e], coords[2 * e + 1], coords[2 * q], coords[2 * q + 1])) { | |
e = q; | |
if (e === start) { | |
e = -1; | |
break; | |
} | |
} | |
if (e === -1) continue; // likely a near-duplicate point; skip it | |
// add the first triangle from the point | |
let t = this._addTriangle(e, i, hullNext[e], -1, -1, hullTri[e]); | |
// recursively flip triangles from the point until they satisfy the Delaunay condition | |
hullTri[i] = this._legalize(t + 2); | |
hullTri[e] = t; // keep track of boundary triangles on the hull | |
hullSize++; | |
// walk forward through the hull, adding more triangles and flipping recursively | |
let n = hullNext[e]; | |
while (q = hullNext[n], orient(x, y, coords[2 * n], coords[2 * n + 1], coords[2 * q], coords[2 * q + 1])) { | |
t = this._addTriangle(n, i, q, hullTri[i], -1, hullTri[n]); | |
hullTri[i] = this._legalize(t + 2); | |
hullNext[n] = n; // mark as removed | |
hullSize--; | |
n = q; | |
} | |
// walk backward from the other side, adding more triangles and flipping | |
if (e === start) { | |
while (q = hullPrev[e], orient(x, y, coords[2 * q], coords[2 * q + 1], coords[2 * e], coords[2 * e + 1])) { | |
t = this._addTriangle(q, i, e, -1, hullTri[e], hullTri[q]); | |
this._legalize(t + 2); | |
hullTri[q] = t; | |
hullNext[e] = e; // mark as removed | |
hullSize--; | |
e = q; | |
} | |
} | |
// update the hull indices | |
this.hullStart = hullPrev[i] = e; | |
hullNext[e] = hullPrev[n] = i; | |
hullNext[i] = n; | |
// save the two new edges in the hash table | |
hullHash[this._hashKey(x, y)] = i; | |
hullHash[this._hashKey(coords[2 * e], coords[2 * e + 1])] = e; | |
} | |
this.hull = new Uint32Array(hullSize); | |
for (let i = 0, e = this.hullStart; i < hullSize; i++) { | |
this.hull[i] = e; | |
e = hullNext[e]; | |
} | |
// trim typed triangle mesh arrays | |
this.triangles = triangles.subarray(0, this.trianglesLen); | |
this.halfedges = halfedges.subarray(0, this.trianglesLen); | |
return this; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment