use itertools::Itertools;
use nalgebra::{allocator::Allocator, Const, DefaultAllocator, DimName, OPoint, Point2};
use spade::{ConstrainedDelaunayTriangulation, Point2 as SP2, SpadeNum, Triangulation};
use crate::prelude::{Contains, PolygonMesh, Tessellation};
use super::{orientation, FloatingPoint, Orientation};
#[derive(Debug, Clone)]
pub struct PolygonBoundary<T: FloatingPoint, D: DimName>
where
DefaultAllocator: Allocator<D>,
{
vertices: Vec<OPoint<T, D>>,
}
impl<T: FloatingPoint, D: DimName> PolygonBoundary<T, D>
where
DefaultAllocator: Allocator<D>,
{
pub fn new(vertices: Vec<OPoint<T, D>>) -> Self {
Self { vertices }
}
pub fn vertices(&self) -> &Vec<OPoint<T, D>> {
&self.vertices
}
}
impl<T: FloatingPoint, D: DimName> FromIterator<OPoint<T, D>> for PolygonBoundary<T, D>
where
DefaultAllocator: Allocator<D>,
{
fn from_iter<I: IntoIterator<Item = OPoint<T, D>>>(iter: I) -> Self {
Self::new(iter.into_iter().collect())
}
}
impl<T: FloatingPoint> Contains<OPoint<T, Const<2>>> for PolygonBoundary<T, Const<2>> {
type Option = ();
fn contains(&self, c: &Point2<T>, _option: Self::Option) -> anyhow::Result<bool> {
let winding_number = self.vertices().iter().circular_tuple_windows().fold(
0_i32,
move |winding_number, (p0, p1)| {
if p0.y <= c.y {
if p1.y >= c.y {
let o = orientation(p0, p1, c);
if o == Orientation::CounterClockwise && p1.y != c.y {
return winding_number + 1;
}
}
} else if p1.y <= c.y {
let o = orientation(p0, p1, c);
if o == Orientation::Clockwise {
return winding_number - 1;
}
}
winding_number
},
);
Ok(winding_number != 0)
}
}
impl<T: FloatingPoint + SpadeNum> Tessellation<()> for PolygonBoundary<T, Const<2>> {
type Output = anyhow::Result<PolygonMesh<T, Const<2>>>;
fn tessellate(&self, _options: ()) -> Self::Output {
let mut cdt = ConstrainedDelaunayTriangulation::<SP2<T>>::default();
let mut vertex_handles = Vec::new();
for point in self.vertices() {
let spade_point = SP2::new(point.x, point.y);
let handle = cdt.insert(spade_point)?;
vertex_handles.push(handle);
}
for i in 0..vertex_handles.len() {
let next = (i + 1) % vertex_handles.len();
if cdt.can_add_constraint(vertex_handles[i], vertex_handles[next]) {
cdt.add_constraint(vertex_handles[i], vertex_handles[next]);
}
}
let mut vertices = Vec::new();
let mut faces = Vec::new();
let mut vertex_map = std::collections::HashMap::new();
for face in cdt.inner_faces() {
let indices = face
.vertices()
.iter()
.map(|vertex| {
let idx = if let Some(&existing_idx) = vertex_map.get(&vertex.fix()) {
existing_idx
} else {
let pos = vertex.position();
let new_idx = vertices.len();
vertices.push(Point2::new(pos.x, pos.y));
vertex_map.insert(vertex.fix(), new_idx);
new_idx
};
idx
})
.collect_array::<3>();
if let Some(indices) = indices {
faces.push(indices);
}
}
Ok(PolygonMesh::new(vertices, faces))
}
}
#[cfg(feature = "serde")]
impl<T, D: DimName> serde::Serialize for PolygonBoundary<T, D>
where
T: FloatingPoint + serde::Serialize,
DefaultAllocator: Allocator<D>,
<DefaultAllocator as nalgebra::allocator::Allocator<D>>::Buffer<T>: serde::Serialize,
{
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: serde::Serializer,
{
use serde::ser::SerializeStruct;
let mut state = serializer.serialize_struct("PolygonBoundary", 1)?;
state.serialize_field("vertices", &self.vertices)?;
state.end()
}
}
#[cfg(feature = "serde")]
impl<'de, T, D: DimName> serde::Deserialize<'de> for PolygonBoundary<T, D>
where
T: FloatingPoint + serde::Deserialize<'de>,
DefaultAllocator: Allocator<D>,
<DefaultAllocator as nalgebra::allocator::Allocator<D>>::Buffer<T>: serde::Deserialize<'de>,
{
fn deserialize<S>(deserializer: S) -> Result<Self, S::Error>
where
S: serde::Deserializer<'de>,
{
use serde::de::{self, MapAccess, Visitor};
#[derive(Debug)]
enum Field {
Vertices,
}
impl<'de> serde::Deserialize<'de> for Field {
fn deserialize<S>(deserializer: S) -> Result<Self, S::Error>
where
S: serde::Deserializer<'de>,
{
struct FieldVisitor;
impl Visitor<'_> for FieldVisitor {
type Value = Field;
fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
formatter.write_str("`vertices`")
}
fn visit_str<E>(self, value: &str) -> Result<Field, E>
where
E: de::Error,
{
match value {
"vertices" => Ok(Field::Vertices),
_ => Err(de::Error::unknown_field(value, FIELDS)),
}
}
}
deserializer.deserialize_identifier(FieldVisitor)
}
}
struct PolygonBoundaryVisitor<T, D>(std::marker::PhantomData<(T, D)>);
impl<T, D> PolygonBoundaryVisitor<T, D> {
fn new() -> Self {
Self(std::marker::PhantomData)
}
}
impl<'de, T, D: DimName> Visitor<'de> for PolygonBoundaryVisitor<T, D>
where
T: FloatingPoint + serde::Deserialize<'de>,
DefaultAllocator: Allocator<D>,
<DefaultAllocator as nalgebra::allocator::Allocator<D>>::Buffer<T>:
serde::Deserialize<'de>,
{
type Value = PolygonBoundary<T, D>;
fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
formatter.write_str("struct PolygonBoundary")
}
fn visit_map<V>(self, mut map: V) -> Result<Self::Value, V::Error>
where
V: MapAccess<'de>,
{
let mut vertices = None;
while let Some(key) = map.next_key()? {
match key {
Field::Vertices => {
if vertices.is_some() {
return Err(de::Error::duplicate_field("vertices"));
}
vertices = Some(map.next_value()?);
}
}
}
let vertices = vertices.ok_or_else(|| de::Error::missing_field("vertices"))?;
Ok(PolygonBoundary::new(vertices))
}
}
const FIELDS: &[&str] = &["vertices"];
deserializer.deserialize_struct("PolygonBoundary", FIELDS, PolygonBoundaryVisitor::new())
}
}