Capturing an idea of a potential performance improvement: currently we use a fixed hash table size for the hull — sqrt(n). This generally works very well, but can be too low for certain kinds of input where hull sizes tend to be big.

For optimal performance, hash size should depend on the size of the convex hull, but we don't know that size beforehand. So what we could try to do is to reinitialize the hash from scratch multiple times during triangulation, adjusting it to the hull size. If we don't do it often (e.g. once per 1000 processed points), it shouldn't have a noticeable overhead.

There are cases when the euclidean voronoi looks too raw. It would be wonderful to be able to generate Manhattan variant in such cases.

That's very minor, yet, may discourage users who are new to this excellent library and wants to evaluate it.

What I did with the first example:

const coords = [168,180, 168,178, 168,179, 168,181, 168,183, ...];

const delaunay = new Delaunator(coords);
console.log(delaunay.triangles);
// [623, 636, 619,  636, 444, 619, ...]

was to make it runnable by changing:

const coords = [168,180, 168,178, 168,179, 168,181, 168,183];

and to my surprise this yielded no triangles.
Having a second look I found that all the points are on the same line so, indeed, no triangulation can be done.

Changing example shouldn't be hard but may save some time for new users, the time I have just wasted...

Thanks you for exceptional library, much appreciated!

Hi,

Instead of using circle, isn't it faster to compute digonals distances ?

If the triangles are ABC and BCD.
The delaunay edge is the shorter of BC and AD, right ?

It may be faster to compute BC and AD magnitude and get the shorter one instead of computing the whole circle stuff.

It seems that in certain situation the hull is incorrect. See the attached demo for the behaviour we encountered.

In our case, we have solved the issue by doubling the hashSize.

Example html.
demo.zip

Hi. Firstly thanks for this library. I ported it to python before. https://github.com/HakanSeven12/Delaunator-Python

I want to use it for a cad program module. But I need some extra functions like:

• Add point
• Delete point
• Swap edge
• Add a polylines( and swap edges to make triangulation compatible with polylines)
• Delete triangle by selecting an edge and retriangulate this new hole
• Add a border
• Paste a triangulation to another one(pasted triangulation must be dominant)

If you can help me I will be very happy.

java version url is https://github.com/waveware4ai/delaunator-java

can you append a delaunator port lists ?

have a nice day :-)

While I am by no means an expert on Javascript, I am a bit puzzled by the design of the built Delaunator files. Maybe I'm missing something obvious here.

I am making an offline application, so I need to download and store the libraries I'm using. I'm not using NPM or any other package manager, I'm trying to keep things simple for now.

Let's take Three.js as an example. I can simply download three.module.min.js, store this in a folder called three (along with its license, of course), and then simply do (in my javascript code)
import * as THREE from './three/three.module.min.js';

This is extremely convenient because

1. It works
2. VS Code understands what you're doing and can autocomplete etc.

For Delaunator, however, the same approach does not work.
I can either do
import './delaunator/delaunator.min.js';
which works in the browser, but not in VS Code (it has no idea that Delaunator is a thing)
or I can do
import * as Delaunator from './delaunator/delaunator.min.js';
which VS Code understands perfectly, but doesn't work in the browser. In Chrome, it gets imported as a module object, and I see no obvious way to access the actual Delaunator class from it.

Is there a good reason to design the .js file like this? Am I missing something obvious in how to get both VS Code to understand what's going on, and making it work in a browser as well?

Thanks for making an awesome and fast library!

This is beautiful math and I've been admiring the algorithm for hours now. Thanks so much for writing this wonderful code.

Ricardo Matias created a Kotlin port of Delaunator, would be nice to have a link to it in the README.

I myself ported that port to Java for my own use. I haven't published that on any repo yet, so not sure if that's worth linking to in the README.

For example, note the missing edge here:

It seems you can avoid some of these cases by introducing surrounding points, e.g.,

Live test case in Observable:

