mod geom;
use rand::prelude::thread_rng;
use rand::Rng;
use std::fmt;
use std::fs::File;
use std::io::Write;
use std::mem;
extern crate rand;
pub struct Triangle {
pub tr0: usize,
pub tr1: usize,
pub tr2: usize,
}
impl Triangle {
fn is_infinite(&self) -> bool {
if self.tr0 == 0 || self.tr1 == 0 || self.tr2 == 0 {
return true;
}
return false;
}
}
impl fmt::Display for Triangle {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "({}, {}, {})", self.tr0, self.tr1, self.tr2)
}
}
struct Link(Vec<usize>);
impl Link {
fn new() -> Link {
Link(Vec::with_capacity(8))
}
fn len(&self) -> usize {
self.0.len()
}
fn is_empty(&self) -> bool {
if self.0.len() == 0 {
true
} else {
false
}
}
fn add(&mut self, v: usize) {
self.0.push(v);
}
fn insert_after_v(&mut self, v: usize, after: usize) {
let pos = self.0.iter().position(|&x| x == after).unwrap();
self.0.insert(pos + 1, v);
}
fn delete(&mut self, v: usize) {
let re = self.0.iter().position(|&x| x == v);
if re != None {
self.0.remove(re.unwrap());
}
}
fn replace(&mut self, v: usize, newv: usize) {
let re = self.0.iter().position(|&x| x == v);
if re != None {
self.0[re.unwrap()] = newv;
}
}
fn infinite_first(&mut self) {
let re = self.0.iter().position(|&x| x == 0);
if re != None {
let posinf = re.unwrap();
if posinf == 0 {
return;
}
let mut newstar: Vec<usize> = Vec::new();
for j in posinf..self.0.len() {
newstar.push(self.0[j]);
}
for j in 0..posinf {
newstar.push(self.0[j]);
}
self.0 = newstar;
}
}
fn clear(&mut self) {
self.0.clear();
}
fn contains_infinite_vertex(&self) -> bool {
let pos = self.0.iter().position(|&x| x == 0);
if pos == None {
return false;
} else {
return true;
}
}
fn next_index(&self, i: usize) -> usize {
if i == (self.0.len() - 1) {
0
} else {
i + 1
}
}
fn get_index(&self, v: usize) -> Option<usize> {
return self.0.iter().position(|&x| x == v);
}
fn get_next_vertex(&self, v: usize) -> Option<usize> {
let re = self.get_index(v);
if re.is_none() {
return None;
}
let pos = re.unwrap();
if pos == (self.0.len() - 1) {
return Some(self.0[0]);
} else {
return Some(self.0[(pos + 1)]);
}
}
fn get_prev_vertex(&self, v: usize) -> Option<usize> {
let re = self.get_index(v);
if re.is_none() {
return None;
}
let pos = re.unwrap();
if pos == 0 {
return Some(self.0[(self.0.len() - 1)]);
} else {
return Some(self.0[(pos - 1)]);
}
}
fn iter(&self) -> Iter {
Iter(Box::new(self.0.iter()))
}
}
struct Iter<'a>(Box<Iterator<Item = &'a usize> + 'a>);
impl<'a> Iterator for Iter<'a> {
type Item = &'a usize;
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
}
}
impl std::ops::Index<usize> for Link {
type Output = usize;
fn index(&self, idx: usize) -> &usize {
&self.0[idx as usize]
}
}
struct Star {
pub pt: [f64; 3],
pub link: Link,
}
impl Star {
pub fn new(x: f64, y: f64, z: f64) -> Star {
let l = Link::new();
Star {
pt: [x, y, z],
link: l,
}
}
pub fn is_deleted(&self) -> bool {
self.link.is_empty()
}
}
pub struct Triangulation {
stars: Vec<Star>,
snaptol: f64,
cur: usize,
is_init: bool,
jump_and_walk: bool,
robust_predicates: bool,
removed_indices: Vec<usize>,
}
impl Triangulation {
pub fn new() -> Triangulation {
let mut l: Vec<Star> = Vec::new();
l.push(Star::new(-99999.99999, -99999.99999, -99999.99999));
let es: Vec<usize> = Vec::new();
Triangulation {
stars: l,
snaptol: 0.001,
cur: 0,
is_init: false,
jump_and_walk: false,
robust_predicates: true,
removed_indices: es,
}
}
fn insert_one_pt_init_phase(&mut self, x: f64, y: f64, z: f64) -> Result<usize, usize> {
let p: [f64; 3] = [x, y, z];
for i in 1..self.stars.len() {
if geom::distance2d_squared(&self.stars[i].pt, &p) <= (self.snaptol * self.snaptol) {
return Err(i);
}
}
self.stars.push(Star::new(x, y, z));
let l = self.stars.len();
if l >= 4 {
let a = l - 3;
let b = l - 2;
let c = l - 1;
let re = geom::orient2d(
&self.stars[a].pt,
&self.stars[b].pt,
&self.stars[c].pt,
self.robust_predicates,
);
if re == 1 {
self.stars[0].link.add(a);
self.stars[0].link.add(c);
self.stars[0].link.add(b);
self.stars[a].link.add(0);
self.stars[a].link.add(b);
self.stars[a].link.add(c);
self.stars[b].link.add(0);
self.stars[b].link.add(c);
self.stars[b].link.add(a);
self.stars[c].link.add(0);
self.stars[c].link.add(a);
self.stars[c].link.add(b);
self.is_init = true;
} else if re == -1 {
self.stars[0].link.add(a);
self.stars[0].link.add(b);
self.stars[0].link.add(c);
self.stars[a].link.add(0);
self.stars[a].link.add(c);
self.stars[a].link.add(b);
self.stars[b].link.add(0);
self.stars[b].link.add(a);
self.stars[b].link.add(c);
self.stars[c].link.add(0);
self.stars[c].link.add(b);
self.stars[c].link.add(a);
self.is_init = true;
}
}
self.cur = l - 1;
if self.is_init == true {
for j in 1..(l - 3) {
let tr = self.walk(&self.stars[j].pt);
self.flip13(j, &tr);
self.update_dt(j);
}
}
Ok(self.cur)
}
pub fn set_snap_tolerance(&mut self, snaptol: f64) -> f64 {
if snaptol > 0.0 {
self.snaptol = snaptol;
}
self.snaptol
}
pub fn get_snap_tolerance(&self) -> f64 {
self.snaptol
}
pub fn set_jump_and_walk(&mut self, b: bool) {
self.jump_and_walk = b;
}
pub fn is_using_robust_predicates(&self) -> bool {
self.robust_predicates
}
pub fn use_robust_predicates(&mut self, b: bool) {
self.robust_predicates = b;
}
pub fn insert(&mut self, pts: &Vec<Vec<f64>>) {
let mut duplicates = 0;
for each in pts {
if (each.len() < 2) || (each.len() > 3) {
panic!(
"Point {:?} should be 2D or 3D (and is now {}D).",
each,
each.len()
);
} else {
let re;
if each.len() == 2 {
re = self.insert_one_pt(each[0], each[1], 0.0);
} else {
re = self.insert_one_pt(each[0], each[1], each[2]);
}
match re {
Ok(_x) => continue,
Err(_e) => duplicates = duplicates + 1,
}
}
}
}
pub fn insert_one_pt(&mut self, px: f64, py: f64, pz: f64) -> Result<usize, usize> {
if self.is_init == false {
return self.insert_one_pt_init_phase(px, py, pz);
}
let p: [f64; 3] = [px, py, pz];
let tr = self.walk(&p);
if geom::distance2d_squared(&self.stars[tr.tr0].pt, &p) <= (self.snaptol * self.snaptol) {
return Err(tr.tr0);
}
if geom::distance2d_squared(&self.stars[tr.tr1].pt, &p) <= (self.snaptol * self.snaptol) {
return Err(tr.tr1);
}
if geom::distance2d_squared(&self.stars[tr.tr2].pt, &p) <= (self.snaptol * self.snaptol) {
return Err(tr.tr2);
}
let pi: usize;
if self.removed_indices.is_empty() == true {
self.stars.push(Star::new(px, py, pz));
pi = self.stars.len() - 1;
} else {
pi = self.removed_indices.pop().unwrap();
self.stars[pi].pt[0] = px;
self.stars[pi].pt[1] = py;
self.stars[pi].pt[2] = pz;
}
self.flip13(pi, &tr);
self.update_dt(pi);
self.cur = pi;
Ok(pi)
}
fn update_dt(&mut self, pi: usize) {
let mut mystack: Vec<Triangle> = Vec::new();
mystack.push(Triangle {
tr0: pi,
tr1: self.stars[pi].link[0],
tr2: self.stars[pi].link[1],
});
mystack.push(Triangle {
tr0: pi,
tr1: self.stars[pi].link[1],
tr2: self.stars[pi].link[2],
});
mystack.push(Triangle {
tr0: pi,
tr1: self.stars[pi].link[2],
tr2: self.stars[pi].link[0],
});
loop {
let tr = match mystack.pop() {
None => break,
Some(x) => x,
};
let opposite = self.get_opposite_vertex(&tr);
if tr.is_infinite() == true {
let mut a: i8 = 0;
if tr.tr0 == 0 {
a = geom::orient2d(
&self.stars[opposite].pt,
&self.stars[tr.tr1].pt,
&self.stars[tr.tr2].pt,
self.robust_predicates,
);
} else if tr.tr1 == 0 {
a = geom::orient2d(
&self.stars[tr.tr0].pt,
&self.stars[opposite].pt,
&self.stars[tr.tr2].pt,
self.robust_predicates,
);
} else if tr.tr2 == 0 {
a = geom::orient2d(
&self.stars[tr.tr0].pt,
&self.stars[tr.tr1].pt,
&self.stars[opposite].pt,
self.robust_predicates,
);
}
if a > 0 {
let (ret0, ret1) = self.flip22(&tr, opposite);
mystack.push(ret0);
mystack.push(ret1);
}
} else {
if opposite == 0 {
if geom::orient2d(
&self.stars[tr.tr0].pt,
&self.stars[tr.tr1].pt,
&self.stars[tr.tr2].pt,
self.robust_predicates,
) == 0
{
let (ret0, ret1) = self.flip22(&tr, 0);
mystack.push(ret0);
mystack.push(ret1);
}
} else {
if geom::incircle(
&self.stars[tr.tr0].pt,
&self.stars[tr.tr1].pt,
&self.stars[tr.tr2].pt,
&self.stars[opposite].pt,
self.robust_predicates,
) > 0
{
let (ret0, ret1) = self.flip22(&tr, opposite);
mystack.push(ret0);
mystack.push(ret1);
}
}
}
}
}
fn flip13(&mut self, pi: usize, tr: &Triangle) {
self.stars[pi].link.add(tr.tr0);
self.stars[pi].link.add(tr.tr1);
self.stars[pi].link.add(tr.tr2);
self.stars[tr.tr0].link.insert_after_v(pi, tr.tr1);
self.stars[tr.tr1].link.insert_after_v(pi, tr.tr2);
self.stars[tr.tr2].link.insert_after_v(pi, tr.tr0);
self.stars[pi].link.infinite_first();
}
fn flip31(&mut self, v: usize) {
let mut ns: Vec<usize> = Vec::new();
for each in self.stars[v].link.iter() {
ns.push(*each);
}
for n in ns.iter() {
self.stars[*n].link.delete(v);
}
self.stars[v].link.clear();
self.stars[v].pt[0] = -999.9;
self.stars[v].pt[1] = -999.9;
self.stars[v].pt[2] = -999.9;
self.removed_indices.push(v);
if ns[0] != 0 {
self.cur = ns[0];
} else {
self.cur = ns[1];
}
}
pub fn get_point(&self, v: usize) -> Option<Vec<f64>> {
if self.vertex_exists(v) == false {
None
} else {
Some(self.stars[v].pt.to_vec())
}
}
pub fn adjacent_triangles_to_triangle(&self, tr: &Triangle) -> Option<Vec<Triangle>> {
if self.is_triangle(&tr) == false || tr.is_infinite() == true {
return None;
}
let mut trs: Vec<Triangle> = Vec::new();
let mut opp = self.stars[tr.tr2].link.get_next_vertex(tr.tr1).unwrap();
if opp != 0 {
trs.push(Triangle {
tr0: tr.tr1,
tr1: opp,
tr2: tr.tr2,
});
}
opp = self.stars[tr.tr0].link.get_next_vertex(tr.tr2).unwrap();
if opp != 0 {
trs.push(Triangle {
tr0: tr.tr2,
tr1: opp,
tr2: tr.tr0,
});
}
opp = self.stars[tr.tr1].link.get_next_vertex(tr.tr0).unwrap();
if opp != 0 {
trs.push(Triangle {
tr0: tr.tr0,
tr1: opp,
tr2: tr.tr1,
});
}
Some(trs)
}
pub fn incident_triangles_to_vertex(&self, v: usize) -> Option<Vec<Triangle>> {
if self.vertex_exists(v) == false {
return None;
}
let mut trs: Vec<Triangle> = Vec::new();
for (i, each) in self.stars[v].link.iter().enumerate() {
let j = self.stars[v].link.next_index(i);
trs.push(Triangle {
tr0: v,
tr1: *each,
tr2: self.stars[v].link[j],
});
}
Some(trs)
}
pub fn degree(&self, v: usize) -> Option<usize> {
if self.vertex_exists(v) == false {
return None;
}
Some(self.stars[v].link.len())
}
pub fn adjacent_vertices_to_vertex(&self, v: usize) -> Option<Vec<usize>> {
if self.vertex_exists(v) == false {
return None;
}
let mut adjs: Vec<usize> = Vec::new();
for each in self.stars[v].link.iter() {
adjs.push(*each);
}
Some(adjs)
}
pub fn is_triangle(&self, tr: &Triangle) -> bool {
let re = self.stars[tr.tr0].link.get_next_vertex(tr.tr1);
if re.is_none() {
return false;
} else {
if re.unwrap() == tr.tr2 {
return true;
} else {
return false;
}
}
}
pub fn statistics_degree(&self) -> (f64, usize, usize) {
let mut total: f64 = 0.0;
let mut min: usize = usize::max_value();
let mut max: usize = usize::min_value();
for i in 1..self.stars.len() {
total = total + self.stars[i].link.len() as f64;
if self.stars[i].link.len() > max {
max = self.stars[i].link.len();
}
if self.stars[i].link.len() < min {
min = self.stars[i].link.len();
}
}
total = total / (self.stars.len() - 2) as f64;
return (total, min, max);
}
pub fn number_of_vertices(&self) -> usize {
(self.stars.len() - 1 - self.removed_indices.len())
}
pub fn number_of_triangles(&self) -> usize {
let mut count: usize = 0;
for (i, star) in self.stars.iter().enumerate() {
for (j, value) in star.link.iter().enumerate() {
if i < *value {
let k = star.link[star.link.next_index(j)];
if i < k {
let tr = Triangle {
tr0: i,
tr1: *value,
tr2: k,
};
if tr.is_infinite() == false {
count = count + 1;
}
}
}
}
}
count
}
pub fn number_of_removed_vertices(&self) -> usize {
self.removed_indices.len()
}
pub fn is_vertex_removed(&self, v: usize) -> bool {
let re = self.removed_indices.iter().position(|&x| x == v);
if re == None {
false
} else {
true
}
}
pub fn convex_hull(&self) -> Vec<usize> {
let mut re: Vec<usize> = Vec::new();
for x in self.stars[0].link.iter() {
re.push(*x);
}
re.reverse();
re
}
pub fn number_of_vertices_on_convex_hull(&self) -> usize {
if self.is_init == false {
return 0;
}
return self.stars[0].link.len();
}
pub fn is_vertex_convex_hull(&self, v: usize) -> bool {
if v == 0 {
return false;
}
if self.vertex_exists(v) == false {
return false;
}
self.stars[v].link.contains_infinite_vertex()
}
pub fn locate(&self, px: f64, py: f64) -> Option<Triangle> {
let p: [f64; 3] = [px, py, 0.0];
let re = self.walk(&p);
match re.is_infinite() {
true => None,
false => Some(re),
}
}
pub fn closest_point(&self, px: f64, py: f64) -> Option<usize> {
let re = self.locate(px, py);
if re.is_none() == true {
return None;
}
let p: [f64; 3] = [px, py, 0.0];
let tr = re.unwrap();
let mut d = std::f64::MAX;
let mut chosen: usize = 3;
if geom::distance2d_squared(&self.stars[tr.tr0].pt, &p) < d {
d = geom::distance2d_squared(&self.stars[tr.tr0].pt, &p);
chosen = 0;
}
if geom::distance2d_squared(&self.stars[tr.tr1].pt, &p) < d {
d = geom::distance2d_squared(&self.stars[tr.tr1].pt, &p);
chosen = 1;
}
if geom::distance2d_squared(&self.stars[tr.tr2].pt, &p) < d {
chosen = 2;
}
if chosen == 0 {
return Some(tr.tr0);
} else if chosen == 1 {
return Some(tr.tr1);
} else {
return Some(tr.tr2);
}
}
fn walk(&self, x: &[f64]) -> Triangle {
let mut cur = self.cur;
if self.jump_and_walk == true {
let mut rng = thread_rng();
let mut d: f64 = geom::distance2d_squared(&self.stars[self.cur].pt, &x);
let n = (self.stars.len() as f64).powf(0.25);
for _i in 0..n as i32 {
let re: usize = rng.gen_range(1, self.stars.len());
if self.stars[re].is_deleted() == true {
continue;
}
let dtemp = geom::distance2d_squared(&self.stars[re].pt, &x);
if dtemp < d {
cur = re;
d = dtemp;
}
}
}
let mut tr = Triangle {
tr0: 0,
tr1: 0,
tr2: 0,
};
tr.tr0 = cur;
if self.stars[cur].link[0] == 0 {
tr.tr1 = self.stars[cur].link[1];
tr.tr2 = self.stars[cur].link[2];
} else {
tr.tr1 = self.stars[cur].link[0];
tr.tr2 = self.stars[cur].link[1];
}
if geom::orient2d(
&self.stars[tr.tr0].pt,
&self.stars[tr.tr1].pt,
&x,
self.robust_predicates,
) == -1
{
if geom::orient2d(
&self.stars[tr.tr1].pt,
&self.stars[tr.tr2].pt,
&x,
self.robust_predicates,
) != -1
{
mem::swap(&mut tr.tr0, &mut tr.tr1);
mem::swap(&mut tr.tr1, &mut tr.tr2);
} else {
mem::swap(&mut tr.tr1, &mut tr.tr2);
mem::swap(&mut tr.tr0, &mut tr.tr1);
}
}
loop {
if tr.is_infinite() == true {
break;
}
if geom::orient2d(
&self.stars[tr.tr1].pt,
&self.stars[tr.tr2].pt,
&x,
self.robust_predicates,
) != -1
{
if geom::orient2d(
&self.stars[tr.tr2].pt,
&self.stars[tr.tr0].pt,
&x,
self.robust_predicates,
) != -1
{
break;
} else {
let prev = self.stars[tr.tr2].link.get_prev_vertex(tr.tr0).unwrap();
tr.tr1 = tr.tr2;
tr.tr2 = prev;
}
} else {
let prev = self.stars[tr.tr1].link.get_prev_vertex(tr.tr2).unwrap();
tr.tr0 = tr.tr2;
tr.tr2 = prev;
}
}
return tr;
}
fn flip22(&mut self, tr: &Triangle, opposite: usize) -> (Triangle, Triangle) {
self.stars[tr.tr0].link.insert_after_v(opposite, tr.tr1);
self.stars[tr.tr1].link.delete(tr.tr2);
self.stars[opposite].link.insert_after_v(tr.tr0, tr.tr2);
self.stars[tr.tr2].link.delete(tr.tr1);
let ret0 = Triangle {
tr0: tr.tr0,
tr1: tr.tr1,
tr2: opposite,
};
let ret1 = Triangle {
tr0: tr.tr0,
tr1: opposite,
tr2: tr.tr2,
};
(ret0, ret1)
}
fn get_opposite_vertex(&self, tr: &Triangle) -> usize {
self.stars[tr.tr2].link.get_next_vertex(tr.tr1).unwrap()
}
pub fn all_vertices(&self) -> Vec<Vec<f64>> {
let mut pts: Vec<Vec<f64>> = Vec::with_capacity(self.stars.len() - 1);
for i in 0..self.stars.len() {
pts.push(self.stars[i].pt.to_vec());
}
pts
}
pub fn all_edges(&self) -> Vec<usize> {
let mut edges: Vec<usize> = Vec::new();
for i in 1..self.stars.len() {
for value in self.stars[i].link.iter() {
if (*value != 0) && (i < *value) {
edges.push(i);
edges.push(*value);
}
}
}
edges
}
pub fn all_triangles(&self) -> Vec<Triangle> {
let mut trs: Vec<Triangle> = Vec::new();
for (i, star) in self.stars.iter().enumerate() {
for (j, value) in star.link.iter().enumerate() {
if i < *value {
let k = star.link[star.link.next_index(j)];
if i < k {
let tr = Triangle {
tr0: i,
tr1: *value,
tr2: k,
};
if tr.is_infinite() == false {
trs.push(tr);
}
}
}
}
}
trs
}
pub fn is_valid(&self) -> bool {
self.is_valid_ch_convex() && self.is_valid_circumcircle()
}
fn is_valid_circumcircle(&self) -> bool {
let mut re = true;
let trs = self.all_triangles();
for tr in trs.iter() {
for i in 1..self.stars.len() {
if self.stars[i].is_deleted() == false
&& geom::incircle(
&self.stars[tr.tr0].pt,
&self.stars[tr.tr1].pt,
&self.stars[tr.tr2].pt,
&self.stars[i].pt,
self.robust_predicates,
) > 0
{
println!("NOT DELAUNAY FFS!");
println!("{} with {}", tr, i);
re = false
}
}
}
re
}
fn is_valid_ch_convex(&self) -> bool {
let mut re = true;
let ch = self.convex_hull();
for i in 0..ch.len() {
if geom::orient2d(
&self.stars[ch[i % ch.len()]].pt,
&self.stars[ch[(i + 1) % ch.len()]].pt,
&self.stars[ch[(i + 2) % ch.len()]].pt,
self.robust_predicates,
) == -1
{
re = false;
break;
}
}
if re == false {
println!("CONVEX NOT CONVEX");
}
return re;
}
fn remove_on_convex_hull(&mut self, v: usize) -> Result<usize, &'static str> {
let mut adjs: Vec<usize> = Vec::new();
for each in self.stars[v].link.iter() {
adjs.push(*each);
}
let mut cur: usize = 0;
let mut nadjs = adjs.len();
let mut steps = 0;
while adjs.len() > 3 {
if steps == nadjs {
break;
}
if adjs.len() == nadjs {
steps += 1;
} else {
nadjs = adjs.len();
steps = 0;
}
let a = cur % adjs.len();
let b = (cur + 1) % adjs.len();
let c = (cur + 2) % adjs.len();
if adjs[a] == 0 || adjs[b] == 0 || adjs[c] == 0 {
cur += 1;
continue;
}
if (geom::orient2d(
&self.stars[adjs[a]].pt,
&self.stars[adjs[b]].pt,
&self.stars[adjs[c]].pt,
self.robust_predicates,
) == 1)
&& (geom::orient2d(
&self.stars[adjs[a]].pt,
&self.stars[adjs[c]].pt,
&self.stars[v].pt,
self.robust_predicates,
) >= 0)
{
let cur2 = cur + 3;
let mut isdel = true;
for i in 0..adjs.len() - 3 {
if adjs[(cur2 + i) % adjs.len()] != 0
&& geom::incircle(
&self.stars[adjs[a]].pt,
&self.stars[adjs[b]].pt,
&self.stars[adjs[c]].pt,
&self.stars[adjs[(cur2 + i) % adjs.len()]].pt,
self.robust_predicates,
) > 0
{
isdel = false;
break;
}
}
if isdel == true {
let t = Triangle {
tr0: adjs[a],
tr1: adjs[b],
tr2: v,
};
self.flip22(&t, adjs[c]);
adjs.remove((cur + 1) % adjs.len());
}
}
cur += 1;
}
if adjs.len() == 3 {
self.flip31(v);
return Ok(self.stars.len() - 1);
} else {
self.stars[adjs[1]].link.delete(v);
self.stars[*(adjs.last().unwrap())].link.delete(v);
for i in 2..(adjs.len() - 1) {
self.stars[adjs[i]].link.replace(v, 0);
self.stars[adjs[i]].link.infinite_first();
}
let mut prev = v;
for i in 2..(adjs.len() - 1) {
self.stars[0].link.insert_after_v(adjs[i], prev);
prev = adjs[i];
}
self.stars[adjs[0]].link.delete(v);
self.stars[v].link.clear();
self.stars[v].pt[0] = -999.9;
self.stars[v].pt[1] = -999.9;
self.stars[v].pt[2] = -999.9;
self.removed_indices.push(v);
if adjs[0] != 0 {
self.cur = adjs[0];
} else {
self.cur = adjs[1];
}
return Ok(self.stars.len() - 1);
}
}
pub fn remove(&mut self, v: usize) -> Result<usize, &'static str> {
if v == 0 {
return Err("Cannot remove the infinite vertex");
}
if self.vertex_exists(v) == false {
return Err("Vertex does not exist");
}
if self.is_vertex_convex_hull(v) {
return self.remove_on_convex_hull(v);
}
let mut adjs: Vec<usize> = Vec::new();
for each in self.stars[v].link.iter() {
adjs.push(*each);
}
let mut cur: usize = 0;
while adjs.len() > 3 {
let a = cur % adjs.len();
let b = (cur + 1) % adjs.len();
let c = (cur + 2) % adjs.len();
if (geom::orient2d(
&self.stars[adjs[a]].pt,
&self.stars[adjs[b]].pt,
&self.stars[adjs[c]].pt,
self.robust_predicates,
) == 1)
&& (geom::orient2d(
&self.stars[adjs[a]].pt,
&self.stars[adjs[c]].pt,
&self.stars[v].pt,
self.robust_predicates,
) >= 0)
{
let cur2 = cur + 3;
let mut isdel = true;
for i in 0..adjs.len() - 3 {
if geom::incircle(
&self.stars[adjs[a]].pt,
&self.stars[adjs[b]].pt,
&self.stars[adjs[c]].pt,
&self.stars[adjs[(cur2 + i) % adjs.len()]].pt,
self.robust_predicates,
) > 0
{
isdel = false;
break;
}
}
if isdel == true {
let t = Triangle {
tr0: adjs[a],
tr1: adjs[b],
tr2: v,
};
self.flip22(&t, adjs[c]);
adjs.remove((cur + 1) % adjs.len());
}
}
cur = cur + 1;
}
self.flip31(v);
return Ok(self.stars.len() - 1);
}
pub fn write_obj(&self, path: String, twod: bool) -> std::io::Result<()> {
let trs = self.all_triangles();
let mut f = File::create(path)?;
for i in 1..self.stars.len() {
if twod == true {
write!(
f,
"v {} {} {}\n",
self.stars[i].pt[0], self.stars[i].pt[1], 0
)
.unwrap();
} else {
write!(
f,
"v {} {} {}\n",
self.stars[i].pt[0], self.stars[i].pt[1], self.stars[i].pt[2]
)
.unwrap();
}
}
for tr in trs.iter() {
write!(f, "f {} {} {}\n", tr.tr0, tr.tr1, tr.tr2).unwrap();
}
Ok(())
}
pub fn printme(&self, withxyz: bool) -> String {
let mut s = String::from("**********\n");
for (i, p) in self.stars.iter().enumerate() {
s.push_str(&format!("{}: [", i));
for each in p.link.iter() {
s.push_str(&format!("{} - ", each));
}
s.push_str(&format!("]\n"));
if withxyz == true {
s.push_str(&format!("\t{:?}\n", self.stars[i].pt));
}
}
s.push_str("**********\n");
s
}
fn vertex_exists(&self, v: usize) -> bool {
let mut re = true;
if v >= self.stars.len() || self.is_vertex_removed(v) == true {
re = false;
}
re
}
}
impl fmt::Display for Triangulation {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
fmt.write_str("======== TRIANGULATION ========\n")?;
fmt.write_str(&format!("# vertices: {:19}\n", self.number_of_vertices()))?;
fmt.write_str(&format!("# triangles: {:18}\n", self.number_of_triangles()))?;
fmt.write_str(&format!(
"# convex hull: {:16}\n",
self.number_of_vertices_on_convex_hull()
))?;
fmt.write_str(&format!("---\nrobust: {}\n", self.robust_predicates))?;
fmt.write_str("===============================\n")?;
Ok(())
}
}