pub fn triangulate(data: &[f64], hole_indices: &[usize], dim: usize) -> Vec<usize> {
earcut(data, hole_indices, dim)
}
type NodeId = usize;
#[derive(Clone, Debug)]
struct Node {
i: usize,
x: f64,
y: f64,
prev: NodeId,
next: NodeId,
z: i32,
prev_z: Option<NodeId>,
next_z: Option<NodeId>,
steiner: bool,
}
struct Earcut {
nodes: Vec<Node>,
}
fn truthy(inv_size: Option<f64>) -> bool {
matches!(inv_size, Some(v) if v != 0.0 && !v.is_nan())
}
fn earcut(data: &[f64], hole_indices: &[usize], dim: usize) -> Vec<usize> {
let mut ec = Earcut { nodes: Vec::new() };
let has_holes = !hole_indices.is_empty();
let outer_len = if has_holes {
hole_indices[0] * dim
} else {
data.len()
};
let outer_node = ec.linked_list(data, 0, outer_len, dim, true);
let mut triangles = Vec::new();
let Some(mut outer_node) = outer_node else {
return triangles;
};
if ec.nodes[outer_node].next == ec.nodes[outer_node].prev {
return triangles;
}
let mut min_x = f64::NAN;
let mut min_y = f64::NAN;
let mut inv_size = None;
if has_holes {
outer_node = ec.eliminate_holes(data, hole_indices, outer_node, dim);
}
if data.len() > 80 * dim {
min_x = data[0];
min_y = data[1];
let mut max_x = min_x;
let mut max_y = min_y;
let mut i = dim;
while i < outer_len {
let x = data[i];
let y = data[i + 1];
if x < min_x {
min_x = x;
}
if y < min_y {
min_y = y;
}
if x > max_x {
max_x = x;
}
if y > max_y {
max_y = y;
}
i += dim;
}
let size = (max_x - min_x).max(max_y - min_y);
inv_size = Some(if size != 0.0 { 32767.0 / size } else { 0.0 });
}
ec.earcut_linked(
Some(outer_node),
&mut triangles,
dim,
min_x,
min_y,
inv_size,
0,
);
triangles
}
impl Earcut {
fn n(&self, id: NodeId) -> &Node {
&self.nodes[id]
}
fn equals(&self, p1: NodeId, p2: NodeId) -> bool {
let (a, b) = (self.n(p1), self.n(p2));
a.x == b.x && a.y == b.y
}
fn area(&self, p: NodeId, q: NodeId, r: NodeId) -> f64 {
let (p, q, r) = (self.n(p), self.n(q), self.n(r));
(q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
}
fn linked_list(
&mut self,
data: &[f64],
start: usize,
end: usize,
dim: usize,
clockwise: bool,
) -> Option<NodeId> {
let mut last: Option<NodeId> = None;
if clockwise == (signed_area(data, start, end, dim) > 0.0) {
let mut i = start;
while i < end {
last = Some(self.insert_node(i / dim, data[i], data[i + 1], last));
i += dim;
}
} else if end >= dim {
let mut i = (end - dim) as isize;
while i >= start as isize {
let iu = i as usize;
last = Some(self.insert_node(iu / dim, data[iu], data[iu + 1], last));
i -= dim as isize;
}
}
if let Some(l) = last {
if self.equals(l, self.n(l).next) {
self.remove_node(l);
last = Some(self.n(l).next);
}
}
last
}
fn filter_points(&mut self, start: Option<NodeId>, end: Option<NodeId>) -> Option<NodeId> {
let start = start?;
let mut end = end.unwrap_or(start);
let mut p = start;
loop {
let mut again = false;
let (prev, next) = (self.n(p).prev, self.n(p).next);
if !self.n(p).steiner && (self.equals(p, next) || self.area(prev, p, next) == 0.0) {
self.remove_node(p);
p = self.n(p).prev;
end = p;
if p == self.n(p).next {
break;
}
again = true;
} else {
p = self.n(p).next;
}
if !(again || p != end) {
break;
}
}
Some(end)
}
#[allow(clippy::too_many_arguments)]
fn earcut_linked(
&mut self,
ear: Option<NodeId>,
triangles: &mut Vec<usize>,
dim: usize,
min_x: f64,
min_y: f64,
inv_size: Option<f64>,
pass: u8,
) {
let Some(mut ear) = ear else {
return;
};
if pass == 0 && truthy(inv_size) {
self.index_curve(ear, min_x, min_y, inv_size.unwrap_or(0.0));
}
let mut stop = ear;
while self.n(ear).prev != self.n(ear).next {
let prev = self.n(ear).prev;
let next = self.n(ear).next;
let is_ear = if truthy(inv_size) {
self.is_ear_hashed(ear, min_x, min_y, inv_size.unwrap_or(0.0))
} else {
self.is_ear(ear)
};
if is_ear {
triangles.push(self.n(prev).i);
triangles.push(self.n(ear).i);
triangles.push(self.n(next).i);
self.remove_node(ear);
ear = self.n(next).next;
stop = self.n(next).next;
continue;
}
ear = next;
if ear == stop {
if pass == 0 {
let filtered = self.filter_points(Some(ear), None);
self.earcut_linked(filtered, triangles, dim, min_x, min_y, inv_size, 1);
} else if pass == 1 {
let filtered = self.filter_points(Some(ear), None);
let cured = self.cure_local_intersections(filtered, triangles);
self.earcut_linked(cured, triangles, dim, min_x, min_y, inv_size, 2);
} else if pass == 2 {
self.split_earcut(ear, triangles, dim, min_x, min_y, inv_size);
}
break;
}
}
}
fn is_ear(&self, ear: NodeId) -> bool {
let a = self.n(ear).prev;
let b = ear;
let c = self.n(ear).next;
if self.area(a, b, c) >= 0.0 {
return false; }
let (ax, bx, cx) = (self.n(a).x, self.n(b).x, self.n(c).x);
let (ay, by, cy) = (self.n(a).y, self.n(b).y, self.n(c).y);
let x0 = js_min3(ax, bx, cx);
let y0 = js_min3(ay, by, cy);
let x1 = js_max3(ax, bx, cx);
let y1 = js_max3(ay, by, cy);
let mut p = self.n(c).next;
while p != a {
let pn = self.n(p);
if pn.x >= x0
&& pn.x <= x1
&& pn.y >= y0
&& pn.y <= y1
&& point_in_triangle_except_first(ax, ay, bx, by, cx, cy, pn.x, pn.y)
&& self.area(pn.prev, p, pn.next) >= 0.0
{
return false;
}
p = pn.next;
}
true
}
#[allow(clippy::too_many_arguments)]
fn blocks_ear(
&self,
p: NodeId,
a: NodeId,
c: NodeId,
tri: (f64, f64, f64, f64, f64, f64),
bbox: (f64, f64, f64, f64),
) -> bool {
let (ax, ay, bx, by, cx, cy) = tri;
let (x0, y0, x1, y1) = bbox;
let pn = self.n(p);
pn.x >= x0
&& pn.x <= x1
&& pn.y >= y0
&& pn.y <= y1
&& p != a
&& p != c
&& point_in_triangle_except_first(ax, ay, bx, by, cx, cy, pn.x, pn.y)
&& self.area(pn.prev, p, pn.next) >= 0.0
}
fn is_ear_hashed(&self, ear: NodeId, min_x: f64, min_y: f64, inv_size: f64) -> bool {
let a = self.n(ear).prev;
let b = ear;
let c = self.n(ear).next;
if self.area(a, b, c) >= 0.0 {
return false; }
let (ax, bx, cx) = (self.n(a).x, self.n(b).x, self.n(c).x);
let (ay, by, cy) = (self.n(a).y, self.n(b).y, self.n(c).y);
let x0 = js_min3(ax, bx, cx);
let y0 = js_min3(ay, by, cy);
let x1 = js_max3(ax, bx, cx);
let y1 = js_max3(ay, by, cy);
let min_z = z_order(x0, y0, min_x, min_y, inv_size);
let max_z = z_order(x1, y1, min_x, min_y, inv_size);
let tri = (ax, ay, bx, by, cx, cy);
let bbox = (x0, y0, x1, y1);
let mut p = self.n(ear).prev_z;
let mut n = self.n(ear).next_z;
while let (Some(pp), Some(nn)) = (p, n) {
if !(self.n(pp).z >= min_z && self.n(nn).z <= max_z) {
break;
}
if self.blocks_ear(pp, a, c, tri, bbox) {
return false;
}
p = self.n(pp).prev_z;
if self.blocks_ear(nn, a, c, tri, bbox) {
return false;
}
n = self.n(nn).next_z;
}
while let Some(pp) = p {
if self.n(pp).z < min_z {
break;
}
if self.blocks_ear(pp, a, c, tri, bbox) {
return false;
}
p = self.n(pp).prev_z;
}
while let Some(nn) = n {
if self.n(nn).z > max_z {
break;
}
if self.blocks_ear(nn, a, c, tri, bbox) {
return false;
}
n = self.n(nn).next_z;
}
true
}
fn cure_local_intersections(
&mut self,
start: Option<NodeId>,
triangles: &mut Vec<usize>,
) -> Option<NodeId> {
let mut start = start?;
let mut p = start;
loop {
let a = self.n(p).prev;
let b = self.n(self.n(p).next).next;
if !self.equals(a, b)
&& self.intersects(a, p, self.n(p).next, b)
&& self.locally_inside(a, b)
&& self.locally_inside(b, a)
{
triangles.push(self.n(a).i);
triangles.push(self.n(p).i);
triangles.push(self.n(b).i);
self.remove_node(p);
let pn = self.n(p).next;
self.remove_node(pn);
p = b;
start = b;
}
p = self.n(p).next;
if p == start {
break;
}
}
self.filter_points(Some(p), None)
}
fn split_earcut(
&mut self,
start: NodeId,
triangles: &mut Vec<usize>,
dim: usize,
min_x: f64,
min_y: f64,
inv_size: Option<f64>,
) {
let mut a = start;
loop {
let mut b = self.n(self.n(a).next).next;
while b != self.n(a).prev {
if self.n(a).i != self.n(b).i && self.is_valid_diagonal(a, b) {
let c = self.split_polygon(a, b);
let a_next = self.n(a).next;
let a = self.filter_points(Some(a), Some(a_next));
let c_next = self.n(c).next;
let c = self.filter_points(Some(c), Some(c_next));
self.earcut_linked(a, triangles, dim, min_x, min_y, inv_size, 0);
self.earcut_linked(c, triangles, dim, min_x, min_y, inv_size, 0);
return;
}
b = self.n(b).next;
}
a = self.n(a).next;
if a == start {
break;
}
}
}
fn eliminate_holes(
&mut self,
data: &[f64],
hole_indices: &[usize],
mut outer_node: NodeId,
dim: usize,
) -> NodeId {
let mut queue: Vec<NodeId> = Vec::new();
let len = hole_indices.len();
for i in 0..len {
let start = hole_indices[i] * dim;
let end = if i < len - 1 {
hole_indices[i + 1] * dim
} else {
data.len()
};
let list = self
.linked_list(data, start, end, dim, false)
.expect("three-rs: earcut: an empty hole (three.js throws on the null list)");
if list == self.n(list).next {
self.nodes[list].steiner = true;
}
queue.push(self.get_leftmost(list));
}
queue.sort_by(|&a, &b| {
let result = self.compare_x_y_slope(a, b);
if result < 0.0 {
std::cmp::Ordering::Less
} else if result > 0.0 {
std::cmp::Ordering::Greater
} else {
std::cmp::Ordering::Equal
}
});
for &hole in &queue {
outer_node = self.eliminate_hole(hole, outer_node);
}
outer_node
}
fn compare_x_y_slope(&self, a: NodeId, b: NodeId) -> f64 {
let (an, bn) = (self.n(a), self.n(b));
let mut result = an.x - bn.x;
if result == 0.0 {
result = an.y - bn.y;
if result == 0.0 {
let (anx, bnx) = (self.n(an.next), self.n(bn.next));
let a_slope = (anx.y - an.y) / (anx.x - an.x);
let b_slope = (bnx.y - bn.y) / (bnx.x - bn.x);
result = a_slope - b_slope;
}
}
result
}
fn eliminate_hole(&mut self, hole: NodeId, outer_node: NodeId) -> NodeId {
let Some(bridge) = self.find_hole_bridge(hole, outer_node) else {
return outer_node;
};
let bridge_reverse = self.split_polygon(bridge, hole);
let brn = self.n(bridge_reverse).next;
self.filter_points(Some(bridge_reverse), Some(brn));
let bn = self.n(bridge).next;
self.filter_points(Some(bridge), Some(bn))
.expect("three-rs: earcut: filterPoints of a non-null start is non-null")
}
fn find_hole_bridge(&self, hole: NodeId, outer_node: NodeId) -> Option<NodeId> {
let mut p = outer_node;
let hx = self.n(hole).x;
let hy = self.n(hole).y;
let mut qx = f64::NEG_INFINITY;
let mut m: Option<NodeId> = None;
if self.equals(hole, p) {
return Some(p);
}
loop {
let pn = self.n(p);
let next = self.n(pn.next);
if self.equals(hole, pn.next) {
return Some(pn.next);
} else if hy <= pn.y && hy >= next.y && next.y != pn.y {
let x = pn.x + (hy - pn.y) * (next.x - pn.x) / (next.y - pn.y);
if x <= hx && x > qx {
qx = x;
let mm = if pn.x < next.x { p } else { pn.next };
m = Some(mm);
if x == hx {
return Some(mm); }
}
}
p = pn.next;
if p == outer_node {
break;
}
}
let mut m = m?;
let stop = m;
let mx = self.n(m).x;
let my = self.n(m).y;
let mut tan_min = f64::INFINITY;
p = m;
loop {
let (px, py) = (self.n(p).x, self.n(p).y);
if hx >= px
&& px >= mx
&& hx != px
&& point_in_triangle(
if hy < my { hx } else { qx },
hy,
mx,
my,
if hy < my { qx } else { hx },
hy,
px,
py,
)
{
let tan = (hy - py).abs() / (hx - px);
if self.locally_inside(p, hole)
&& (tan < tan_min
|| (tan == tan_min
&& (px > self.n(m).x
|| (px == self.n(m).x && self.sector_contains_sector(m, p)))))
{
m = p;
tan_min = tan;
}
}
p = self.n(p).next;
if p == stop {
break;
}
}
Some(m)
}
fn sector_contains_sector(&self, m: NodeId, p: NodeId) -> bool {
self.area(self.n(m).prev, m, self.n(p).prev) < 0.0
&& self.area(self.n(p).next, m, self.n(m).next) < 0.0
}
fn index_curve(&mut self, start: NodeId, min_x: f64, min_y: f64, inv_size: f64) {
let mut p = start;
loop {
if self.nodes[p].z == 0 {
self.nodes[p].z = z_order(self.nodes[p].x, self.nodes[p].y, min_x, min_y, inv_size);
}
self.nodes[p].prev_z = Some(self.nodes[p].prev);
self.nodes[p].next_z = Some(self.nodes[p].next);
p = self.nodes[p].next;
if p == start {
break;
}
}
let pz = self.nodes[p]
.prev_z
.expect("three-rs: earcut: indexCurve just set prevZ");
self.nodes[pz].next_z = None;
self.nodes[p].prev_z = None;
self.sort_linked(p);
}
fn sort_linked(&mut self, list: NodeId) -> Option<NodeId> {
let mut list = Some(list);
let mut in_size = 1;
loop {
let mut p = list;
list = None;
let mut tail: Option<NodeId> = None;
let mut num_merges = 0;
while let Some(pp) = p {
num_merges += 1;
let mut q = Some(pp);
let mut p_size = 0;
for _ in 0..in_size {
p_size += 1;
q = q.and_then(|q| self.nodes[q].next_z);
if q.is_none() {
break;
}
}
let mut q_size = in_size;
let mut p_cur = Some(pp);
while p_size > 0 || (q_size > 0 && q.is_some()) {
let e;
let take_p = p_size != 0
&& (q_size == 0
|| q.is_none()
|| self.nodes[p_cur.expect("pSize > 0")].z
<= self.nodes[q.expect("q checked")].z);
if take_p {
let ep = p_cur.expect("three-rs: earcut: pSize > 0 means p is set");
e = ep;
p_cur = self.nodes[ep].next_z;
p_size -= 1;
} else {
let eq = q.expect("three-rs: earcut: the q branch runs with q set");
e = eq;
q = self.nodes[eq].next_z;
q_size -= 1;
}
if let Some(t) = tail {
self.nodes[t].next_z = Some(e);
} else {
list = Some(e);
}
self.nodes[e].prev_z = tail;
tail = Some(e);
}
p = q;
}
if let Some(t) = tail {
self.nodes[t].next_z = None;
}
in_size *= 2;
if num_merges <= 1 {
break;
}
}
list
}
fn get_leftmost(&self, start: NodeId) -> NodeId {
let mut p = start;
let mut leftmost = start;
loop {
let (pn, ln) = (self.n(p), self.n(leftmost));
if pn.x < ln.x || (pn.x == ln.x && pn.y < ln.y) {
leftmost = p;
}
p = pn.next;
if p == start {
break;
}
}
leftmost
}
fn is_valid_diagonal(&self, a: NodeId, b: NodeId) -> bool {
let (an, bn) = (self.n(a), self.n(b));
let area_truthy = |v: f64| v != 0.0 && !v.is_nan();
self.n(an.next).i != bn.i
&& self.n(an.prev).i != bn.i
&& !self.intersects_polygon(a, b) && ((self.locally_inside(a, b)
&& self.locally_inside(b, a)
&& self.middle_inside(a, b) && (area_truthy(self.area(an.prev, a, bn.prev))
|| area_truthy(self.area(a, bn.prev, b)))) || (self.equals(a, b)
&& self.area(an.prev, a, an.next) > 0.0
&& self.area(bn.prev, b, bn.next) > 0.0)) }
fn intersects(&self, p1: NodeId, q1: NodeId, p2: NodeId, q2: NodeId) -> bool {
let o1 = sign(self.area(p1, q1, p2));
let o2 = sign(self.area(p1, q1, q2));
let o3 = sign(self.area(p2, q2, p1));
let o4 = sign(self.area(p2, q2, q1));
if o1 != o2 && o3 != o4 {
return true; }
if o1 == 0 && self.on_segment(p1, p2, q1) {
return true; }
if o2 == 0 && self.on_segment(p1, q2, q1) {
return true; }
if o3 == 0 && self.on_segment(p2, p1, q2) {
return true; }
if o4 == 0 && self.on_segment(p2, q1, q2) {
return true; }
false
}
fn on_segment(&self, p: NodeId, q: NodeId, r: NodeId) -> bool {
let (p, q, r) = (self.n(p), self.n(q), self.n(r));
q.x <= js_max2(p.x, r.x)
&& q.x >= js_min2(p.x, r.x)
&& q.y <= js_max2(p.y, r.y)
&& q.y >= js_min2(p.y, r.y)
}
fn intersects_polygon(&self, a: NodeId, b: NodeId) -> bool {
let (ai, bi) = (self.n(a).i, self.n(b).i);
let mut p = a;
loop {
let pn = self.n(p);
let next_i = self.n(pn.next).i;
if pn.i != ai
&& next_i != ai
&& pn.i != bi
&& next_i != bi
&& self.intersects(p, pn.next, a, b)
{
return true;
}
p = pn.next;
if p == a {
break;
}
}
false
}
fn locally_inside(&self, a: NodeId, b: NodeId) -> bool {
let an = self.n(a);
if self.area(an.prev, a, an.next) < 0.0 {
self.area(a, b, an.next) >= 0.0 && self.area(a, an.prev, b) >= 0.0
} else {
self.area(a, b, an.prev) < 0.0 || self.area(a, an.next, b) < 0.0
}
}
fn middle_inside(&self, a: NodeId, b: NodeId) -> bool {
let mut p = a;
let mut inside = false;
let px = (self.n(a).x + self.n(b).x) / 2.0;
let py = (self.n(a).y + self.n(b).y) / 2.0;
loop {
let pn = self.n(p);
let next = self.n(pn.next);
if ((pn.y > py) != (next.y > py))
&& next.y != pn.y
&& (px < (next.x - pn.x) * (py - pn.y) / (next.y - pn.y) + pn.x)
{
inside = !inside;
}
p = pn.next;
if p == a {
break;
}
}
inside
}
fn split_polygon(&mut self, a: NodeId, b: NodeId) -> NodeId {
let a2 = self.create_node(self.n(a).i, self.n(a).x, self.n(a).y);
let b2 = self.create_node(self.n(b).i, self.n(b).x, self.n(b).y);
let an = self.n(a).next;
let bp = self.n(b).prev;
self.nodes[a].next = b;
self.nodes[b].prev = a;
self.nodes[a2].next = an;
self.nodes[an].prev = a2;
self.nodes[b2].next = a2;
self.nodes[a2].prev = b2;
self.nodes[bp].next = b2;
self.nodes[b2].prev = bp;
b2
}
fn insert_node(&mut self, i: usize, x: f64, y: f64, last: Option<NodeId>) -> NodeId {
let p = self.create_node(i, x, y);
match last {
None => {
self.nodes[p].prev = p;
self.nodes[p].next = p;
}
Some(last) => {
let last_next = self.n(last).next;
self.nodes[p].next = last_next;
self.nodes[p].prev = last;
self.nodes[last_next].prev = p;
self.nodes[last].next = p;
}
}
p
}
fn remove_node(&mut self, p: NodeId) {
let (prev, next) = (self.n(p).prev, self.n(p).next);
self.nodes[next].prev = prev;
self.nodes[prev].next = next;
let (prev_z, next_z) = (self.n(p).prev_z, self.n(p).next_z);
if let Some(pz) = prev_z {
self.nodes[pz].next_z = next_z;
}
if let Some(nz) = next_z {
self.nodes[nz].prev_z = prev_z;
}
}
fn create_node(&mut self, i: usize, x: f64, y: f64) -> NodeId {
let id = self.nodes.len();
self.nodes.push(Node {
i,
x,
y,
prev: id,
next: id,
z: 0,
prev_z: None,
next_z: None,
steiner: false,
});
id
}
}
fn z_order(x: f64, y: f64, min_x: f64, min_y: f64, inv_size: f64) -> i32 {
let mut x = to_int32((x - min_x) * inv_size);
let mut y = to_int32((y - min_y) * inv_size);
x = (x | (x << 8)) & 0x00FF00FF;
x = (x | (x << 4)) & 0x0F0F0F0F;
x = (x | (x << 2)) & 0x33333333;
x = (x | (x << 1)) & 0x55555555;
y = (y | (y << 8)) & 0x00FF00FF;
y = (y | (y << 4)) & 0x0F0F0F0F;
y = (y | (y << 2)) & 0x33333333;
y = (y | (y << 1)) & 0x55555555;
x | (y << 1)
}
fn to_int32(v: f64) -> i32 {
if !v.is_finite() {
return 0;
}
(v.trunc().rem_euclid(4294967296.0) as u64 as u32) as i32
}
#[allow(clippy::too_many_arguments)]
fn point_in_triangle(
ax: f64,
ay: f64,
bx: f64,
by: f64,
cx: f64,
cy: f64,
px: f64,
py: f64,
) -> bool {
(cx - px) * (ay - py) >= (ax - px) * (cy - py)
&& (ax - px) * (by - py) >= (bx - px) * (ay - py)
&& (bx - px) * (cy - py) >= (cx - px) * (by - py)
}
#[allow(clippy::too_many_arguments)]
fn point_in_triangle_except_first(
ax: f64,
ay: f64,
bx: f64,
by: f64,
cx: f64,
cy: f64,
px: f64,
py: f64,
) -> bool {
!(ax == px && ay == py) && point_in_triangle(ax, ay, bx, by, cx, cy, px, py)
}
fn sign(num: f64) -> i32 {
if num > 0.0 {
1
} else if num < 0.0 {
-1
} else {
0
}
}
fn js_min2(a: f64, b: f64) -> f64 {
if a.is_nan() || b.is_nan() {
f64::NAN
} else {
a.min(b)
}
}
fn js_max2(a: f64, b: f64) -> f64 {
if a.is_nan() || b.is_nan() {
f64::NAN
} else {
a.max(b)
}
}
fn js_min3(a: f64, b: f64, c: f64) -> f64 {
js_min2(js_min2(a, b), c)
}
fn js_max3(a: f64, b: f64, c: f64) -> f64 {
js_max2(js_max2(a, b), c)
}
fn signed_area(data: &[f64], start: usize, end: usize, dim: usize) -> f64 {
let mut sum = 0.0;
if end < dim {
return sum;
}
let mut i = start;
let mut j = end - dim;
while i < end {
sum += (data[j] - data[i]) * (data[i + 1] + data[j + 1]);
j = i;
i += dim;
}
sum
}