Brunobkr/llama.cpp_AlgMor24_github

1# Delaunator [![CI](https://github.com/mapbox/delaunator/actions/workflows/node.yml/badge.svg)](https://github.com/mapbox/delaunator/actions/workflows/node.yml) [![](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects) [![](https://badgen.net/bundlephobia/minzip/delaunator)](https://unpkg.com/delaunator)2 3An incredibly fast and robust JavaScript library for4[Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) of 2D points.5 6- [Interactive Demo](https://mapbox.github.io/delaunator/demo.html)7- [Guide to data structures](https://mapbox.github.io/delaunator/)8 9<img src="delaunator.png" alt="Delaunay triangulation example" width="600" />10 11### Projects based on Delaunator12 13- [d3-delaunay](https://github.com/d3/d3-delaunay) for Voronoi diagrams, search, traversal and rendering (a part of [D3](https://d3js.org)).14- [d3-geo-voronoi](https://github.com/Fil/d3-geo-voronoi) for Delaunay triangulations and Voronoi diagrams on a sphere (e.g. for geographic locations).15 16## Example17 18```js19const coords = [377,479,  453,434,  326,387,  444,359,  511,389,20                586,429,  470,315,  622,493,  627,367,  570,314];21const delaunay = new Delaunator(coords);22console.log(delaunay.triangles);23// [4,3,1,  4,6,3,  1,5,4,  4,9,6,  2,0,1,  1,7,5,24//  5,9,4,  6,2,3,  3,2,1,  5,8,9,  0,7,1,  5,7,8]25```26 27<img src="docs/example.png" alt="Delaunay triangulation example with labeled points" width="600" />28 29## Install30 31Install with NPM (`npm install delaunator`) or Yarn (`yarn add delaunator`), then import as an ES module:32 33```js34import Delaunator from 'delaunator';35```36 37To use as a module in a browser:38 39```html40<script type="module">41    import Delaunator from 'https://cdn.skypack.dev/delaunator@5.0.0';42</script>43```44 45Or use a browser UMD build that exposes a `Delaunator` global variable:46 47```html48<script src="https://unpkg.com/delaunator@5.0.0/delaunator.min.js"></script>49```50 51## API Reference52 53#### new Delaunator(coords)54 55Constructs a delaunay triangulation object given an array of point coordinates of the form:56`[x0, y0, x1, y1, ...]` (use a typed array for best performance).57 58#### Delaunator.from(points[, getX, getY])59 60Constructs a delaunay triangulation object given an array of points (`[x, y]` by default).61`getX` and `getY` are optional functions of the form `(point) => value` for custom point formats.62Duplicate points are skipped.63 64#### delaunay.triangles65 66A `Uint32Array` array of triangle vertex indices (each group of three numbers forms a triangle).67All triangles are directed counterclockwise.68 69To get the coordinates of all triangles when using `Delaunator.from(points)`, use:70 71```js72for (let i = 0; i < triangles.length; i += 3) {73    coordinates.push([74        points[triangles[i]],75        points[triangles[i + 1]],76        points[triangles[i + 2]]77    ]);78}79```80 81To get the coordinates of all triangles when using `new Delaunator(coords)`, use:82 83```js84for (let i = 0; i < triangles.length; i += 3) {85    coordinates.push([86        [coords[2 * triangles[i]],     coords[2 * triangles[i] + 1]],87        [coords[2 * triangles[i + 1]], coords[2 * triangles[i + 1] + 1]],88        [coords[2 * triangles[i + 2]], coords[2 * triangles[i + 2] + 1]]89    ]);90}91```92 93#### delaunay.halfedges94 95A `Int32Array` array of triangle half-edge indices that allows you to traverse the triangulation.96`i`-th half-edge in the array corresponds to vertex `triangles[i]` the half-edge is coming from.97`halfedges[i]` is the index of a twin half-edge in an adjacent triangle98(or `-1` for outer half-edges on the convex hull).99 100The flat array-based data structures might be counterintuitive,101but they're one of the key reasons this library is fast.102 103#### delaunay.hull104 105A `Uint32Array` array of indices that reference points on the convex hull of the input data, counter-clockwise.106 107#### delaunay.coords108 109An array of input coordinates in the form `[x0, y0, x1, y1, ....]`,110of the type provided in the constructor (or `Float64Array` if you used `Delaunator.from`).111 112#### delaunay.update()113 114Updates the triangulation if you modified `delaunay.coords` values in place, avoiding expensive memory allocations.115Useful for iterative relaxation algorithms such as [Lloyd's](https://en.wikipedia.org/wiki/Lloyd%27s_algorithm).116 117## Performance118 119Benchmark results against other Delaunay JS libraries120(`npm run bench` on Macbook Pro Retina 15" 2017, Node v10.10.0):121 122&nbsp; | uniform 100k | gauss 100k | grid 100k | degen 100k | uniform 1&nbsp;million | gauss 1&nbsp;million | grid 1&nbsp;million | degen 1&nbsp;million123:-- | --: | --: | --: | --: | --: | --: | --: | --:124**delaunator** | 82ms | 61ms | 66ms | 25ms | 1.07s | 950ms | 830ms | 278ms125[faster&#8209;delaunay](https://github.com/Bathlamos/delaunay-triangulation) | 473ms | 411ms | 272ms | 68ms | 4.27s | 4.62s | 4.3s | 810ms126[incremental&#8209;delaunay](https://github.com/mikolalysenko/incremental-delaunay) | 547ms | 505ms | 172ms | 528ms | 5.9s | 6.08s | 2.11s | 6.09s127[d3&#8209;voronoi](https://github.com/d3/d3-voronoi) | 972ms | 909ms | 358ms | 720ms | 15.04s | 13.86s | 5.55s | 11.13s128[delaunay&#8209;fast](https://github.com/darkskyapp/delaunay-fast) | 3.8s | 4s | 12.57s | timeout | 132s | 138s | 399s | timeout129[delaunay](https://github.com/darkskyapp/delaunay) | 4.85s | 5.73s | 15.05s | timeout | 156s | 178s | 326s | timeout130[delaunay&#8209;triangulate](https://github.com/mikolalysenko/delaunay-triangulate) | 2.24s | 2.04s | OOM | 1.51s | OOM | OOM | OOM | OOM131[cdt2d](https://github.com/mikolalysenko/cdt2d) | 45s | 51s | 118s | 17s | timeout | timeout | timeout | timeout132 133## Papers134 135The algorithm is based on ideas from the following papers:136 137- [A simple sweep-line Delaunay triangulation algorithm](http://www.academicpub.org/jao/paperInfo.aspx?paperid=15630), 2013, Liu Yonghe, Feng Jinming and Shao Yuehong138- [S-hull: a fast radial sweep-hull routine for Delaunay triangulation](http://www.s-hull.org/paper/s_hull.pdf), 2010, David Sinclair139- [A faster circle-sweep Delaunay triangulation algorithm](http://cglab.ca/~biniaz/papers/Sweep%20Circle.pdf), 2011, Ahmad Biniaz and Gholamhossein Dastghaibyfard140 141## Robustness142 143Delaunator should produce valid output even on highly degenerate input. It does so by depending on [robust-predicates](https://github.com/mourner/robust-predicates), a modern port of Jonathan Shewchuk's robust geometric predicates, an industry standard in computational geometry.144 145## Ports to other languages146 147- [delaunator-rs](https://github.com/mourner/delaunator-rs) (Rust)148- [fogleman/delaunay](https://github.com/fogleman/delaunay) (Go)149- [delaunator-cpp](https://github.com/abellgithub/delaunator-cpp) (C++)150- [delaunator-sharp](https://github.com/nol1fe/delaunator-sharp) (C#)151- [delaunator-ruby](https://github.com/hendrixfan/delaunator-ruby) (Ruby)152- [Delaunator-Python](https://github.com/HakanSeven12/Delaunator-Python) (Python)153- [torch-delaunay](https://github.com/ybubnov/torch_delaunay) (Python/Torch)154- [ricardomatias/delaunator](https://github.com/ricardomatias/delaunator) (Kotlin)155- [delaunator-java](https://github.com/waveware4ai/delaunator-java) (Java)156- [delaunay-Stata](https://github.com/asjadnaqvi/stata-delaunay-voronoi) (Stata/Mata)157- [Delaunator.jl](https://github.com/JuliaGeometry/Delaunator.jl) (Julia)158