# Crate simplicity[−][src]

Implementation of Simulation of Simplicity by Edelsbrunner and Mücke

Simulation of simplicity is a technique for ignoring
degeneracies when calculating geometric predicates,
such as the orientation of one point with respect to a list of points.
Each point **p**_ *i* is perturbed by some polynomial
in ε, a sufficiently small positive number.
Specifically, coordinate *p_(i,j)* is perturbed by ε^(3^(*d***i* - *j*)),
where *d* is more than the number of dimensions.

# Predicates

## Orientation

The orientation of 2 points **p**_0, **p**_1 in 1-dimensional space is
positive if **p**_0 is to the right of **p**_1 and negative otherwise.
We don't consider the case where **p**_0 = **p**_1 because of the perturbations.

The orientation of *n* points **p**_0, ..., **p**_(n - 1) in (n - 1)-dimensional space is
the same as the orientation of **p**_1, ..., **p**_(n - 1) when looked at
from **p**_0. In particular, the orientation of 3 points in 2-dimensional space
is positive iff they form a left turn.

Orientation predicates for 1, 2, and 3 dimensions are implemented. They return whether the orientation is positive.

## In Hypersphere

The in-circle of 4 points measures whether the last point is inside the circle that goes through the first 3 points. Those 3 points are not collinear because of the perturbations.

The in-sphere of 5 points measures whether the last point is inside the sphere that goes through the first 4 points. Those 4 points are not coplanar because of the perturbations.

# Usage

use simplicity::{nalgebra, orient_2d}; use nalgebra::Vector2; let points = vec![ Vector2::new(0.0, 0.0), Vector2::new(1.0, 0.0), Vector2::new(1.0, 1.0), Vector2::new(0.0, 1.0), Vector2::new(2.0, 0.0), ]; // Positive orientation let result = orient_2d(&points, |l, i| l[i], 0, 1, 2); assert!(result); // Negative orientation let result = orient_2d(&points, |l, i| l[i], 0, 3, 2); assert!(!result); // Degenerate orientation, tie broken by perturbance let result = orient_2d(&points, |l, i| l[i], 0, 1, 4); assert!(result); let result = orient_2d(&points, |l, i| l[i], 4, 1, 0); assert!(!result);

Because the predicates take an indexing function, this can be
used for arbitrary lists without having to implement `Index`

for them:

let points = vec![ (Vector2::new(0.0, 0.0), 0.8), (Vector2::new(1.0, 0.0), 0.4), (Vector2::new(2.0, 0.0), 0.6), ]; let result = orient_2d(&points, |l, i| l[i].0, 0, 1, 2);

## Re-exports

`pub use nalgebra;` |

## Functions

in_circle | Returns whether the last point is inside the oriented circle that goes through the first 3 points after perturbing them. The first 3 points should be oriented positive or the result will be flipped. |

in_circle_unoriented | Returns whether the last point is inside the circle that goes through the first 3 points after perturbing them. |

in_sphere | Returns whether the last point is inside the sphere that goes through the first 4 points after perturbing them. |

in_sphere_unoriented | Returns whether the last point is inside the sphere that goes through the first 4 points after perturbing them. The first 4 points must be oriented positive or the result will be flipped. |

orient_1d | Returns whether the orientation of 2 points in 1-dimensional space is positive after perturbing them; that is, if the 1st one is to the right of the 2nd one. |

orient_2d | Returns whether the orientation of 3 points in 2-dimensional space is positive after perturbing them; that is, if the 3 points form a left turn when visited in order. |

orient_3d | Returns whether the orientation of 4 points in 3-dimensional space is positive after perturbing them; that is, if the last 3 points form a left turn when visited in order, looking from the first point. |