Delaunay triangulation by edge legalization: Examples & Code
Delaunay triangulation by edge legalization: Triangulate the convex hull, insert remaining sites, and flip an interior edge when its opposite site lies…
javascript
function algorithm(x, y, n, output) {
if (n < 0 || n > 10) { return -1; } for (let i = 0; i < n; i++) { if (x[i] < -10 || x[i] > 10 || y[i] < -10 || y[i] > 10) { return -1; } }
let order = Array(256).fill(0); let unique = Array(256).fill(0); let hull = Array(256).fill(0); let ta = Array(256).fill(0); let tb = Array(256).fill(0); let tc = Array(256).fill(0); let nextA = Array(256).fill(0); let nextB = Array(256).fill(0); let nextC = Array(256).fill(0); let vertices = Array(256).fill(0);
let size = 0; let top = 0; let boundary = 0; let count = 0; let key = 0; let cursor = 0; let point = 0; let onHull = 0; let found = 0; let a = 0; let b = 0; let c = 0; let edgeU = 0; let edgeV = 0; let third = 0; let nextCount = 0; let changed = 0; let shared = 0; let u = 0; let v = 0; let oppositeA = 0; let oppositeB = 0; let ax = 0; let ay = 0; let bx = 0; let by = 0; let cx = 0; let cy = 0; let determinant = 0; let keyA = 0; let keyB = 0; let keyC = 0;
for (let i = 0; i < n; i++) { order[i] = i; } for (let i = 1; i < n; i++) { key = order[i]; cursor = i-1; while (cursor >= 0 && (x[order[cursor]] > x[key] || (x[order[cursor]] == x[key] && y[order[cursor]] > y[key]))) { order[cursor+1] = order[cursor]; cursor--; } order[cursor+1] = key; }
for (let i = 0; i < n; i++) { point = order[i]; if (size == 0 || x[point] != x[unique[size-1]] || y[point] != y[unique[size-1]]) { unique[size] = point; size++; } } if (size < 3) { return 0; }
for (let i = 0; i < size; i++) { point = unique[i]; while (top >= 2 && ((x[hull[top-1]]-x[hull[top-2]])*(y[point]-y[hull[top-2]])-(y[hull[top-1]]-y[hull[top-2]])*(x[point]-x[hull[top-2]])) <= 0) { top--; } hull[top] = point; top++; } boundary = top+1;
for (let i = size-2; i >= 0; i--) { point = unique[i]; while (top >= boundary && ((x[hull[top-1]]-x[hull[top-2]])*(y[point]-y[hull[top-2]])-(y[hull[top-1]]-y[hull[top-2]])*(x[point]-x[hull[top-2]])) <= 0) { top--; } hull[top] = point; top++; } top--; if (top < 3) { return 0; }
for (let i = 1; i < top-1; i++) { ta[count] = hull[0]; tb[count] = hull[i]; tc[count] = hull[i+1]; count++; }
for (let position = 0; position < size; position++) { point = unique[position]; onHull = 0; for (let i = 0; i < top; i++) { if (hull[i] == point) { onHull = 1; } } if (onHull != 0) { continue; } found = -1; edgeU = -1; edgeV = -1;
for (let i = 0; i < count && found < 0; i++) { a = ta[i]; b = tb[i]; c = tc[i]; if (((x[b]-x[a])*(y[point]-y[a])-(y[b]-y[a])*(x[point]-x[a])) >= 0 && ((x[c]-x[b])*(y[point]-y[b])-(y[c]-y[b])*(x[point]-x[b])) >= 0 && ((x[a]-x[c])*(y[point]-y[c])-(y[a]-y[c])*(x[point]-x[c])) >= 0) { found = i; if (((x[b]-x[a])*(y[point]-y[a])-(y[b]-y[a])*(x[point]-x[a])) == 0) { edgeU = a; edgeV = b; } else if (((x[c]-x[b])*(y[point]-y[b])-(y[c]-y[b])*(x[point]-x[b])) == 0) { edgeU = b; edgeV = c; } else if (((x[a]-x[c])*(y[point]-y[c])-(y[a]-y[c])*(x[point]-x[c])) == 0) { edgeU = c; edgeV = a; } } } if (found < 0) { return -2; }
if (edgeU < 0) { a = ta[found]; b = tb[found]; c = tc[found]; ta[found] = a; tb[found] = b; tc[found] = point; ta[count] = b; tb[count] = c; tc[count] = point; count++; ta[count] = c; tb[count] = a; tc[count] = point; count++; }
Nov 16, 2026
javascript