Edelsbrunner 和 Mücke 的《简单性模拟》的实现（https://arxiv.org/pdf/math/9410209.pdf）

简单性模拟是一种在计算几何谓词时忽略退化情况的技术，例如计算一个点相对于一系列点的方向。每个点 p_ i 都通过 ε 的某个多项式进行扰动，ε 是一个足够小的正数。具体来说，坐标 p_(i,j) 通过 ε^(3^(d*i - j)) 进行扰动，其中 d 大于维度数。

谓词

方向

在1维空间中，两点 p_0, p_1 的方向为正，如果 p_0 在 p_1 的右侧，否则为负。由于扰动，我们不考虑 p_0 = p_1 的情况。

(n - 1)-维空间中 n 个点 p_0, ..., p_(n - 1) 的方向与从 p_0 观看时 p_1, ..., p_(n - 1) 的方向相同。特别是，在二维空间中，三个点的方向为正当且仅当它们形成一个左转。

实现了1、2、3维的方向谓词。它们返回方向是否为正。

在超球面上

四个点的内切圆测量最后一个点是否在通过前三个点的圆内。由于扰动，这三个点不共线。

五个点的内球测量最后一个点是否在通过前四个点的球内。由于扰动，这四个点不共面。

用法

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);

由于谓词接受索引函数，因此可以用于任意列表，而无需为它们实现 Index

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);