https://beta.observablehq.com/d/02bcb6fb83d7e33f

Hi there,

I have a pseudo quadtree geometry (THREE.BufferGeometry) set by a series of points.

Each partition has to be rendered through its own draw call by geometry.addGroup() method and individual material. Everything works fine.

However, for my own purposes, I have to use your Delaunator.JS to process original geometry and it seems that output has another indexing for triangles (faces) starting from center.

So, is there a way to rearrange faces back to original indexing, so I could get the same result as my first image with similar multiple draw calls?

I'm not asking for tweaking your Delanuator.JS code but for some hints.

What do you think of a len read limit, so the input array buffer doesn't need to resize itself all the time?

I want to draw the polygon data from the subunits.json file obtained from Natural Earth, but it's not triangulating correctly and not drawing. However, earcut is drawing geojson data.

I do suggest the following change in forEachTriange (the version on the website does only provide one coordinate (and even the wrong one), this version returns both x and y coordinates:

function forEachTriangle(points, delaunay, callback) {
  for (let t = 0; t < delaunay.triangles.length / 3; t++) {
    callback(t, pointsOfTriangle(delaunay, t).map(p => [points[2*p],points[2*p+1]]));
  }
}

My program works in steps: I update the set S of 2D points, and then I need a triangulation of S. Your library works well, but it is a bit too slow for my case.

In each step, I update only a small subset of points of S (they usually lie in a circle). I was thinking, that maybe I could compute a triangulation for this subset of S, and then, combine it with an old triangulation of the whole S.

Do you think your library could be extended in this way?

Here's a set of points that causes a test in tests.js to fail. Are collinear points a problem? I tried adding Math.random() to each point and this test still fails.

tape("delaunator: properly connected halfedges", function(t) {
    let points = [[122,270],[181,121],[195,852],[204,694],[273,525],[280,355],[31,946],
                         [319,938],[33,625],[344,93],[369,793],[38,18],[426,539],[454,239],
                         [503,51],[506,997],[516,661],[532,386],[619,889],[689,131],[730,511],
                         [747,750],[760,285],[856,83],[88,479],[884,943],[927,696],[960,472],
                         [992,253]];
    var d = new Delaunator(points);
    for (var i = 0; i < d.halfedges.length; i++) {
        var i2 = d.halfedges[i];
        if (i2 !== -1 && d.halfedges[i2] !== i) {
            t.fail('invalid halfedge connection');
        }
    }
    t.pass('halfedges are valid');
    t.end();
});

Hello, I am tempted to convert this library to work with 3D points and graphs.
I looked over index.js and managed to understand most of the parts.
Main difficulties are with the hull aspects hullNext, hullPrev, hullTri, hullHash, etc and a little with _legalize , I imagine these 2 are kind of core functionality so should be much better understanded.

Contents of _hashKey I also do not understand, but as it is a 2 value hash function, i can just use a slower Map and call it a day. This way i can ignore pseudoAngle also.
Most 2d functions can be implemented in 3d or have variants in robust-predicates : dist, inCircle (use insphere), circumradius, circumcenter, orient2d (use orient3d).

I think most difficulties will rise from the increasing hull; in 2D, a new point results in a new triangle, but in 3D it could result in ~3 new triangles depending on neighbors.

Will start also to check delaunay-triangulate as it has a 3D delaunay implementation, but feel like delaunator is a better starting point since it is more used and maintained.

My motivation for doing this is mostly for procedurally generating points on a sphere (planet) , but feel that the way I am combining point generation, running d3-geo-voronoi, computing a graph with dijkstra and then drawing with THREE.js
I am wasting a lot of time with arrays and conversions.
I'm content with the possibility of this topic being too advanced for my skillset and just drop the port.

Lloyd's Algorithm works by repeatedly moving generators of a Voronoi diagram to their center of mass and re-computing the diagram.

This is is used in many contexts, but a fun one is Secord's stippling algorithm - Mike Bostock has a notebook here.

This requires creating a new diagram from scratch each time. So far so good. However, that also comes with allocating nine typed arrays each iteration:

    constructor(coords) {
        const n = coords.length >> 1;

        /* ... */

        const maxTriangles = 2 * n - 5;
        const triangles = this.triangles = new Uint32Array(maxTriangles * 3);
        const halfedges = this.halfedges = new Int32Array(maxTriangles * 3);

        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 = new Int32Array(this._hashSize).fill(-1); // angular edge hash

        // populate an array of point indices; calculate input data bbox
        const ids = new Uint32Array(n);

        /* ... */

        const dists = new Float64Array(n);

        /* ... */

        this.hull = new Uint32Array(hullSize);
        /* ... */
    }

Now, the this.hull one is pretty small, so let's just pretend it compensates for the -5 in the maxTriangles calculation. Then for n points, we allocate the equivalent of Uint32Array(10*n) + Int32Array(6*n + Math.sqrt(n)) + Float64Array(n). For a single allocation this is not a big deal, but I want to hook up that Voronoi stippling algorithm to my webcam. At 60FPS, you start to notice this!

And when using Lloyd's Algorithm the number of coordinates remains the same anyway, so it would make a lot more sense to just re-use those arrays.

A hypothetical update() function would be almost identical to the currentt contructor, except it would have to check if the new coords is the same length as the old one, and then it would reset all typed arrays with TypedArray.prototype.fill(0).

Perhaps there is a preference for Delaunator to remain immutable. Well, then one could make a MutableDelaunator class, no?

Would be great to turn this into an ES6 module:
export default function Delaunator(points, getX, getY) {
Takes some overhead with roll-up and forces you to make a dist as well for now but makes it future proof (and for me easier to integrate ;-)

I can make a PR if interested.

hi,

I made a C# version of delaunator but I have the following error with large vertex count. Does it happen to you too ?
the error :

index parameter is out of range : -128 -2,147484E+09

so key is -2,147484E+09
and aze is -128

at lines 190 in your code

The code
` key = hashKey(x, y);
for (int j = 0; j < hashSize; j++)
{
try
{
aze = (int)Math.Round((key + j) % hashSize);
start = hullHash[aze];

				}
				catch(IndexOutOfRangeException ex)
				{
					// Set IndexOutOfRangeException to the new exception's InnerException.
					Debug.LogError("index parameter is out of range : " + aze + " " + key);
					throw new ArgumentOutOfRangeException("index parameter is out of range : " + aze, ex);
				}

				if (start != -1 && start != hullNext[start]) break;
			}

`

EDIT : I am using float coords instead of int, maybe it breaks the hash code.
EDIT 2 : I made some tests with only 1000 vertices and it happens too frome time to time, again with E+09 float hash.

when I try to build the project it fails with this message:

Failed to minify the code from this file: 

 	./node_modules/delaunator/index.js:4 

After triangulation, should the hull contain edge indices that have no twins? This doesn't seem to be the case for delaunator-cpp, so I am wondering whether that is a mistake there, or if it's something that's also unsupported by the original code.

What to do when this happen :

// don't worry about hitting the cap: it can only happen on extremely degenerate input
EDGE_STACK[i++] = br;

thanks

Take circumference points:

[[4,1],[3.7974166882130675,2.0837249985614585],[3.2170267516619773,3.0210869309396715],[2.337215067329615,3.685489874065187],[1.276805078389906,3.9872025288851036],[0.17901102978375127,3.885476929518457],[-0.8079039091377689,3.3940516818407187],[-1.550651407188842,2.5792964886320684],[-1.9489192990517052,1.5512485534497125],[-1.9489192990517057,0.44875144655029087],[-1.5506514071888438,-0.5792964886320653],[-0.8079039091377715,-1.394051681840717],[0.17901102978374794,-1.8854769295184561],[1.276805078389902,-1.987202528885104],[2.337215067329611,-1.6854898740651891],[3.217026751661974,-1.021086930939675],[3.7974166882130653,-0.08372499856146409]]

With delaunay-triangulate we get hull:

Vertices:

[2,1,0,16,15,0,15,2,0,3,2,15,14,13,15,4,3,5,5,3,15,13,12,15,6,5,7,7,5,15,12,10,15,11,10,12,9,8,7,9,7,15,10,9,15]

With delanuator we get broken image:

Vertices:

[15,2,1,2,5,1,5,15,1,0,16,1,5,3,2,9,5,2,15,9,2,15,12,9,5,4,3,15,14,12,9,8,6,12,10,9,8,7,6,14,13,12,12,11,10]

Is that expected behavior? (for me no)

Hi, I am trying to refactor your code into Swift, and am running into an issue. Is it possible your quicksort algorithm is not working as intended? I run into issues with the following set of blue noise points (but other sets of points also fail, either not sorting or not triangulating); your code triangulates successfully only 3 out of 4 times or so. I am still pulling my hair out wondering whether it is my code... could someone verify with this simple set of points?

coords = [12.0, 100.0, 181.0, 13.0, 72.0, 7.0, 274.0, 23.0, 133.0, 13.0, 153.0, 66.0, 248.0, 71.0, 56.0, 59.0, 97.0, 98.0, 207.0, 86.0, 496.0, 9.0, 546.0, 1.0, 427.0, 23.0, 384.0, 7.0, 332.0, 20.0, 507.0, 62.0, 450.0, 94.0, 578.0, 102.0, 364.0, 61.0, 317.0, 103.0, 400.0, 106.0];

According to my test output, your quicksort sorts these coords in ids into this order (which shows the point number, and the dist() function result to cx/cy:
3:=1371.25
19:=2934.25
14:=2491.25
18:=4817.25
9:=8800.25
13:=10083.25
20:=13781.25
1:=14636.25
5:=20320.25
12:=18354.25
16:=25665.25
4:=27884.25
8:=41184.25
10:=42381.25
15:=45016.25
2:=51891.25
7:=57151.25
11:=65757.25
0:=82251.25
17:=82441.25

Conforming or constrained triangulation would be utter-cool. Input can be points, lines and polygons while output edges will not cross existing input edges. Conforming would introduce new points in order to be true delaunay triangles (steiner points) while constrained is not always truely delaunay but doesn't introduce extra points.

Relevant information:

• http://www.cs.cmu.edu/~quake/triangle.defs.html#conform
• http://www.cs.cmu.edu/~quake/triangle.delaunay.html
• http://lin-ear-th-inking.blogspot.nl/2009/04/delaunay-triangulation-in-jts-111.html

I was about to ask if there existed any C++ ports, then I realized I hadn't searched on the internet yet, found this Rust port announcement, which alongside the Rust version mentioned Go and C++ ports.

It's just a small thing, so I'll just do a quick edit in the Github page and submit a pull request :). Give me a sec

EDIT: Wait, they're already mentioned. Ok, slight rewrite to make it easier to notice them then ;)

@mourner - I'm seeing different results for the same set of points when upgrading from 1.0.0 to 1.0.3. My use case is a bit weird as I'm iteratively adding points, but it's a deterministic process and upgrading has resulted in a change. Is this expected?

Reading through the commits I don't see anything that seems to imply an intentional change. If this is unexpected, I'll spend some time to create a dataset that reproduces the result.

Delaunator.from([])
Uncaught RangeError: Invalid typed array length: -15

Delaunator.from([[1,2])
Uncaught RangeError: Invalid typed array length: -9

Delaunator.from([[1,2],[2,3]])
Uncaught RangeError: Invalid typed array length: -3

I suppose more clear message would be Uncaught Error: No Delaunay triangulation exists for this input.

(Well, actually I am not sure that Delaunator should throw this error as there are more simple ways to process such cases, see #46)

How to get hull's halfedges ? Is there anything to get them directly or must I check all edges around hull's points ?
I need this to close the triangulation on a sphere. The last triangles are made with a pole in sterographic projection connected to each hull's edge. This pole/point is removed before running delaunator then added after and so all new triangles with this new point.

hull give points but hulltri, hullhash, hullnext and hullprev are not related to hull's actual edges.

Shouldn't be too much work to extend Delaunator to calculate a Voronoi diagram after triangulation.

I want to get a voronoi centroid outlines as hull edges.
how can I do ???

I see in the code that the initial triangle is counter-clockwise, and two of the referenced papers mention that all the triangles will be counter-clockwise, but does your algorithm also guarantee that? (If so, that'd be handy to put in the readme.)

I was just wondering what the complexity of the code is, it'd be a great help.

Hi,
First I just wanted to say that this is great library! I found an issue where delaunator gets stuck in an infinite loop. This bug seems to affect JavaScript and C++ delaunator. Attached is the zip file containing a json file of the points that reproduce the issue. The loop occurs somewhere starting in this for loop: https://github.com/mapbox/delaunator/blob/master/index.js#L147

error.zip

I'll try to look into it myself later. Thanks!

const points = [[-500, 0], [0, 500], [500, 0], [1000, 500], [1500, 0]];
 
const delaunay = Delaunator.from(points);
console.log(delaunay.triangles);
console.log(delaunay.halfedges);

Uint32Array(9) [2, 0, 1, 1, 3, 2, 3, 4, 2]
Int32Array(9) [-1, -1, 5, -1, 8, 2, -1, -1, 4]

I can't make sense out of those numbers console.log(delaunay.halfedges)

Any help appreciated!

Implemented Typescript Definition for this library via PR DefinitelyTyped/DefinitelyTyped#17811

Close this issue if everything looks 👍

CC: @mourner

Any php port ??

If polygon not convex (concave), delanuator put in answer also triangles out of border of polygon, so need some check.
How to do that in code?

@redblobgames I'm wondering whether we could drop the script { display: block; } hack — while it's definitely cool, it has some drawbacks:

• We can't add code highlighting to the code (e.g. with https://highlightjs.org/), which would help docs readability a lot.
• We have to split the code into two files entangled together, which makes refactoring inconvenient.
• It's impossible to lint it in CI (because variable contexts are different between script blocks — it doesn't consider cross-script globals).

Input data are not always guaranteed to have delaunay solution, and there is no way to verify it other then call Delaunator.

But in this case Delaunator throws error, so to process this call correctly we have to wrap it into try/catch, which is not obvious, not documented, and not convenient.

I suppose that we do not need this error at all, 'cause there is more simple way to get the same info: empty output arrays.

Using "https://unpkg.com/[email protected]/delaunator.js"
I am converting the code to another system. It works in the Chrome but not in the other system. What is missing ?
///////////////////////////////////////////////////
TypeError: undefined is not a constructor (evaluating 'new Int32Array(this._hashSize).fill(-1)')

moi://appdata/nodeeditor2/nodes/extensions/delaunator.js line 26

22: this._hashSize = Math.ceil(Math.sqrt(n));
23: this._hullPrev = new Uint32Array(n); // edge to prev edge
24: this._hullNext = new Uint32Array(n); // edge to next edge
25: this._hullTri = new Uint32Array(n); // edge to adjacent triangle
26: >> this._hullHash = new Int32Array(this._hashSize).fill(-1); // angular edge hash
27:
28: // temporary arrays for sorting points
29: this._ids = new Uint32Array(n);
30: this._dists = new Float64Array(n);
/////////////////////////////////////////////////////////

I was poking at the idea of dynamically creating a mesh in 3D space based off points hovering around a sphere.

Delaunator is only designed for 2D, so I used longitude/latitude in place of x/y (I'm pretty sure that this is going to cause problems at the trigonomic boundaries, but for starters, I'm experimenting with it). The resulting triangles looked good until I converted the points from longitude/latitude (x/y) into XYZ around my sphere and rendered the points in 3D space (using ThreeJs with React and built with Vite).

It looks fine head-on:

But move the camera to the side and there are very clearly extra triangles from one side of the rectangle to the other:

I didn't expect those extra triangles. I was expecting the minimal number of triangles to form a rectangle. Will the algorithm still form triangles even if the angle between adjacent points is ~180 degrees? Should a triangle be abandoned if the circumcircle is too large? Or maybe I'm not understanding the subtleties and quirks of the particular algorithm being used here.

Please advise.

Here's the section of the program that forms this test rectangle (extracted and simplified from earlier testing). If you'd like to see the entire program, let me know and I'll put together a branch.

import { useEffect, useRef, useState } from "react"
import * as THREE from "three"
import Delaunator from "delaunator"

function ConvertLatLongToXYZ(lat, long, sphereRadius) {
  let latRad = (lat / 180.0) * Math.PI
  let longRad = (long / 180.0) * Math.PI

  let projectionOfRadiusOntoXZPlane = sphereRadius * Math.cos(latRad)
  let x = Math.sin(longRad) * projectionOfRadiusOntoXZPlane
  let y = Math.sin(latRad) * sphereRadius
  let z = Math.cos(longRad) * projectionOfRadiusOntoXZPlane

  return [x, y, z,]
}

export function Region() {
  const meshRef = useRef()
  useEffect(() => {
    // Testing
    let testLongLatArr = [
      [34.99902026115871, -5.311780837060211],
      [34.382157360924246, -8.247675958196918],
      [35.61588316139318, -2.375885715923504],
      [31.966457021422954, -4.674606933353613],
      [31.34959412118849, -7.61050205449032],
      [32.58331992165742, -1.7387118122169052],
      [28.933893781687196, -4.037433029647014],
      [28.31703088145273, -6.973328150783721],
      [29.550756681921662, -1.1015379085103068],
      [25.901330541951438, -3.4002591259404156],
      [25.284467641716972, -6.336154247077123],
      [26.518193442185904, -0.4643640048037081],
      [22.86876730221568, -2.763085222233817],
      [22.251904401981214, -5.698980343370524],
      [23.485630202450146, 0.17280989890289034],
      [19.836204062479922, -2.1259113185272183],
      [19.219341162245456, -5.0618064396639255],
      [20.453066962714388, 0.809983802609489],
      [16.803640822744164, -1.4887374148206196],
      [16.186777922509698, -4.424632535957327],
      [17.42050372297863, 1.4471577063160876],
      [13.771077583008406, -0.851563511114021],
      [13.15421468277394, -3.787458632250728],
      [14.387940483242872, 2.0843316100226863],
      [10.738514343272648, -0.21438960740742274],
      [10.121651443038182, -3.15028472854413],
      [11.355377243507114, 2.7215055137292845],
      [7.7059511035368935, 0.42278429629917547],
      [7.089088203302428, -2.513110824837532],
      [8.32281400377136, 3.3586794174358827],
      [4.6733878638011355, 1.0599582000057746],
      [4.05652496356667, -1.8759369211309327],
      [5.290250764035601, 3.995853321142482],
      [1.6408246240653739, 1.6971321037123728],
      [1.023961723830908, -1.2387630174243345],
      [2.2576875242998398, 4.63302722484908],
      [-1.3917386156703841, 2.334306007418972],
      [-2.00860151590485, -0.6015891137177354],
      [-0.7748757154359183, 5.270201128555679],
      [-4.424301855406142, 2.971479911125571],
      [-5.041164755640608, 0.03558478998886372],
      [-3.8074389551716763, 5.907375032262278],
      [-7.4568650951419, 3.608653814832169],
      [-8.073727995376366, 0.6727586936954619],
      [-6.840002194907434, 6.544548935968876],
      [-10.489428334877658, 4.245827718538767],
      [-11.106291235112124, 1.3099325974020601],
      [-9.872565434643192, 7.181722839675475],
      [-13.521991574613416, 4.883001622245366],
      [-14.138854474847882, 1.9471065011086583],
      [-12.90512867437895, 7.818896743382073],
      [-16.554554814349167, 5.520175525951964],
      [-17.171417714583633, 2.5842804048152566],
      [-15.937691914114701, 8.456070647088671]
    ]

    let pointsArr = []
    testLongLatArr.forEach((longLat) => {
      let lat = longLat[1]
      let long = longLat[0]
      let sphereRadius = 10
      const [x, y, z] = ConvertLatLongToXYZ(lat, long, sphereRadius)
      pointsArr.push(x, y, z)
    })

    // let expectedIndicesArr = [24, 21, 25, 21, 22, 25, 24, 26, 21, 26, 23, 21, 18, 19, 22, 28, 27, 24, 24, 27, 26, 25, 28, 24, 18, 22, 21, 22, 19, 25, 25, 19, 28, 23, 18, 21, 27, 29, 26, 26, 29, 23, 30, 29, 27, 23, 20, 18, 29, 20, 23, 28, 30, 27, 28, 31, 30, 19, 31, 28, 18, 16, 19, 15, 16, 18, 20, 15, 18, 35, 32, 30, 30, 32, 29, 29, 17, 20, 20, 17, 15, 53, 17, 29, 31, 33, 30, 37, 34, 31, 31, 34, 33, 16, 13, 19, 15, 13, 16, 12, 13, 15, 17, 12, 15, 33, 35, 30, 17, 14, 12, 12, 10, 13, 34, 37, 33, 33, 36, 35, 19, 37, 31, 37, 36, 33, 13, 10, 19, 9, 10, 12, 14, 9, 12, 36, 38, 35, 35, 38, 32, 17, 11, 14, 14, 11, 9, 9, 7, 10, 37, 39, 36, 36, 41, 38, 6, 7, 9, 19, 40, 37, 37, 40, 39, 11, 6, 9, 44, 41, 39, 39, 41, 36, 11, 8, 6, 40, 43, 39, 43, 42, 39, 3, 4, 6, 6, 4, 7, 7, 4, 10, 8, 3, 6, 42, 44, 39, 41, 44, 38, 38, 53, 32, 32, 53, 29, 11, 5, 8, 8, 5, 3, 3, 1, 4, 43, 46, 42, 42, 47, 44, 40, 46, 43, 0, 1, 3, 46, 45, 42, 5, 0, 3, 45, 47, 42, 5, 2, 0, 46, 49, 45, 45, 50, 47, 40, 49, 46, 49, 48, 45, 48, 50, 45, 47, 50, 44, 44, 53, 38, 52, 51, 48, 48, 51, 50, 49, 52, 48, 52, 53, 51, 51, 53, 50, 50, 53, 44, 17, 53, 11]
    const testTypedArr = new Float32Array(testLongLatArr.flat())
    let delaunator = new Delaunator(testTypedArr)
    let indicesArr = delaunator.triangles

    // Create geometry for the points
    let valuesPerVertex = 3
    let valuesPerIndex = 1
    let positionAttribute = new THREE.Float32BufferAttribute(pointsArr, valuesPerVertex)
    let indicesAttribute = new THREE.Uint32BufferAttribute(indicesArr, valuesPerIndex)

    meshRef.current.geometry.setAttribute("position", positionAttribute)
    meshRef.current.geometry.setIndex(indicesAttribute)
  }, [meshRef.current])

  return (
    <>
      <mesh name="IntermediatePointsMesh" ref={meshRef}>
        <meshBasicMaterial color={0x00ff00} side={THREE.DoubleSide} wireframe={true} />
      </mesh>
    </>
  )
}

My x,y points are in flat arrays (e.g. Float32Array), and I want to run Delaunator on them. I think I have two options:

1. I construct a dummy array of indices [0, 1, 2, 3, …] and then pass in getX, getY accessors that use the index to look up the value. This feels silly because Delaunator is constructing the ids array which is exactly what I'm passing in.
2. I convert my flat array to a nested array and don't use getX, getY accessors. This also feels silly because I'm converting my flat array to a nested array and then Delaunator is converting the nested array back to a flat array coords, which is exactly the same as what I started with.

Now, it may be that this doesn't really matter, and I should just convert the data to the format Delaunator needs. But I also wonder if there's a clean way to separate the input-conversion part of the Delaunator() function (ids, coords, points.length) from the part of the code that runs the algorithm, so that I could skip the conversion process.

Note:
A more thorough introduction is here in the original issue at delaunator-cpp .

I am processing point clouds around the size of 100 k to 1.000 k Points. The points' outer hull is a near perfect rectangle and their distribution is grid like. In pre-processing the point cloud gets slightly tilted towards a plane for error compensation.

While I have not yet observed the issue below in our raw data, occasionally there was a number of big triangles (hundreds in a cloud of a million points) spanning across the whole pre-processed (tilted) point cloud. To reproduce this, I wrote a test. It generates simple square grid, rotates it by a few degrees and then calls delaunator to triangulate.

I have ported my test from C++ to JS by modifying your demo (Forgive me, it is my first JS ever).
Erroneous grids get dumped to console. You can rotate the grid by moving the mouse left or right on the canvas. Uncomment the "Test loop" bit to automatically iterate over 10.000 test cases. One grid that fails validation is at 302.328° rotation (Firefox 74.0, 64-bit, Win10):

points = [[-3.0381276552207055, 10.481881920449052], [-2.1931270567413446, 11.016647278872279], [-1.3481264582619854, 11.551412637295508], [-0.5031258597826245, 12.086177995718735], [0.3418747386967347, 12.620943354141964], [1.1868753371760938, 13.155708712565193], [-2.5033622967974765, 9.63688132196969], [-1.6583616983181173, 10.171646680392918], [-0.8133610998387582, 10.706412038816147], [0.03163949864060278, 11.241177397239376], [0.8766400971199619, 11.775942755662605], [1.721640695599322, 12.310708114085832], [-1.9685969383742474, 8.791880723490332], [-1.1235963398948883, 9.326646081913559], [-0.2785957414155291, 9.861411440336788], [0.5664048570638318, 10.396176798760017], [1.411405455543191, 10.930942157183246], [2.25640605402255, 11.465707515606473], [-1.4338315799510184, 7.9468801250109715], [-0.5888309814716592, 8.4816454834342], [0.2561696170076999, 9.016410841857429], [1.10117021548706, 9.551176200280658], [1.94617081396642, 10.085941558703885], [2.791171412445779, 10.620706917127112], [-0.8990662215277911, 7.1018795265316115], [-0.05406562304843021, 7.6366448849548405], [0.7909349754309281, 8.17141024337807], [1.635935573910288, 8.706175601801297], [2.4809361723896473, 9.240940960224526], [3.3259367708690073, 9.775706318647753], [-0.3643008631045621, 6.256878928052252], [0.48069973537479704, 6.7916442864754805], [1.3257003338541562, 7.326409644898709], [2.1707009323335162, 7.861175003321938], [3.0157015308128763, 8.395940361745165], [3.8607021292922354, 8.930705720168394]];

Although the error is similar, it does occur under different rotation angles under C++ and JS. Also, @abellgithub had at first not been able to recreate the error under OSX. I suppose the difference lies in different function implementations in the standard libraries, e.g. for sine and cosine that lead to different rounding errors.