npm package: @lempf/rita
Description: 2D and 3D Randomized Incremental Triangulation Algorithms
Latest version: 0.2.2

# rita - Randomized Incremental Triangulation Algorithms

[![Crates.io version](https://img.shields.io/crates/v/rita.svg)](https://crates.io/crates/rita)
[![unsafe forbidden](https://img.shields.io/badge/unsafe-forbidden-brightgreen.svg)](https://github.com/glennDittmann/rita/blob/main/src/lib.rs#L12)

An implementation of (randomized) incremental weighted Delaunay triangulations in safe rust.

You can create a two- or three-dimensional Delaunay triangulation, including weighted points, as follows.

## 2D

```rust
let vertices = vec![
    [0.0, 0.0],
    [-0.5, 1.0],
    [0.0, 2.5],
    [2.0, 3.0],
    [4.0, 2.5],
    [5.0, 1.5],
    [4.5, 0.5],
    [2.5, -0.5],
    [1.5, 1.5],
    [3.0, 1.0],
];
let weights = vec![0.2, 0.3, 0.55, 0.5, 0.6, 0.4, 0.65, 0.7, 0.85, 0.35]; // or None

let mut triangulation = Triangulation::new(None); // specify epsilon here
let result = triangulation.insert_vertices(&vertices, Some(weights), true);  // last parameter toggles spatial sorting
```

## 3D
```rust
let vertices = vec![
    [0.0, 0.0, 0.0],
    [-0.5, 1.0, 0.5],
    [0.0, 2.5, 2.5],
    [2.0, 3.0, 5.0],
    [4.0, 2.5, 6.5],
    [5.0, 1.5, 6.5],
    [4.5, 0.5, 5.0],
    [2.5, -0.5, 2.0],
    [1.5, 1.5, 3.0],
    [3.0, 1.0, 4.0],
];
let weights = vec![0.2, 0.3, 0.55, 0.5, 0.6, 0.4, 0.65, 0.7, 0.85, 0.35]; // or None

let mut tetrahedralization = Tetrahedralization::new(None); // specify epsilon here
let result = tetrahedralization.insert_vertices(&vertices, Some(weights), true);  // last parameter toggles spatial sorting
```

The eps parameter is used to perform an approximation technique, which leaves out certain vertices based on epsilon in the incremental insertion process.

:warning: **This is a work in progress.** :warning:
The algorithms work, as test coverage indicates.
However, the code is not yet fully optimized and the API is not yet simplified.
There might be duplicate and unnecessarily complex code.

## Robustness
Robustness is achieved through [geogram_predicates](https://github.com/glenndittmann/geogram_predicates), which itself uses [cxx](https://github.com/dtolnay/cxx) to make the geometric predicates from [geogram](https://github.com/BrunoLevy/geogram) available in `rust`.

## Wasm
In order to have an easy wasm compilable target it is necessary to have a rust only version of this crate. The usage of `geogram_predicates` makes this difficult as its an ffi to the `geogram` c++ library.
The workaround is to have an abstraction layer over the geometric predicates. For normal usage the `geogram_predicates` will be used.
When activating `wasm` the fallback rust-only predicates will be used. The downside of these is that they do not support lifted orientation test, i.e. we can not compute weighted Delaunay triangulations.
For the majority of the use cases however this is fine, and maybe `robust` can be extended in the future to support the weighted predicates as well.

### Building and publishing the WASM package
The name `rita` is already taken on npm, so **pass the scope at build time** so the generated `package.json` gets a scoped name (e.g. `@lempf/rita`). If you build without `--scope`, the package name stays `rita` and publish will try to use the existing npm package.

Build with your npm scope (use `--` so `--no-default-features` and `--features` go to cargo, not wasm-pack):
```bash
wasm-pack build rita --scope lempf --target web -- --no-default-features --features "std,wasm"
```
Then publish (scoped packages require `--access public`):
```bash
cd rita/pkg && npm publish --access=public
```
Install as `npm install @lempf/rita`.

### Usage in web

The WASM build exposes two functions: `triangulate` (2D) and `triangulate3d` (3D). Both accept a flat array of coordinates and an optional `epsilon` (pass `null` to omit).

**2D — triangles**

```javascript
import * as rita from '@lempf/rita';

// Flat array: [x1, y1, x2, y2, ...]
const vertices = [0, 0, 1, 0, 0.5, 1, 0.2, 0.3];
const result = rita.triangulate(vertices, null);

// result.triangles: Array<{ id: string, a: { x, y }, b: { x, y }, c: { x, y } }>
// result.vertices:  Array<{ x, y }>
console.log(result.triangles.length, result.vertices.length);
```

**3D — tetrahedra**

```javascript
import * as rita from '@lempf/rita';

// Flat array: [x1, y1, z1, x2, y2, z2, ...]
const vertices = [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0.5, 0.5, 0.5];
const result = rita.triangulate3d(vertices, null);

// result.tetrahedra: Array<{ id: string, a: { x, y, z }, b, c, d }>
// result.vertices:   Array<{ x, y, z }>
console.log(result.tetrahedra.length, result.vertices.length);
```

**Data structures**

| API            | Input (flat)   | Output                                                                 |
|----------------|----------------|------------------------------------------------------------------------|
| `triangulate`  | `[x, y, ...]`  | `{ triangles: [{ id, a, b, c }], vertices: [{ x, y }] }`              |
| `triangulate3d`| `[x, y, z, ...]` | `{ tetrahedra: [{ id, a, b, c, d }], vertices: [{ x, y, z }] }`     |

Corner fields `a`, `b`, `c` (and `d` for 3D) are vertex objects with `x`, `y` and optionally `z`. At least 3 points are required for 2D and 4 for 3D.
Note: epsilon and weighted triangulations are not yet supported in wasm

## Testing
To make sure both predicate libraries produce the same results tests can be run for both features.

### Testing with geogram_predicates
`cargo test -p rita --features logging`

### Testing with robust
`cargo test -p rita --no-default-features --features "std,wasm"`

## Base implementation
There is decent preliminary work done in the rust eco-system by [Bastien Durix](https://scholar.google.fr/citations?user=Crc4sdsAAAAJ&hl=fr) in the crate [simple_delaunay_lib](https://github.com/Ibujah/simple_delaunay_lib).

We forked this and re-fined by adding
  - weighted triangulations for 2D and 3D
  - adding geograms robust predicates
  - adding novel method: eps-Circles

_Theoretical Concepts_
- extended for 2D weighted delaunay triangulations, which includes
  - the flippability check (check for an edge to be flippable and only then and if it is not regular flip it)
  - the 3->1 flip (with weights come possible redundant points, i.e. points not present in the final triangulation, which are achieved by 3->1 flips)
  - the in_power_circler predicate via geogram_predicates (this is the "in_circle test" for weighted points)
- extend for 3D weighted Delaunay triangulations, which includes
  - adding weights to the general data structure
  - use regular "in-circle" predicates in the appropriate places
  - do not insert redundant vertices

_Code structure_
- reused Node struct, for 3D (instead of duplicating)
- split each struct into own files for better readabilit and maintainability
- implement fmt::Display for structs that had print() or println()
- improved overall readabilit, e.g. by refactoring larger functions, documenting or adding comments
- ...

_Conventions_
- improved overall naming conventions
- applied clippy style guide, e.g. exchanging a lot of if else with match
- align naming in code with literature, i.e. flip namings, data structure namings etc.

_Algorithmic Improvements_
- remove unneccary push of 2 extra edges after 2->2 flip
- remove unused match case in should_flip_hedge()
- early out for match case in should_flip_hedge that always returns false i.e. Flip::None
- exchange geo::robust for geogram_predicates which has the same features plus:
  - perurbation of simplicity
  - arithmetic schemes
- add a naive version of _last inserted triangle_, which speeds up location (especially when using spatial sorting)


_WIP_
- add 3D Flipping Algo (there are just a few edge cases to fix. main work is done)
- extend 3D flipping algo for weighted cases

## Acknowledgements
Thanks to Bastien Durix for his prior work on incremental Delaunay triangulations in rust.