Published by Dimitris Kougioumtzis · Updated
Triangulate the convex hull, insert remaining sites, and flip an interior edge when its opposite site lies strictly inside the adjacent circumcircle.
Triangulate a lexicographically rooted convex-hull fan, insert non-hull sites by splitting containing triangles or edges, and repeatedly legalize shared edges with the empty-circumcircle predicate. Flip only strictly positive incircle determinants.
When to use Delaunay triangulation by edge legalization
Building and inspecting a small planar Delaunay mesh with deterministic degeneracy handling.
Choosing an alternative
Voronoi cells describe nearest-site regions; Delaunay triangles connect their dual site relationships. This view uses a naive edge-legalization implementation rather than an optimal divide-and-conquer, sweep or randomized production triangulator.
Worked example: input and state changes
Example input
-5,-3;5,-3;0,5;-1,0;2,1
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Deduplicate coordinates and construct a lexicographically rooted hull fan.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4 ], "active": [], "kind": "graph", "points": [ [ -5, -3 ], [ 5, -3 ], [ 0, 5 ], [ -1, 0 ], [ 2, 1 ] ], "nodeLabels": [ "P0 (-5, -3)", "P1 (5, -3)", "P2 (0, 5)", "P3 (-1, 0)", "P4 (2, 1)" ], "polygons": [], "directed": false, "chosen": [], "visited": [], "result": 0, "output": [] }Step 1: Initial convex-hull fan; insert non-hull sites in lexicographic order.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4 ], "active": [], "kind": "graph", "points": [ [ -5, -3 ], [ 5, -3 ], [ 0, 5 ], [ -1, 0 ], [ 2, 1 ] ], "nodeLabels": [ "P0 (-5, -3)", "P1 (5, -3)", "P2 (0, 5)", "P3 (-1, 0)", "P4 (2, 1)" ], "polygons": [ { "indices": [ 0, 1, 2 ], "color": [ 0.18, 0.4, 0.52 ] } ], "directed": false, "chosen": [], "visited": [], "result": 0, "output": [] }Step 2: Insert P3 by splitting its containing triangle.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4 ], "active": [ 3 ], "kind": "graph", "points": [ [ -5, -3 ], [ 5, -3 ], [ 0, 5 ], [ -1, 0 ], [ 2, 1 ] ], "nodeLabels": [ "P0 (-5, -3)", "P1 (5, -3)", "P2 (0, 5)", "P3 (-1, 0)", "P4 (2, 1)" ], "polygons": [ { "indices": [ 0, 1, 3 ], "color": [ 0.6, 0.4, 0.15 ] }, { "indices": [ 1, 2, 3 ], "color": [ 0.6, 0.4, 0.15 ] }, { "indices": [ 2, 0, 3 ], "color": [ 0.6, 0.4, 0.15 ] } ], "directed": false, "chosen": [ 1, 2, 4 ], "visited": [], "result": 0, "output": [] }Step 3: Insert P4 by splitting its containing triangle.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4 ], "active": [ 4 ], "kind": "graph", "points": [ [ -5, -3 ], [ 5, -3 ], [ 0, 5 ], [ -1, 0 ], [ 2, 1 ] ], "nodeLabels": [ "P0 (-5, -3)", "P1 (5, -3)", "P2 (0, 5)", "P3 (-1, 0)", "P4 (2, 1)" ], "polygons": [ { "indices": [ 0, 1, 3 ], "color": [ 0.18, 0.4, 0.52 ] }, { "indices": [ 1, 2, 4 ], "color": [ 0.6, 0.4, 0.15 ] }, { "indices": [ 2, 0, 3 ], "color": [ 0.18, 0.4, 0.52 ] }, { "indices": [ 2, 3, 4 ], "color": [ 0.6, 0.4, 0.15 ] }, { "indices": [ 3, 1, 4 ], "color": [ 0.6, 0.4, 0.15 ] } ], "directed": false, "chosen": [ 4, 5, 8 ], "visited": [], "result": 0, "output": [] }Step 4: Delaunay complete: 5 CCW triangles; zero incircle ties retain existing edges.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4 ], "active": [], "kind": "graph", "points": [ [ -5, -3 ], [ 5, -3 ], [ 0, 5 ], [ -1, 0 ], [ 2, 1 ] ], "nodeLabels": [ "P0 (-5, -3)", "P1 (5, -3)", "P2 (0, 5)", "P3 (-1, 0)", "P4 (2, 1)" ], "polygons": [ { "indices": [ 0, 1, 3 ], "color": [ 0.18, 0.4, 0.52 ] }, { "indices": [ 0, 3, 2 ], "color": [ 0.18, 0.4, 0.52 ] }, { "indices": [ 1, 2, 4 ], "color": [ 0.18, 0.4, 0.52 ] }, { "indices": [ 1, 4, 3 ], "color": [ 0.18, 0.4, 0.52 ] }, { "indices": [ 2, 3, 4 ], "color": [ 0.18, 0.4, 0.52 ] } ], "directed": false, "chosen": [], "visited": [], "result": 5, "output": [ 0, 1, 3, 0, 3, 2, 1, 2, 4, 1, 4, 3, 2, 3, 4 ] }
Expected final state
Delaunay complete: 5 CCW triangles; zero incircle ties retain existing edges.
Complexity and input bounds
Family: Geometry. Time complexity: O(n^2) setup plus bounded naive edge-flip scans.
Implementation detail: Zero through ten integer sites -10..10 in downloads; the UI accepts at least one. Duplicate coordinates use first original indices. Every orientation/incircle product fits signed 32-bit arithmetic; no artificial supertriangle or floating predicate is used. Return triangle count and write CCW original-index triples, rotated to minimum index then sorted lexicographically; 48 output integers suffice. Invalid input returns -1 without writes, and a guarded construction failure is -2. Independent BigInt empty-circle enumeration checks general-position data, with hand-specified cocircular hull fans and boundary/interior insertion fixtures.
Space complexity: O(n) working triangles and index buffers for the fixed n<=10 contract, excluding saved frames.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1..10 integer points x,y separated by ;, coordinates -10..10. Duplicate points use first original indices. Empty-circumcircle and orientation predicates are exact bounded integers; cocircular edges are retained.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Keep triangle orientation consistent when evaluating incircle signs. Remove duplicate sites, split both sides of an interior insertion edge, and preserve existing edges on cocircular zero determinants. Collinear sites have no triangular faces.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | // Delaunay triangulation via convex-hull fan, lexicographic non-hull site insertion and strict incircle edge legalization. n 0..10 integer sites -10..10; duplicates use first original indices. Exact signed-32-bit-safe orientation/incircle products; no supertriangle or floating geometric predicates. Cocircular zero determinants retain existing edges. Return triangle count and write CCW original-index triples, each rotated to smallest index and sorted lexicographically. Capacity 48 integers suffices. Collinear/fewer-than-three-unique inputs return 0. Invalid inputs return -1 without writes; guarded construction failure returns -2 (not expected for validated bounded inputs). Input coordinates unchanged. O(n^2) setup with naive bounded triangle-pair legalization scans, not an O(n log n) production implementation. O(n) triangle/scratch storage for fixed n<=10. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. 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++; } else { nextCount = 0; for (let i = 0; i < count; i++) { if ((ta[i] == edgeU || tb[i] == edgeU || tc[i] == edgeU) && (ta[i] == edgeV || tb[i] == edgeV || tc[i] == edgeV)) { third = ta[i]; if (third == edgeU || third == edgeV) { third = tb[i]; } if (third == edgeU || third == edgeV) { third = tc[i]; } nextA[nextCount] = edgeU; nextB[nextCount] = point; nextC[nextCount] = third; if (((x[point]-x[edgeU])*(y[third]-y[edgeU])-(y[point]-y[edgeU])*(x[third]-x[edgeU])) < 0) { nextB[nextCount] = third; nextC[nextCount] = point; } nextCount++; nextA[nextCount] = point; nextB[nextCount] = edgeV; nextC[nextCount] = third; if (((x[edgeV]-x[point])*(y[third]-y[point])-(y[edgeV]-y[point])*(x[third]-x[point])) < 0) { nextB[nextCount] = third; nextC[nextCount] = edgeV; } nextCount++; } else { nextA[nextCount] = ta[i]; nextB[nextCount] = tb[i]; nextC[nextCount] = tc[i]; nextCount++; } } count = nextCount; for (let i = 0; i < count; i++) { ta[i] = nextA[i]; tb[i] = nextB[i]; tc[i] = nextC[i]; } } } changed = 1; while (changed != 0) { changed = 0; for (let i = 0; i < count && changed == 0; i++) { for (let j = i+1; j < count && changed == 0; j++) { shared = 0; u = -1; v = -1; oppositeA = -1; oppositeB = -1; vertices[0] = ta[i]; vertices[1] = tb[i]; vertices[2] = tc[i]; for (let k = 0; k < 3; k++) { point = vertices[k]; if (point == ta[j] || point == tb[j] || point == tc[j]) { if (shared == 0) { u = point; } else { v = point; } shared++; } else { oppositeA = point; } } if (shared != 2) { continue; } oppositeB = ta[j]; if (oppositeB == u || oppositeB == v) { oppositeB = tb[j]; } if (oppositeB == u || oppositeB == v) { oppositeB = tc[j]; } if (((x[oppositeB]-x[oppositeA])*(y[u]-y[oppositeA])-(y[oppositeB]-y[oppositeA])*(x[u]-x[oppositeA]))*((x[oppositeB]-x[oppositeA])*(y[v]-y[oppositeA])-(y[oppositeB]-y[oppositeA])*(x[v]-x[oppositeA])) >= 0) { continue; } a = ta[i]; b = tb[i]; c = tc[i]; ax = x[a]-x[oppositeB]; ay = y[a]-y[oppositeB]; bx = x[b]-x[oppositeB]; by = y[b]-y[oppositeB]; cx = x[c]-x[oppositeB]; cy = y[c]-y[oppositeB]; determinant = (ax*ax+ay*ay)*(bx*cy-by*cx)-(bx*bx+by*by)*(ax*cy-ay*cx)+(cx*cx+cy*cy)*(ax*by-ay*bx); if (determinant > 0) { ta[i] = oppositeA; tb[i] = oppositeB; tc[i] = u; if (((x[oppositeB]-x[oppositeA])*(y[u]-y[oppositeA])-(y[oppositeB]-y[oppositeA])*(x[u]-x[oppositeA])) < 0) { tb[i] = u; tc[i] = oppositeB; } ta[j] = oppositeB; tb[j] = oppositeA; tc[j] = v; if (((x[oppositeA]-x[oppositeB])*(y[v]-y[oppositeB])-(y[oppositeA]-y[oppositeB])*(x[v]-x[oppositeB])) < 0) { tb[j] = v; tc[j] = oppositeA; } changed = 1; } } } } for (let i = 0; i < count; i++) { a = ta[i]; b = tb[i]; c = tc[i]; if (b < a && b < c) { ta[i] = b; tb[i] = c; tc[i] = a; } else if (c < a && c < b) { ta[i] = c; tb[i] = a; tc[i] = b; } } for (let i = 1; i < count; i++) { keyA = ta[i]; keyB = tb[i]; keyC = tc[i]; cursor = i-1; while (cursor >= 0 && (ta[cursor] > keyA || (ta[cursor] == keyA && (tb[cursor] > keyB || (tb[cursor] == keyB && tc[cursor] > keyC))))) { ta[cursor+1] = ta[cursor]; tb[cursor+1] = tb[cursor]; tc[cursor+1] = tc[cursor]; cursor--; } ta[cursor+1] = keyA; tb[cursor+1] = keyB; tc[cursor+1] = keyC; } for (let i = 0; i < count; i++) { output[3*i] = ta[i]; output[3*i+1] = tb[i]; output[3*i+2] = tc[i]; } return count; } |
Source
Primary triangulation-flip research and an authoritative Delaunay reference. The playground builds a hull fan and inserts sites before strict edge legalization, using exact bounded integer predicates and explicit cocircular ties; this is not a production optimal-time implementation.
- Transforming triangulations
Charles L. Lawson (1972). Research paper. - Computational Geometry
Mark de Berg; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Reference book.