#![forbid(unsafe_code)]
use super::{
facet::{FacetHandle, facet_key_from_vertices},
simplex::{NeighborSlot, Simplex, SimplexValidationError},
traits::data_type::DataType,
util::{
deduplication::coords_equal_exact, periodic_facet_key_from_lifted_vertices, usize_to_u8,
},
vertex::{Vertex, VertexValidationError},
};
use crate::core::algorithms::flips::FlipError;
use crate::core::collections::{
Entry, FacetToSimplicesMap, FastHashMap, MAX_PRACTICAL_DIMENSION_SIZE, NeighborBuffer,
SimplexKeySet, SimplexRemovalBuffer, SimplexVerticesMap, SmallBuffer, StorageMap,
UuidToSimplexKeyMap, UuidToVertexKeyMap, VertexKeyBuffer, VertexKeySet,
fast_hash_map_with_capacity,
};
use crate::core::validation::TriangulationValidationError;
use crate::geometry::traits::coordinate::CoordinateScalar;
use crate::validation::DelaunayTriangulationValidationError;
use serde::{
Deserialize, Deserializer, Serialize,
de::{self, MapAccess, Visitor},
ser::SerializeStruct,
};
use slotmap::{Key, new_key_type};
use std::{
cmp::Ordering as CmpOrdering,
collections::VecDeque,
fmt::{self, Debug},
marker::PhantomData,
sync::{
Arc,
atomic::{AtomicU64, Ordering},
},
};
use thiserror::Error;
use uuid::Uuid;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum TriangulationConstructionState {
Incomplete(usize),
Constructed,
}
impl Default for TriangulationConstructionState {
fn default() -> Self {
Self::Incomplete(0)
}
}
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[non_exhaustive]
pub enum TdsConstructionError {
#[error("Validation error during construction: {0}")]
ValidationError(#[from] TdsError),
#[error("Duplicate UUID: {entity:?} with UUID {uuid} already exists")]
DuplicateUuid {
entity: EntityKind,
uuid: Uuid,
},
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum EntityKind {
Vertex,
Simplex,
}
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[non_exhaustive]
pub enum GeometricError {
#[error("Degenerate geometric orientation: {message}")]
DegenerateOrientation {
message: String,
},
#[error("Negative geometric orientation: {message}")]
NegativeOrientation {
message: String,
},
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum SharedFacetMismatchSide {
SourceFacet,
NeighborFacet,
}
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[non_exhaustive]
pub enum NeighborValidationError {
#[error("Neighbor vector length {actual} != expected {expected} during {context}")]
LengthMismatch {
actual: usize,
expected: usize,
context: String,
},
#[error(
"Simplex {simplex_uuid} (key {simplex_key:?}) has unassigned neighbor slot at facet {facet_index} during {context}"
)]
UnassignedNeighborSlot {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
context: String,
},
#[error(
"Simplex {simplex_uuid} (key {simplex_key:?}) has non-periodic self-neighbor at facet {facet_index}"
)]
NonPeriodicSelfNeighbor {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
},
#[error(
"Simplex {simplex_uuid} (key {simplex_key:?}) facet {facet_index} references missing neighbor {neighbor_key:?} during {context}"
)]
MissingNeighborSimplex {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
neighbor_key: SimplexKey,
context: String,
},
#[error(
"Simplex {simplex_uuid} (key {simplex_key:?}) facet {facet_index} references removed neighbor {neighbor_key:?}"
)]
ReferencedRemovedNeighbor {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
neighbor_key: SimplexKey,
},
#[error(
"Simplex {simplex_uuid} (key {simplex_key:?}) facet {facet_index} shares {shared_count} vertices with neighbor, expected {expected}"
)]
SharedVertexCountMismatch {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
shared_count: usize,
expected: usize,
},
#[error(
"Simplex {simplex_uuid} (key {simplex_key:?}) neighbor at facet {facet_index} is opposite {observed_opposite:?}, expected {expected_opposite}"
)]
OppositeVertexMismatch {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
observed_opposite: Option<usize>,
expected_opposite: usize,
},
#[error(
"Simplex {simplex_uuid} (key {simplex_key:?}) facet {facet_index} key {facet_key} is missing from facet incidence"
)]
FacetIncidenceMissing {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
facet_key: u64,
},
#[error(
"Simplex {simplex_uuid} (key {simplex_key:?}) facet {facet_index} key {facet_key} does not reference the edited facet"
)]
FacetIncidenceDoesNotReferenceSimplex {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
facet_key: u64,
},
#[error(
"Simplex {simplex_uuid} (key {simplex_key:?}) facet {facet_index} key {facet_key} is shared by {simplex_count} simplices"
)]
FacetIncidenceMultiplicity {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
facet_key: u64,
simplex_count: usize,
},
#[error(
"Simplex {simplex_uuid} (key {simplex_key:?}) facet {facet_index} proposed neighbor {proposed_neighbor:?} does not match expected {expected_neighbor:?}"
)]
NeighborIncidenceMismatch {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
proposed_neighbor: Option<SimplexKey>,
expected_neighbor: Option<SimplexKey>,
},
#[error("Neighbor facet index {facet_index} out of bounds for {slot_count} neighbor slots")]
NeighborSlotOutOfBounds {
facet_index: usize,
slot_count: usize,
},
#[error(
"Could not determine mirror facet during {context}: simplex {simplex_uuid}[{facet_index}] -> neighbor {neighbor_uuid}"
)]
MirrorFacetMissing {
simplex_uuid: Uuid,
facet_index: usize,
neighbor_uuid: Uuid,
context: String,
},
#[error(
"Mirror facet is ambiguous: simplex {simplex_uuid} and neighbor {neighbor_uuid} differ by more than one vertex"
)]
MirrorFacetAmbiguous {
simplex_uuid: Uuid,
neighbor_uuid: Uuid,
},
#[error(
"Mirror facet could not be determined: simplex {simplex_uuid} and neighbor {neighbor_uuid} share all vertices"
)]
MirrorFacetDuplicateSimplices {
simplex_uuid: Uuid,
neighbor_uuid: Uuid,
},
#[error(
"Mirror facet index mismatch: simplex {simplex_uuid}[{facet_index}] -> neighbor {neighbor_uuid}; observed {observed_mirror_index}, expected {expected_mirror_index}"
)]
MirrorFacetIndexMismatch {
simplex_uuid: Uuid,
facet_index: usize,
neighbor_uuid: Uuid,
observed_mirror_index: usize,
expected_mirror_index: usize,
},
#[error(
"Shared facet mismatch ({side:?}): simplex {simplex_uuid}[{facet_index}] and neighbor {neighbor_uuid}[{mirror_index}] are missing vertex {missing_vertex:?}"
)]
SharedFacetMissingVertex {
side: SharedFacetMismatchSide,
simplex_uuid: Uuid,
facet_index: usize,
neighbor_uuid: Uuid,
mirror_index: usize,
missing_vertex: VertexKey,
},
#[error(
"Neighbor back-reference mismatch during {context}: simplex {simplex_uuid}[{facet_index}] -> {neighbor_key:?} should be mirrored by {neighbor_uuid}[{mirror_index}] -> {simplex_key:?}, found {observed:?}"
)]
BackReferenceMismatch {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
neighbor_key: SimplexKey,
neighbor_uuid: Uuid,
mirror_index: usize,
observed: Option<SimplexKey>,
context: String,
},
#[error(
"Neighbor simplex {neighbor_uuid}[{mirror_index}] already references {existing_back_ref:?}; refusing to overwrite with {requested_back_ref:?}"
)]
ExistingBackReferenceConflict {
neighbor_uuid: Uuid,
mirror_index: usize,
existing_back_ref: SimplexKey,
requested_back_ref: SimplexKey,
},
#[error(
"Boundary facet {facet_key} unexpectedly has neighbor {neighbor_key:?} across simplex {simplex_uuid}[{facet_index}]"
)]
BoundaryFacetHasNeighbor {
facet_key: u64,
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
neighbor_key: SimplexKey,
},
#[error(
"Boundary facet {facet_key} has non-periodic self-neighbor across simplex {simplex_uuid}[{facet_index}]"
)]
BoundaryFacetHasNonPeriodicSelfNeighbor {
facet_key: u64,
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
},
#[error(
"Interior facet {facet_key} has inconsistent neighbor pointers: {first_simplex_uuid}[{first_facet_index}] -> {first_neighbor:?}, {second_simplex_uuid}[{second_facet_index}] -> {second_neighbor:?}"
)]
InteriorFacetNeighborMismatch {
facet_key: u64,
first_simplex_key: SimplexKey,
first_simplex_uuid: Uuid,
first_facet_index: usize,
first_neighbor: Option<SimplexKey>,
second_simplex_key: SimplexKey,
second_simplex_uuid: Uuid,
second_facet_index: usize,
second_neighbor: Option<SimplexKey>,
},
#[error(
"Could not build facet order during {context}: simplex {simplex_uuid} (key {simplex_key:?}) facet {facet_index}: {source}"
)]
FacetOrderUnavailable {
simplex_key: SimplexKey,
simplex_uuid: Uuid,
facet_index: usize,
context: String,
#[source]
source: Box<FlipError>,
},
#[error("Flip neighbor wiring failed: {reason}")]
FlipNeighborWiring {
#[source]
reason: Box<crate::core::algorithms::flips::FlipNeighborWiringError>,
},
#[error("{message}")]
Other {
message: String,
},
}
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[non_exhaustive]
pub enum TdsError {
#[error("Invalid vertex {vertex_id}: {source}")]
InvalidVertex {
vertex_id: Uuid,
source: VertexValidationError,
},
#[error("Invalid simplex {simplex_id}: {source}")]
InvalidSimplex {
simplex_id: Uuid,
source: SimplexValidationError,
},
#[error("Invalid neighbor relationships: {reason}")]
InvalidNeighbors {
#[source]
reason: NeighborValidationError,
},
#[error(
"Orientation invariant violated between simplices {simplex1_uuid} and {simplex2_uuid}; shared facet orderings {facet_vertices:?} vs {simplex2_facet_vertices:?} (simplex1 facet index {simplex1_facet_index}, simplex2 facet index {simplex2_facet_index}, observed_odd_permutation={observed_odd_permutation}, expected_odd_permutation={expected_odd_permutation})"
)]
OrientationViolation {
simplex1_key: SimplexKey,
simplex1_uuid: Uuid,
simplex2_key: SimplexKey,
simplex2_uuid: Uuid,
simplex1_facet_index: usize,
simplex2_facet_index: usize,
facet_vertices: Vec<VertexKey>,
simplex2_facet_vertices: Vec<VertexKey>,
observed_odd_permutation: bool,
expected_odd_permutation: bool,
},
#[error("Duplicate simplices detected: {message}")]
DuplicateSimplices {
message: String,
},
#[error(
"Facet {facet_key} exceeds incident-simplex limit: observed {attempted_incident_count} incident simplices, max {max_incident_count}; candidate/offending simplex {candidate_simplex_uuid} facet {candidate_facet_index}; other incident simplices {existing_incident_count}"
)]
FacetSharingViolation {
facet_key: u64,
existing_incident_count: usize,
attempted_incident_count: usize,
max_incident_count: usize,
candidate_simplex_uuid: Uuid,
candidate_facet_index: usize,
},
#[error("Failed to create simplex: {message}")]
FailedToCreateSimplex {
message: String,
},
#[error("Simplices {simplex1:?} and {simplex2:?} are not neighbors")]
NotNeighbors {
simplex1: Uuid,
simplex2: Uuid,
},
#[error("{entity:?} mapping inconsistency: {message}")]
MappingInconsistency {
entity: EntityKind,
message: String,
},
#[error("Failed to retrieve vertex keys for simplex {simplex_id}: {message}")]
VertexKeyRetrievalFailed {
simplex_id: Uuid,
message: String,
},
#[error("Simplex key {simplex_key:?} not found: {context}")]
SimplexNotFound {
simplex_key: SimplexKey,
context: String,
},
#[error("Vertex key {vertex_key:?} not found: {context}")]
VertexNotFound {
vertex_key: VertexKey,
context: String,
},
#[error("Dimension mismatch: expected {expected}, got {actual} — {context}")]
DimensionMismatch {
expected: usize,
actual: usize,
context: String,
},
#[error("Index out of bounds: index {index}, bound {bound} — {context}")]
IndexOutOfBounds {
index: usize,
bound: usize,
context: String,
},
#[error("Internal data structure inconsistency: {message}")]
InconsistentDataStructure {
message: String,
},
#[error(transparent)]
Geometric(#[from] GeometricError),
#[error("Facet operation failed: {0}")]
FacetError(#[from] super::facet::FacetError),
#[error("Duplicate coordinates in simplex {simplex_id}: {message}")]
DuplicateCoordinatesInSimplex {
simplex_id: Uuid,
message: String,
},
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub enum TdsErrorKind {
InvalidVertex,
InvalidSimplex,
InvalidNeighbors,
OrientationViolation,
DuplicateSimplices,
FacetSharingViolation,
FailedToCreateSimplex,
NotNeighbors,
MappingInconsistency,
VertexKeyRetrievalFailed,
SimplexNotFound,
VertexNotFound,
DimensionMismatch,
IndexOutOfBounds,
InconsistentDataStructure,
Geometric,
FacetError,
DuplicateCoordinatesInSimplex,
}
impl From<&TdsError> for TdsErrorKind {
fn from(source: &TdsError) -> Self {
match source {
TdsError::InvalidVertex { .. } => Self::InvalidVertex,
TdsError::InvalidSimplex { .. } => Self::InvalidSimplex,
TdsError::InvalidNeighbors { .. } => Self::InvalidNeighbors,
TdsError::OrientationViolation { .. } => Self::OrientationViolation,
TdsError::DuplicateSimplices { .. } => Self::DuplicateSimplices,
TdsError::FacetSharingViolation { .. } => Self::FacetSharingViolation,
TdsError::FailedToCreateSimplex { .. } => Self::FailedToCreateSimplex,
TdsError::NotNeighbors { .. } => Self::NotNeighbors,
TdsError::MappingInconsistency { .. } => Self::MappingInconsistency,
TdsError::VertexKeyRetrievalFailed { .. } => Self::VertexKeyRetrievalFailed,
TdsError::SimplexNotFound { .. } => Self::SimplexNotFound,
TdsError::VertexNotFound { .. } => Self::VertexNotFound,
TdsError::DimensionMismatch { .. } => Self::DimensionMismatch,
TdsError::IndexOutOfBounds { .. } => Self::IndexOutOfBounds,
TdsError::InconsistentDataStructure { .. } => Self::InconsistentDataStructure,
TdsError::Geometric(_) => Self::Geometric,
TdsError::FacetError(_) => Self::FacetError,
TdsError::DuplicateCoordinatesInSimplex { .. } => Self::DuplicateCoordinatesInSimplex,
}
}
}
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[error(transparent)]
#[must_use]
pub struct TdsMutationError(TdsError);
impl TdsMutationError {
#[must_use]
pub const fn as_tds_error(&self) -> &TdsError {
&self.0
}
#[must_use]
pub fn into_inner(self) -> TdsError {
self.0
}
}
impl From<TdsError> for TdsMutationError {
fn from(err: TdsError) -> Self {
Self(err)
}
}
impl From<TdsMutationError> for TdsError {
fn from(err: TdsMutationError) -> Self {
err.0
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub enum InvariantKind {
VertexValidity,
SimplexValidity,
SimplexCoordinateUniqueness,
VertexMappings,
SimplexMappings,
SimplexVertexKeys,
VertexIncidence,
DuplicateSimplices,
FacetSharing,
NeighborConsistency,
CoherentOrientation,
Connectedness,
Topology,
DelaunayProperty,
}
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[non_exhaustive]
pub enum InvariantError {
#[error(transparent)]
Tds(#[from] TdsError),
#[error(transparent)]
Triangulation(#[from] TriangulationValidationError),
#[error(transparent)]
Delaunay(#[from] DelaunayTriangulationValidationError),
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub enum InvariantErrorSummaryKind {
Tds,
Triangulation,
Delaunay,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub enum TriangulationValidationErrorKind {
ManifoldFacetMultiplicity,
BoundaryRidgeMultiplicity,
RidgeLinkNotManifold,
VertexLinkNotManifold,
EulerCharacteristicMismatch,
IsolatedVertex,
Disconnected,
OrientationPromotionNonConvergence,
}
impl From<&TriangulationValidationError> for TriangulationValidationErrorKind {
fn from(source: &TriangulationValidationError) -> Self {
match source {
TriangulationValidationError::ManifoldFacetMultiplicity { .. } => {
Self::ManifoldFacetMultiplicity
}
TriangulationValidationError::BoundaryRidgeMultiplicity { .. } => {
Self::BoundaryRidgeMultiplicity
}
TriangulationValidationError::RidgeLinkNotManifold { .. } => Self::RidgeLinkNotManifold,
TriangulationValidationError::VertexLinkNotManifold { .. } => {
Self::VertexLinkNotManifold
}
TriangulationValidationError::EulerCharacteristicMismatch { .. } => {
Self::EulerCharacteristicMismatch
}
TriangulationValidationError::IsolatedVertex { .. } => Self::IsolatedVertex,
TriangulationValidationError::Disconnected { .. } => Self::Disconnected,
TriangulationValidationError::OrientationPromotionNonConvergence { .. } => {
Self::OrientationPromotionNonConvergence
}
}
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub enum DelaunayValidationErrorKind {
Tds,
Triangulation,
VerificationFailed,
RepairFailed,
RepairOperationFailed,
}
impl From<&DelaunayTriangulationValidationError> for DelaunayValidationErrorKind {
fn from(source: &DelaunayTriangulationValidationError) -> Self {
match source {
DelaunayTriangulationValidationError::Tds(_) => Self::Tds,
DelaunayTriangulationValidationError::Triangulation(_) => Self::Triangulation,
DelaunayTriangulationValidationError::VerificationFailed { .. } => {
Self::VerificationFailed
}
DelaunayTriangulationValidationError::RepairFailed { .. } => Self::RepairFailed,
DelaunayTriangulationValidationError::RepairOperationFailed { .. } => {
Self::RepairOperationFailed
}
}
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub enum InvariantErrorSummaryDetail {
Tds(TdsErrorKind),
Triangulation(TriangulationValidationErrorKind),
Delaunay(DelaunayValidationErrorKind),
}
#[must_use]
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[error("{message}")]
pub struct InvariantErrorSummary {
pub kind: InvariantErrorSummaryKind,
pub detail: InvariantErrorSummaryDetail,
pub message: String,
}
impl From<InvariantError> for InvariantErrorSummary {
fn from(source: InvariantError) -> Self {
let kind = match &source {
InvariantError::Tds(_) => InvariantErrorSummaryKind::Tds,
InvariantError::Triangulation(_) => InvariantErrorSummaryKind::Triangulation,
InvariantError::Delaunay(_) => InvariantErrorSummaryKind::Delaunay,
};
let detail = match &source {
InvariantError::Tds(source) => InvariantErrorSummaryDetail::Tds(source.into()),
InvariantError::Triangulation(source) => {
InvariantErrorSummaryDetail::Triangulation(source.into())
}
InvariantError::Delaunay(source) => {
InvariantErrorSummaryDetail::Delaunay(source.into())
}
};
Self {
kind,
detail,
message: source.to_string(),
}
}
}
#[derive(Clone, Debug)]
pub struct InvariantViolation {
pub kind: InvariantKind,
pub error: InvariantError,
}
#[derive(Clone, Debug)]
pub struct TriangulationValidationReport {
pub violations: Vec<InvariantViolation>,
}
impl TriangulationValidationReport {
#[must_use]
pub const fn is_empty(&self) -> bool {
self.violations.is_empty()
}
}
new_key_type! {
pub struct VertexKey;
}
new_key_type! {
pub struct SimplexKey;
}
#[derive(Debug)]
pub struct Tds<T, U, V, const D: usize> {
vertices: StorageMap<VertexKey, Vertex<T, U, D>>,
simplices: StorageMap<SimplexKey, Simplex<T, U, V, D>>,
pub(crate) uuid_to_vertex_key: UuidToVertexKeyMap,
pub(crate) uuid_to_simplex_key: UuidToSimplexKeyMap,
pub construction_state: TriangulationConstructionState,
generation: Arc<AtomicU64>,
identity: Arc<Uuid>,
}
#[derive(Clone, Copy)]
enum SimplexInsertionTopologyCheck {
Checked,
Prechecked,
}
impl<T, U, V, const D: usize> Clone for Tds<T, U, V, D>
where
T: Clone,
U: Clone,
V: Clone,
{
fn clone(&self) -> Self {
Self {
vertices: self.vertices.clone(),
simplices: self.simplices.clone(),
uuid_to_vertex_key: self.uuid_to_vertex_key.clone(),
uuid_to_simplex_key: self.uuid_to_simplex_key.clone(),
construction_state: self.construction_state.clone(),
generation: Arc::new(AtomicU64::new(self.generation.load(Ordering::Relaxed))),
identity: Arc::new(Uuid::new_v4()),
}
}
}
impl<T, U, V, const D: usize> Tds<T, U, V, D>
where
T: Clone,
U: Clone,
V: Clone,
{
pub(crate) fn clone_for_rollback(&self) -> Self {
Self {
vertices: self.vertices.clone(),
simplices: self.simplices.clone(),
uuid_to_vertex_key: self.uuid_to_vertex_key.clone(),
uuid_to_simplex_key: self.uuid_to_simplex_key.clone(),
construction_state: self.construction_state.clone(),
generation: Arc::new(AtomicU64::new(self.generation.load(Ordering::Relaxed))),
identity: Arc::clone(&self.identity),
}
}
}
impl<T, U, V, const D: usize> Tds<T, U, V, D> {
#[inline]
fn allows_periodic_self_neighbor(simplex: &Simplex<T, U, V, D>) -> bool {
let Some(offsets) = simplex.periodic_vertex_offsets() else {
return false;
};
!offsets.is_empty() && offsets.len() == simplex.number_of_vertices()
}
fn periodic_facet_key_from_simplex_vertices(
simplex: &Simplex<T, U, V, D>,
vertices: &[VertexKey],
facet_index: usize,
) -> Result<u64, TdsError> {
if facet_index >= vertices.len() {
return Err(TdsError::IndexOutOfBounds {
index: facet_index,
bound: vertices.len(),
context: format!("facet index for simplex with {} vertices", vertices.len()),
});
}
let Some(periodic_offsets) = simplex.periodic_vertex_offsets() else {
let mut facet_vertices: SmallBuffer<VertexKey, MAX_PRACTICAL_DIMENSION_SIZE> =
SmallBuffer::new();
for (i, &vertex_key) in vertices.iter().enumerate() {
if i != facet_index {
facet_vertices.push(vertex_key);
}
}
return Ok(facet_key_from_vertices(&facet_vertices));
};
if periodic_offsets.len() != vertices.len() {
return Err(TdsError::DimensionMismatch {
expected: vertices.len(),
actual: periodic_offsets.len(),
context: "simplex periodic offset count vs vertex count".to_string(),
});
}
let mut lifted_vertices: SmallBuffer<(VertexKey, [i8; D]), MAX_PRACTICAL_DIMENSION_SIZE> =
SmallBuffer::new();
for (vertex_idx, &vertex_key) in vertices.iter().enumerate() {
lifted_vertices.push((vertex_key, periodic_offsets[vertex_idx]));
}
periodic_facet_key_from_lifted_vertices::<D>(&lifted_vertices, facet_index).map_err(
|error| TdsError::InconsistentDataStructure {
message: format!(
"Failed to derive periodic facet key for simplex {:?} facet {facet_index}: {error}",
simplex.uuid()
),
},
)
}
fn build_periodic_vertex_uuid_offsets(
&self,
simplex_key: SimplexKey,
vertices: &[VertexKey],
) -> Result<Vec<(Uuid, [i8; D])>, TdsError> {
let simplex = self
.simplices
.get(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: "building periodic vertex identity (UUID/offset)".to_string(),
})?;
let periodic_offsets = simplex.periodic_vertex_offsets();
if let Some(offsets) = periodic_offsets
&& offsets.len() != vertices.len()
{
return Err(TdsError::DimensionMismatch {
expected: vertices.len(),
actual: offsets.len(),
context: format!("simplex {simplex_key:?} periodic offset count vs vertex count"),
});
}
let mut vertex_uuid_offsets: Vec<(Uuid, [i8; D])> = Vec::with_capacity(vertices.len());
for (vertex_idx, &vertex_key) in vertices.iter().enumerate() {
let vertex = self
.vertices
.get(vertex_key)
.ok_or_else(|| TdsError::VertexNotFound {
vertex_key,
context: format!(
"referenced by simplex {simplex_key:?} at index {vertex_idx} while building periodic vertex identity (UUID/offset)",
),
})?;
let offset = periodic_offsets.map_or([0_i8; D], |offsets| offsets[vertex_idx]);
vertex_uuid_offsets.push((vertex.uuid(), offset));
}
vertex_uuid_offsets.sort_unstable();
Ok(vertex_uuid_offsets)
}
fn lifted_vertex_identities(
simplex_key: SimplexKey,
simplex: &Simplex<T, U, V, D>,
) -> Result<SmallBuffer<(VertexKey, [i8; D]), MAX_PRACTICAL_DIMENSION_SIZE>, TdsError> {
let vertices = simplex.vertices();
let periodic_offsets = simplex.periodic_vertex_offsets();
if let Some(offsets) = periodic_offsets
&& offsets.len() != vertices.len()
{
return Err(TdsError::DimensionMismatch {
expected: vertices.len(),
actual: offsets.len(),
context: format!(
"simplex {simplex_key:?} periodic offset count vs vertex count in neighbor topology validation"
),
});
}
let mut lifted_vertices: SmallBuffer<(VertexKey, [i8; D]), MAX_PRACTICAL_DIMENSION_SIZE> =
SmallBuffer::new();
for (vertex_idx, &vertex_key) in vertices.iter().enumerate() {
let offset = periodic_offsets.map_or([0_i8; D], |offsets| offsets[vertex_idx]);
lifted_vertices.push((vertex_key, offset));
}
Ok(lifted_vertices)
}
fn matching_lifted_facet_index(
simplex: &Simplex<T, U, V, D>,
neighbor: &Simplex<T, U, V, D>,
) -> Result<Option<usize>, TdsError> {
let simplex_vertices = simplex.vertices();
let neighbor_vertices = neighbor.vertices();
for simplex_facet_index in 0..simplex_vertices.len() {
let simplex_facet_key = Self::periodic_facet_key_from_simplex_vertices(
simplex,
simplex_vertices,
simplex_facet_index,
)?;
for neighbor_facet_index in 0..neighbor_vertices.len() {
let neighbor_facet_key = Self::periodic_facet_key_from_simplex_vertices(
neighbor,
neighbor_vertices,
neighbor_facet_index,
)?;
if simplex_facet_key == neighbor_facet_key {
return Ok(Some(simplex_facet_index));
}
}
}
Ok(None)
}
fn matching_lifted_mirror_facet_index(
simplex: &Simplex<T, U, V, D>,
facet_idx: usize,
neighbor: &Simplex<T, U, V, D>,
context: &str,
) -> Result<usize, TdsError> {
let simplex_facet_key =
Self::periodic_facet_key_from_simplex_vertices(simplex, simplex.vertices(), facet_idx)?;
let mut mirror_idx = None;
for neighbor_facet_idx in 0..neighbor.vertices().len() {
let neighbor_facet_key = Self::periodic_facet_key_from_simplex_vertices(
neighbor,
neighbor.vertices(),
neighbor_facet_idx,
)?;
if neighbor_facet_key == simplex_facet_key
&& mirror_idx.replace(neighbor_facet_idx).is_some()
{
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetAmbiguous {
simplex_uuid: simplex.uuid(),
neighbor_uuid: neighbor.uuid(),
},
});
}
}
mirror_idx.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetMissing {
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_uuid: neighbor.uuid(),
context: context.to_string(),
},
})
}
pub(crate) fn facet_key_for_simplex_facet(
&self,
simplex_key: SimplexKey,
facet_index: usize,
) -> Result<u64, TdsError> {
let vertices = self.simplex_vertices(simplex_key)?;
let simplex = self
.simplices
.get(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: format!("deriving facet key for index {facet_index}"),
})?;
Self::periodic_facet_key_from_simplex_vertices(simplex, &vertices, facet_index)
}
pub(crate) fn assign_neighbors(&mut self) -> Result<(), TdsError> {
type FacetInfo = (SimplexKey, usize);
let cap = self.simplices.len().saturating_mul(D.saturating_add(1));
let mut facet_map: FastHashMap<u64, SmallBuffer<FacetInfo, 2>> =
fast_hash_map_with_capacity(cap);
for (simplex_key, simplex) in &self.simplices {
let vertices = self.simplex_vertices(simplex_key).map_err(|err| {
TdsError::VertexKeyRetrievalFailed {
simplex_id: simplex.uuid(),
message: format!(
"Failed to retrieve vertex keys for simplex during neighbor assignment: {err}"
),
}
})?;
for i in 0..vertices.len() {
let facet_key =
Self::periodic_facet_key_from_simplex_vertices(simplex, &vertices, i)?;
let facet_entry = facet_map.entry(facet_key).or_default();
if facet_entry.len() >= 2 {
return Err(TdsError::InconsistentDataStructure {
message: format!(
"Facet with key {} already shared by {} simplices; cannot add simplex {} (would violate 2-manifold property)",
facet_key,
facet_entry.len(),
simplex.uuid()
),
});
}
facet_entry.push((simplex_key, i));
}
}
let mut simplex_neighbors: FastHashMap<
SimplexKey,
SmallBuffer<Option<SimplexKey>, MAX_PRACTICAL_DIMENSION_SIZE>,
> = fast_hash_map_with_capacity(self.simplices.len());
for (simplex_key, simplex) in &self.simplices {
let vertex_count = simplex.number_of_vertices();
if vertex_count > MAX_PRACTICAL_DIMENSION_SIZE {
return Err(TdsError::InconsistentDataStructure {
message: format!(
"simplex {} vertex count ({vertex_count}) exceeds storage limit MAX_PRACTICAL_DIMENSION_SIZE ({MAX_PRACTICAL_DIMENSION_SIZE}) (would overflow neighbors buffer)",
simplex.uuid(),
),
});
}
let mut neighbors = SmallBuffer::with_capacity(vertex_count);
neighbors.resize(vertex_count, None);
simplex_neighbors.insert(simplex_key, neighbors);
}
for (_facet_key, facet_infos) in facet_map {
if facet_infos.len() != 2 {
continue;
}
let (simplex_key1, vertex_index1) = facet_infos[0];
let (simplex_key2, vertex_index2) = facet_infos[1];
simplex_neighbors.get_mut(&simplex_key1).ok_or_else(|| {
TdsError::SimplexNotFound {
simplex_key: simplex_key1,
context: "assign_neighbors: simplex missing from local neighbors map"
.to_string(),
}
})?[vertex_index1] = Some(simplex_key2);
simplex_neighbors.get_mut(&simplex_key2).ok_or_else(|| {
TdsError::SimplexNotFound {
simplex_key: simplex_key2,
context: "assign_neighbors: simplex missing from local neighbors map"
.to_string(),
}
})?[vertex_index2] = Some(simplex_key1);
}
for (simplex_key, neighbors) in &simplex_neighbors {
if let Some(simplex) = self.simplices.get_mut(*simplex_key) {
let simplex_id = simplex.uuid();
simplex
.set_neighbors_from_keys(neighbors.iter().copied())
.map_err(|source| TdsError::InvalidSimplex { simplex_id, source })?;
}
}
self.bump_generation();
Ok(())
}
pub fn simplices(&self) -> impl Iterator<Item = (SimplexKey, &Simplex<T, U, V, D>)> {
self.simplices.iter()
}
pub fn simplices_values(&self) -> impl Iterator<Item = &Simplex<T, U, V, D>> {
self.simplices.values()
}
pub fn vertices(&self) -> impl Iterator<Item = (VertexKey, &Vertex<T, U, D>)> {
self.vertices.iter()
}
pub fn vertex_keys(&self) -> impl Iterator<Item = VertexKey> + '_ {
self.vertices.keys()
}
pub fn simplex_keys(&self) -> impl Iterator<Item = SimplexKey> + '_ {
self.simplices.keys()
}
#[must_use]
pub fn simplex(&self, key: SimplexKey) -> Option<&Simplex<T, U, V, D>> {
self.simplices.get(key)
}
#[must_use]
pub fn contains_simplex(&self, key: SimplexKey) -> bool {
self.simplices.contains_key(key)
}
#[must_use]
pub fn number_of_vertices(&self) -> usize {
self.vertices.len()
}
#[must_use]
pub fn dim(&self) -> i32 {
let nv = self.number_of_vertices();
let nv_i32 = i32::try_from(nv).unwrap_or(i32::MAX);
let d_i32 = i32::try_from(D).unwrap_or(i32::MAX);
nv_i32.saturating_sub(1).min(d_i32)
}
#[must_use]
pub fn number_of_simplices(&self) -> usize {
self.simplices.len()
}
#[must_use]
pub fn is_connected(&self) -> bool {
let total = self.simplices.len();
if total == 0 {
return true;
}
let Some(start) = self.simplex_keys().next() else {
return true;
};
let mut visited: SimplexKeySet = SimplexKeySet::default();
visited.reserve(total);
let mut stack: Vec<SimplexKey> = Vec::with_capacity(total.min(64));
stack.push(start);
while let Some(ck) = stack.pop() {
if !visited.insert(ck) {
continue;
}
let Some(simplex) = self.simplices.get(ck) else {
continue;
};
let Some(neighbors) = simplex.neighbor_keys() else {
continue;
};
for n_opt in neighbors {
let Some(nk) = n_opt else {
continue;
};
if self.simplices.contains_key(nk) && !visited.contains(&nk) {
stack.push(nk);
}
}
}
visited.len() == total
}
#[inline]
fn bump_generation(&self) {
self.generation.fetch_add(1, Ordering::Relaxed);
}
#[inline]
#[must_use]
pub fn generation(&self) -> u64 {
self.generation.load(Ordering::Relaxed)
}
#[inline]
pub(crate) const fn identity(&self) -> &Arc<Uuid> {
&self.identity
}
#[inline]
pub(crate) fn mark_topology_modified(&self) {
self.bump_generation();
}
}
impl<T, U, V, const D: usize> Tds<T, U, V, D> {
pub(crate) fn insert_vertex_with_mapping(
&mut self,
vertex: Vertex<T, U, D>,
) -> Result<VertexKey, TdsConstructionError> {
let vertex_uuid = vertex.uuid();
match self.uuid_to_vertex_key.entry(vertex_uuid) {
Entry::Occupied(_) => Err(TdsConstructionError::DuplicateUuid {
entity: EntityKind::Vertex,
uuid: vertex_uuid,
}),
Entry::Vacant(e) => {
let vertex_key = self.vertices.insert(vertex);
e.insert(vertex_key);
self.bump_generation();
Ok(vertex_key)
}
}
}
pub(crate) fn insert_simplex_with_mapping(
&mut self,
simplex: Simplex<T, U, V, D>,
) -> Result<SimplexKey, TdsConstructionError> {
self.insert_simplex_with_mapping_impl(simplex, SimplexInsertionTopologyCheck::Checked)
}
pub(crate) fn insert_simplex_with_mapping_trusted_vertices(
&mut self,
simplex: Simplex<T, U, V, D>,
) -> Result<SimplexKey, TdsConstructionError> {
self.insert_simplex_with_mapping_impl(simplex, SimplexInsertionTopologyCheck::Checked)
}
pub(crate) fn insert_simplex_with_mapping_prechecked_topology(
&mut self,
simplex: Simplex<T, U, V, D>,
) -> Result<SimplexKey, TdsConstructionError> {
self.insert_simplex_with_mapping_impl(simplex, SimplexInsertionTopologyCheck::Prechecked)
}
fn insert_simplex_with_mapping_impl(
&mut self,
simplex: Simplex<T, U, V, D>,
topology_check: SimplexInsertionTopologyCheck,
) -> Result<SimplexKey, TdsConstructionError> {
if simplex.number_of_vertices() != D + 1 {
return Err(TdsConstructionError::ValidationError(
TdsError::DimensionMismatch {
expected: D + 1,
actual: simplex.number_of_vertices(),
context: format!("{D}-dimensional simplex vertex count"),
},
));
}
self.validate_simplex_vertices_exist(&simplex)?;
let simplex_uuid = simplex.uuid();
if self.uuid_to_simplex_key.contains_key(&simplex_uuid) {
return Err(TdsConstructionError::DuplicateUuid {
entity: EntityKind::Simplex,
uuid: simplex_uuid,
});
}
match topology_check {
SimplexInsertionTopologyCheck::Checked => {
self.validate_simplex_topology_safe_for_insertion(&simplex)?;
}
SimplexInsertionTopologyCheck::Prechecked => {}
}
let simplex_key = self.simplices.insert(simplex);
self.uuid_to_simplex_key.insert(simplex_uuid, simplex_key);
self.bump_generation();
Ok(simplex_key)
}
fn validate_simplex_topology_safe_for_insertion(
&self,
simplex: &Simplex<T, U, V, D>,
) -> Result<(), TdsConstructionError> {
self.validate_no_duplicate_simplex_on_insert(simplex)?;
self.validate_facet_sharing_on_insert(simplex)?;
Ok(())
}
fn candidate_periodic_vertex_uuid_offsets(
&self,
simplex: &Simplex<T, U, V, D>,
) -> Result<Vec<(Uuid, [i8; D])>, TdsError> {
let vertices = simplex.vertices();
let periodic_offsets = simplex.periodic_vertex_offsets();
if let Some(offsets) = periodic_offsets
&& offsets.len() != vertices.len()
{
return Err(TdsError::DimensionMismatch {
expected: vertices.len(),
actual: offsets.len(),
context: format!(
"candidate simplex {} periodic offset count vs vertex count",
simplex.uuid()
),
});
}
let mut vertex_uuid_offsets = Vec::with_capacity(vertices.len());
for (vertex_idx, &vertex_key) in vertices.iter().enumerate() {
let vertex = self
.vertices
.get(vertex_key)
.ok_or_else(|| TdsError::VertexNotFound {
vertex_key,
context: format!(
"referenced by candidate simplex {} at index {vertex_idx} while building periodic vertex identity (UUID/offset)",
simplex.uuid()
),
})?;
let offset = periodic_offsets.map_or([0_i8; D], |offsets| offsets[vertex_idx]);
vertex_uuid_offsets.push((vertex.uuid(), offset));
}
vertex_uuid_offsets.sort_unstable();
Ok(vertex_uuid_offsets)
}
fn validate_no_duplicate_simplex_on_insert(
&self,
simplex: &Simplex<T, U, V, D>,
) -> Result<(), TdsError> {
let candidate_identity = self.candidate_periodic_vertex_uuid_offsets(simplex)?;
for (existing_simplex_key, _existing_simplex) in &self.simplices {
let vertices = self.simplex_vertices(existing_simplex_key)?;
let existing_identity =
self.build_periodic_vertex_uuid_offsets(existing_simplex_key, &vertices)?;
if existing_identity == candidate_identity {
return Err(TdsError::DuplicateSimplices {
message: format!(
"Refusing to insert duplicate simplex {} with same vertex UUIDs as existing simplex {existing_simplex_key:?}: {candidate_identity:?}",
simplex.uuid()
),
});
}
}
Ok(())
}
fn validate_facet_sharing_on_insert(
&self,
simplex: &Simplex<T, U, V, D>,
) -> Result<(), TdsError> {
let vertices = simplex.vertices();
for candidate_facet_idx in 0..vertices.len() {
let candidate_facet_key = Self::periodic_facet_key_from_simplex_vertices(
simplex,
vertices,
candidate_facet_idx,
)?;
let mut incident_count = 0_usize;
for (existing_simplex_key, existing_simplex) in &self.simplices {
let existing_vertices = self.simplex_vertices(existing_simplex_key)?;
for existing_facet_idx in 0..existing_vertices.len() {
let existing_facet_key = Self::periodic_facet_key_from_simplex_vertices(
existing_simplex,
&existing_vertices,
existing_facet_idx,
)?;
if existing_facet_key == candidate_facet_key {
incident_count += 1;
if incident_count >= 2 {
return Err(TdsError::FacetSharingViolation {
facet_key: candidate_facet_key,
existing_incident_count: incident_count,
attempted_incident_count: incident_count + 1,
max_incident_count: 2,
candidate_simplex_uuid: simplex.uuid(),
candidate_facet_index: candidate_facet_idx,
});
}
}
}
}
}
Ok(())
}
fn validate_simplex_vertices_exist(
&self,
simplex: &Simplex<T, U, V, D>,
) -> Result<(), TdsConstructionError> {
for &vkey in simplex.vertices() {
if !self.vertices.contains_key(vkey) {
return Err(TdsConstructionError::ValidationError(
TdsError::VertexNotFound {
vertex_key: vkey,
context: "referenced by simplex being inserted".to_string(),
},
));
}
}
Ok(())
}
#[cfg(test)]
pub(crate) fn insert_simplex_bypassing_topology_checks_for_test(
&mut self,
simplex: Simplex<T, U, V, D>,
) -> Result<SimplexKey, TdsConstructionError> {
self.insert_simplex_with_mapping_impl(simplex, SimplexInsertionTopologyCheck::Prechecked)
}
}
impl<T, U, V, const D: usize> Tds<T, U, V, D> {
#[inline]
pub fn simplex_vertices(&self, simplex_key: SimplexKey) -> Result<VertexKeyBuffer, TdsError> {
let simplex = self
.simplices
.get(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: "simplex_vertices lookup".to_string(),
})?;
let simplex_vertices = simplex.vertices();
let mut keys = VertexKeyBuffer::with_capacity(simplex_vertices.len());
for (idx, &vertex_key) in simplex_vertices.iter().enumerate() {
if !self.vertices.contains_key(vertex_key) {
return Err(TdsError::VertexNotFound {
vertex_key,
context: format!(
"referenced by simplex {} (key {simplex_key:?}) at position {idx}",
simplex.uuid()
),
});
}
keys.push(vertex_key);
}
Ok(keys)
}
#[inline]
#[must_use]
pub fn simplex_key_from_uuid(&self, simplex_uuid: &Uuid) -> Option<SimplexKey> {
self.uuid_to_simplex_key.get(simplex_uuid).copied()
}
#[inline]
#[must_use]
pub fn vertex_key_from_uuid(&self, vertex_uuid: &Uuid) -> Option<VertexKey> {
self.uuid_to_vertex_key.get(vertex_uuid).copied()
}
#[inline]
#[must_use]
pub fn simplex_uuid_from_key(&self, simplex_key: SimplexKey) -> Option<Uuid> {
self.simplices
.get(simplex_key)
.map(super::simplex::Simplex::uuid)
}
#[inline]
#[must_use]
pub fn vertex_uuid_from_key(&self, vertex_key: VertexKey) -> Option<Uuid> {
self.vertices
.get(vertex_key)
.map(super::vertex::Vertex::uuid)
}
#[inline]
#[must_use]
pub(crate) fn simplex_mut(
&mut self,
simplex_key: SimplexKey,
) -> Option<&mut Simplex<T, U, V, D>> {
self.simplices.get_mut(simplex_key)
}
#[inline]
#[must_use]
pub fn vertex(&self, vertex_key: VertexKey) -> Option<&Vertex<T, U, D>> {
self.vertices.get(vertex_key)
}
#[inline]
#[must_use]
pub(crate) fn vertex_mut(&mut self, vertex_key: VertexKey) -> Option<&mut Vertex<T, U, D>> {
self.vertices.get_mut(vertex_key)
}
#[inline]
pub fn set_vertex_data(&mut self, key: VertexKey, data: Option<U>) -> Option<Option<U>> {
let vertex = self.vertices.get_mut(key)?;
let previous = vertex.data.take();
vertex.data = data;
Some(previous)
}
#[inline]
pub fn set_simplex_data(&mut self, key: SimplexKey, data: Option<V>) -> Option<Option<V>> {
let simplex = self.simplices.get_mut(key)?;
let previous = simplex.data.take();
simplex.data = data;
Some(previous)
}
#[inline]
#[must_use]
pub fn contains_simplex_key(&self, simplex_key: SimplexKey) -> bool {
self.simplices.contains_key(simplex_key)
}
#[inline]
#[must_use]
pub fn contains_vertex_key(&self, vertex_key: VertexKey) -> bool {
self.vertices.contains_key(vertex_key)
}
}
impl<T, U, V, const D: usize> Tds<T, U, V, D> {
pub fn remove_simplices_by_keys(&mut self, simplex_keys: &[SimplexKey]) -> usize {
if simplex_keys.is_empty() {
return 0;
}
let simplices_to_remove: SimplexKeySet = simplex_keys.iter().copied().collect();
let (affected_vertices, candidate_incident) = self
.collect_removal_frontier_and_clear_neighbor_back_references(
simplex_keys,
&simplices_to_remove,
);
let removed_count = self.remove_simplices_and_update_uuid_mappings(simplex_keys);
if removed_count == 0 {
return 0;
}
self.repair_incident_simplices_after_simplex_removal(
&affected_vertices,
&simplices_to_remove,
&candidate_incident,
);
self.bump_generation();
removed_count
}
#[cfg(test)]
pub(crate) fn repair_degenerate_simplices(&mut self) -> usize {
if self.simplices.is_empty() {
return 0;
}
let mut to_remove: Vec<SimplexKey> = Vec::new();
for (simplex_key, simplex) in self.simplices() {
if simplex.is_valid().is_err() {
to_remove.push(simplex_key);
continue;
}
if simplex
.vertices()
.iter()
.any(|&vkey| !self.vertices.contains_key(vkey))
{
to_remove.push(simplex_key);
continue;
}
if simplex.neighbor_keys().is_some_and(|neighbors| {
neighbors
.flatten()
.any(|neighbor_key| !self.simplices.contains_key(neighbor_key))
}) {
to_remove.push(simplex_key);
}
}
if to_remove.is_empty() {
return 0;
}
self.remove_simplices_by_keys(&to_remove)
}
fn collect_removal_frontier_and_clear_neighbor_back_references(
&mut self,
simplex_keys: &[SimplexKey],
simplices_to_remove: &SimplexKeySet,
) -> (VertexKeySet, FastHashMap<VertexKey, SimplexKey>) {
let mut affected_vertices: VertexKeySet = VertexKeySet::default();
let mut candidate_incident: FastHashMap<VertexKey, SimplexKey> =
fast_hash_map_with_capacity(simplex_keys.len().saturating_mul(D.saturating_add(1)));
for &simplex_key in simplex_keys {
let Some((vertices, neighbors)) = self.simplices.get(simplex_key).map(|simplex| {
let mut vertices: SmallBuffer<VertexKey, MAX_PRACTICAL_DIMENSION_SIZE> =
SmallBuffer::with_capacity(simplex.number_of_vertices());
vertices.extend(simplex.vertices().iter().copied());
let mut neighbors: SmallBuffer<Option<SimplexKey>, MAX_PRACTICAL_DIMENSION_SIZE> =
SmallBuffer::with_capacity(vertices.len());
neighbors.resize(vertices.len(), None);
if let Some(simplex_neighbors) = simplex.neighbor_keys() {
for (slot, neighbor_opt) in neighbors.iter_mut().zip(simplex_neighbors) {
*slot = neighbor_opt;
}
}
(vertices, neighbors)
}) else {
continue;
};
for &vk in &vertices {
affected_vertices.insert(vk);
}
for (facet_idx, neighbor_key_opt) in neighbors.iter().enumerate() {
let Some(neighbor_key) = neighbor_key_opt else {
continue;
};
if simplices_to_remove.contains(neighbor_key) {
continue; }
for (vertex_index, &vkey) in vertices.iter().enumerate() {
if vertex_index == facet_idx {
continue;
}
candidate_incident.entry(vkey).or_insert(*neighbor_key);
}
let Some(neighbor_simplex) = self.simplices.get_mut(*neighbor_key) else {
continue;
};
let Some(neighbors_buf) = neighbor_simplex.neighbor_slots_mut() else {
continue;
};
for slot in neighbors_buf.iter_mut() {
if slot.simplex_key() == Some(simplex_key) {
*slot = NeighborSlot::Boundary;
}
}
}
}
(affected_vertices, candidate_incident)
}
fn remove_simplices_and_update_uuid_mappings(&mut self, simplex_keys: &[SimplexKey]) -> usize {
let mut removed_count = 0;
for &simplex_key in simplex_keys {
if let Some(removed_simplex) = self.simplices.remove(simplex_key) {
self.uuid_to_simplex_key.remove(&removed_simplex.uuid());
removed_count += 1;
}
}
removed_count
}
fn repair_incident_simplices_after_simplex_removal(
&mut self,
affected_vertices: &VertexKeySet,
simplices_to_remove: &SimplexKeySet,
candidate_incident: &FastHashMap<VertexKey, SimplexKey>,
) {
let vertices_to_repair: Vec<VertexKey> = affected_vertices
.iter()
.copied()
.filter(|&vk| {
let Some(v) = self.vertices.get(vk) else {
return false;
};
match v.incident_simplex() {
None => true,
Some(simplex_key) => {
simplices_to_remove.contains(&simplex_key)
|| !self.simplices.contains_key(simplex_key)
}
}
})
.collect();
let mut incident_updates: Vec<(VertexKey, Option<SimplexKey>)> =
Vec::with_capacity(vertices_to_repair.len());
for vk in vertices_to_repair {
let mut new_incident = candidate_incident.get(&vk).copied().filter(|&ck| {
self.simplices
.get(ck)
.is_some_and(|simplex| simplex.contains_vertex(vk))
});
if new_incident.is_none() {
new_incident = self.simplices.iter().find_map(|(simplex_key, simplex)| {
simplex.contains_vertex(vk).then_some(simplex_key)
});
}
incident_updates.push((vk, new_incident));
}
for (vk, new_incident) in incident_updates {
if let Some(vertex) = self.vertices.get_mut(vk) {
vertex.set_incident_simplex(new_incident);
}
}
}
pub(crate) fn find_simplices_containing_vertex(
&self,
vertex_key: VertexKey,
) -> SimplexRemovalBuffer {
let fallback_scan = || {
self.simplices()
.filter_map(|(simplex_key, simplex)| {
simplex.contains_vertex(vertex_key).then_some(simplex_key)
})
.collect()
};
let Some(vertex) = self.vertices.get(vertex_key) else {
return fallback_scan();
};
let Some(start_simplex_key) = vertex.incident_simplex() else {
return fallback_scan();
};
let Some(start_simplex) = self.simplices.get(start_simplex_key) else {
return fallback_scan();
};
let Some(start_neighbor_slots) = start_simplex.neighbor_slots() else {
return fallback_scan();
};
if !start_simplex.contains_vertex(vertex_key)
|| start_neighbor_slots.iter().any(|slot| slot.is_unassigned())
{
return fallback_scan();
}
let mut visited: SimplexKeySet = SimplexKeySet::default();
let mut stack: SimplexRemovalBuffer = SimplexRemovalBuffer::new();
let mut result: SimplexRemovalBuffer = SimplexRemovalBuffer::new();
visited.insert(start_simplex_key);
stack.push(start_simplex_key);
while let Some(simplex_key) = stack.pop() {
result.push(simplex_key);
let Some(simplex) = self.simplices.get(simplex_key) else {
return fallback_scan();
};
let Some(neighbors) = simplex.neighbor_slots() else {
return fallback_scan();
};
if neighbors.iter().any(|slot| slot.is_unassigned()) {
return fallback_scan();
}
for (facet_idx, neighbor_slot) in neighbors.iter().copied().enumerate() {
if simplex
.vertices()
.get(facet_idx)
.is_some_and(|&vkey| vkey == vertex_key)
{
continue;
}
let NeighborSlot::Neighbor(neighbor_key) = neighbor_slot else {
continue;
};
if visited.contains(&neighbor_key) {
continue;
}
let Some(neighbor_simplex) = self.simplices.get(neighbor_key) else {
return fallback_scan();
};
if !neighbor_simplex.contains_vertex(vertex_key) {
return fallback_scan();
}
visited.insert(neighbor_key);
stack.push(neighbor_key);
}
}
result
}
#[expect(
clippy::unnecessary_wraps,
reason = "Keep Result for future mutation validation without changing the API"
)]
pub(crate) fn remove_vertex(
&mut self,
vertex_key: VertexKey,
) -> Result<usize, TdsMutationError> {
let Some(vertex) = self.vertex(vertex_key) else {
return Ok(0); };
let uuid = vertex.uuid();
let simplices_to_remove = self.find_simplices_containing_vertex(vertex_key);
let simplices_removed = self.remove_simplices_by_keys(&simplices_to_remove);
self.vertices.remove(vertex_key);
self.uuid_to_vertex_key.remove(&uuid);
self.bump_generation();
Ok(simplices_removed)
}
pub(crate) fn remove_isolated_vertex(&mut self, vertex_key: VertexKey) {
let Some(vertex) = self.vertex(vertex_key) else {
return;
};
if vertex.incident_simplex().is_some() {
return;
}
let uuid = vertex.uuid();
self.vertices.remove(vertex_key);
self.uuid_to_vertex_key.remove(&uuid);
self.bump_generation();
}
#[must_use]
pub fn find_neighbors_by_key(
&self,
simplex_key: SimplexKey,
) -> NeighborBuffer<Option<SimplexKey>> {
let mut neighbors = NeighborBuffer::new();
neighbors.resize(D + 1, None);
let Some(simplex) = self.simplex(simplex_key) else {
return neighbors;
};
if let Some(neighbors_from_simplex) = simplex.neighbor_keys() {
for (slot, neighbor_key_opt) in neighbors.iter_mut().zip(neighbors_from_simplex) {
*slot = neighbor_key_opt;
}
}
neighbors
}
fn validate_neighbor_topology(
&self,
simplex_key: SimplexKey,
neighbors: &[Option<SimplexKey>],
) -> Result<(), TdsError> {
if neighbors.len() != D + 1 {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::LengthMismatch {
actual: neighbors.len(),
expected: D + 1,
context: "neighbor topology validation".to_string(),
},
});
}
let simplex = self
.simplices
.get(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: "validate_neighbor_topology".to_string(),
})?;
let simplex_lifted_vertices = Self::lifted_vertex_identities(simplex_key, simplex)?;
for (i, neighbor_key_opt) in neighbors.iter().enumerate() {
if let Some(neighbor_key) = neighbor_key_opt {
if *neighbor_key == simplex_key {
if Self::allows_periodic_self_neighbor(simplex) {
continue;
}
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::NonPeriodicSelfNeighbor {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: i,
},
});
}
let neighbor = self.simplices.get(*neighbor_key).ok_or_else(|| {
TdsError::InvalidNeighbors {
reason: NeighborValidationError::MissingNeighborSimplex {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: i,
neighbor_key: *neighbor_key,
context: "neighbor topology validation".to_string(),
},
}
})?;
let uses_periodic_offsets = simplex.periodic_vertex_offsets().is_some()
|| neighbor.periodic_vertex_offsets().is_some();
let (shared_count, missing_vertex_idx) = if uses_periodic_offsets {
let matching_facet_index =
Self::matching_lifted_facet_index(simplex, neighbor)?;
(matching_facet_index.map_or(0, |_| D), matching_facet_index)
} else {
let neighbor_lifted_vertices =
Self::lifted_vertex_identities(*neighbor_key, neighbor)?;
let mut shared_count = 0;
let mut missing_vertex_idx = None;
for (idx, simplex_vertex_identity) in simplex_lifted_vertices.iter().enumerate()
{
if neighbor_lifted_vertices
.iter()
.any(|neighbor_vertex_identity| {
neighbor_vertex_identity == simplex_vertex_identity
})
{
shared_count += 1;
} else if missing_vertex_idx.is_none() {
missing_vertex_idx = Some(idx);
}
}
(shared_count, missing_vertex_idx)
};
if shared_count != D {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::SharedVertexCountMismatch {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: i,
shared_count,
expected: D,
},
});
}
if missing_vertex_idx != Some(i) {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::OppositeVertexMismatch {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: i,
observed_opposite: missing_vertex_idx,
expected_opposite: i,
},
});
}
}
}
Ok(())
}
fn validate_neighbor_update_matches_facet_incidence(
&self,
simplex_key: SimplexKey,
neighbors: &[Option<SimplexKey>],
) -> Result<(), TdsError> {
let simplex = self
.simplices
.get(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: "validate_neighbor_update_matches_facet_incidence".to_string(),
})?;
let facet_to_simplices = self.build_facet_to_simplices_map()?;
for (facet_idx, proposed_neighbor) in neighbors.iter().copied().enumerate() {
let facet_key = self.facet_key_for_simplex_facet(simplex_key, facet_idx)?;
let Some(simplex_facet_pairs) = facet_to_simplices.get(&facet_key) else {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::FacetIncidenceMissing {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
facet_key,
},
});
};
let expected_neighbor = match simplex_facet_pairs.as_slice() {
[_] => None,
[a, b] => {
if a.simplex_key() == simplex_key && a.facet_index() as usize == facet_idx {
Some(b.simplex_key())
} else if b.simplex_key() == simplex_key
&& b.facet_index() as usize == facet_idx
{
Some(a.simplex_key())
} else {
return Err(TdsError::InvalidNeighbors {
reason:
NeighborValidationError::FacetIncidenceDoesNotReferenceSimplex {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
facet_key,
},
});
}
}
_ => {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::FacetIncidenceMultiplicity {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
facet_key,
simplex_count: simplex_facet_pairs.len(),
},
});
}
};
if proposed_neighbor == Some(simplex_key)
&& expected_neighbor.is_none()
&& Self::allows_periodic_self_neighbor(simplex)
{
continue;
}
if proposed_neighbor != expected_neighbor {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::NeighborIncidenceMismatch {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
proposed_neighbor,
expected_neighbor,
},
});
}
}
Ok(())
}
fn set_simplex_neighbors_normalized(
simplex: &mut Simplex<T, U, V, D>,
neighbors: &[Option<SimplexKey>],
) -> Result<(), TdsError> {
let simplex_id = simplex.uuid();
simplex
.set_neighbors_from_keys(neighbors.iter().copied())
.map_err(|source| TdsError::InvalidSimplex { simplex_id, source })
}
fn ensure_neighbor_buffer(
simplex: &mut Simplex<T, U, V, D>,
) -> Result<&mut SmallBuffer<NeighborSlot, MAX_PRACTICAL_DIMENSION_SIZE>, TdsError> {
if simplex.neighbor_slots().is_none() {
let simplex_id = simplex.uuid();
simplex
.set_neighbors_from_keys((0..=D).map(|_| None))
.map_err(|source| TdsError::InvalidSimplex { simplex_id, source })?;
}
let neighbors = simplex.ensure_neighbors_buffer_mut();
if neighbors.len() != D + 1 {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::LengthMismatch {
actual: neighbors.len(),
expected: D + 1,
context: "reciprocal neighbor update".to_string(),
},
});
}
Ok(neighbors)
}
fn set_neighbor_slot(
simplex: &mut Simplex<T, U, V, D>,
facet_idx: usize,
neighbor: Option<SimplexKey>,
) -> Result<(), TdsError> {
let neighbors = Self::ensure_neighbor_buffer(simplex)?;
let Some(slot) = neighbors.get_mut(facet_idx) else {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::NeighborSlotOutOfBounds {
facet_index: facet_idx,
slot_count: neighbors.len(),
},
});
};
*slot = NeighborSlot::from_neighbor_key(neighbor);
Ok(())
}
fn reciprocal_neighbor_updates_for_neighbor_update(
&self,
simplex_key: SimplexKey,
neighbors: &[Option<SimplexKey>],
) -> Result<Vec<(SimplexKey, usize, Option<SimplexKey>)>, TdsError> {
let simplex = self
.simplices
.get(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: "set_neighbors_by_key".to_string(),
})?;
let old_neighbors: Vec<Option<SimplexKey>> = simplex
.neighbor_keys()
.map_or_else(|| vec![None; D + 1], Iterator::collect);
let mut reciprocal_updates = Vec::new();
self.collect_stale_reciprocal_neighbor_updates(
simplex_key,
simplex,
&old_neighbors,
neighbors,
&mut reciprocal_updates,
)?;
self.collect_new_reciprocal_neighbor_updates(
simplex_key,
simplex,
neighbors,
&mut reciprocal_updates,
)?;
Ok(reciprocal_updates)
}
fn collect_stale_reciprocal_neighbor_updates(
&self,
simplex_key: SimplexKey,
simplex: &Simplex<T, U, V, D>,
old_neighbors: &[Option<SimplexKey>],
new_neighbors: &[Option<SimplexKey>],
reciprocal_updates: &mut Vec<(SimplexKey, usize, Option<SimplexKey>)>,
) -> Result<(), TdsError> {
for (facet_idx, old_neighbor_key) in old_neighbors.iter().copied().enumerate() {
let Some(old_neighbor_key) = old_neighbor_key else {
continue;
};
if old_neighbor_key == simplex_key
|| new_neighbors
.iter()
.copied()
.any(|neighbor_key| neighbor_key == Some(old_neighbor_key))
{
continue;
}
let old_neighbor_simplex =
self.simplices
.get(old_neighbor_key)
.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::MissingNeighborSimplex {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_key: old_neighbor_key,
context: "clearing stale reciprocal neighbor".to_string(),
},
})?;
let mirror_idx = simplex
.mirror_facet_index(facet_idx, old_neighbor_simplex)
.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetMissing {
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_uuid: old_neighbor_simplex.uuid(),
context: "clearing old back-reference".to_string(),
},
})?;
let back_ref = old_neighbor_simplex.neighbor_key(mirror_idx).flatten();
if back_ref == Some(simplex_key) {
reciprocal_updates.push((old_neighbor_key, mirror_idx, None));
}
}
Ok(())
}
fn collect_new_reciprocal_neighbor_updates(
&self,
simplex_key: SimplexKey,
simplex: &Simplex<T, U, V, D>,
neighbors: &[Option<SimplexKey>],
reciprocal_updates: &mut Vec<(SimplexKey, usize, Option<SimplexKey>)>,
) -> Result<(), TdsError> {
for (facet_idx, neighbor_key) in neighbors.iter().copied().enumerate() {
let Some(neighbor_key) = neighbor_key else {
continue;
};
if neighbor_key == simplex_key {
continue;
}
let neighbor_simplex =
self.simplices
.get(neighbor_key)
.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::MissingNeighborSimplex {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_key,
context: "setting reciprocal neighbor".to_string(),
},
})?;
let mirror_idx = simplex
.mirror_facet_index(facet_idx, neighbor_simplex)
.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetMissing {
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_uuid: neighbor_simplex.uuid(),
context: "setting back-reference".to_string(),
},
})?;
let existing_back_ref = neighbor_simplex.neighbor_key(mirror_idx).flatten();
if let Some(existing_back_ref) = existing_back_ref
&& existing_back_ref != simplex_key
{
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::ExistingBackReferenceConflict {
neighbor_uuid: neighbor_simplex.uuid(),
mirror_index: mirror_idx,
existing_back_ref,
requested_back_ref: simplex_key,
},
});
}
reciprocal_updates.push((neighbor_key, mirror_idx, Some(simplex_key)));
}
Ok(())
}
pub fn set_neighbors_by_key(
&mut self,
simplex_key: SimplexKey,
neighbors: &[Option<SimplexKey>],
) -> Result<(), TdsMutationError> {
self.validate_neighbor_topology(simplex_key, neighbors)?;
self.validate_neighbor_update_matches_facet_incidence(simplex_key, neighbors)?;
let reciprocal_updates =
self.reciprocal_neighbor_updates_for_neighbor_update(simplex_key, neighbors)?;
let simplex_uuid = {
let simplex =
self.simplex_mut(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: "set_neighbors_by_key".to_string(),
})?;
let simplex_uuid = simplex.uuid();
Self::set_simplex_neighbors_normalized(simplex, neighbors)?;
simplex_uuid
};
for (neighbor_key, mirror_idx, back_reference) in reciprocal_updates {
let neighbor_simplex =
self.simplices
.get_mut(neighbor_key)
.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::MissingNeighborSimplex {
simplex_key,
simplex_uuid,
facet_index: mirror_idx,
neighbor_key,
context: "applying reciprocal neighbor update".to_string(),
},
})?;
Self::set_neighbor_slot(neighbor_simplex, mirror_idx, back_reference)?;
}
self.bump_generation();
Ok(())
}
#[must_use]
pub fn find_simplices_containing_vertex_by_key(&self, vertex_key: VertexKey) -> SimplexKeySet {
if self.vertex(vertex_key).is_none() {
return SimplexKeySet::default();
}
let simplices = self.find_simplices_containing_vertex(vertex_key);
simplices.iter().copied().collect()
}
pub fn assign_incident_simplices(&mut self) -> Result<(), TdsMutationError> {
if self.simplices.is_empty() {
for vertex in self.vertices.values_mut() {
vertex.set_incident_simplex(None);
}
self.bump_generation();
return Ok(());
}
for vertex in self.vertices.values_mut() {
vertex.set_incident_simplex(None);
}
for (simplex_key, simplex) in &self.simplices {
for &vertex_key in simplex.vertices() {
let Some(vertex) = self.vertices.get_mut(vertex_key) else {
self.bump_generation();
return Err(TdsError::VertexNotFound {
vertex_key,
context: "incident simplex assignment".to_string(),
}
.into());
};
if vertex.incident_simplex().is_none() {
vertex.set_incident_simplex(Some(simplex_key));
}
}
}
self.bump_generation();
Ok(())
}
#[must_use]
pub fn empty() -> Self {
Self {
vertices: StorageMap::with_key(),
simplices: StorageMap::with_key(),
uuid_to_vertex_key: UuidToVertexKeyMap::default(),
uuid_to_simplex_key: UuidToSimplexKeyMap::default(),
construction_state: TriangulationConstructionState::Incomplete(0),
generation: Arc::new(AtomicU64::new(0)),
identity: Arc::new(Uuid::new_v4()),
}
}
#[inline]
pub fn clear_all_neighbors(&mut self) {
for simplex in self.simplices.values_mut() {
simplex.clear_neighbors();
}
self.bump_generation();
}
#[expect(
clippy::too_many_lines,
reason = "orientation normalization is unchanged; simplex nomenclature makes existing names longer"
)]
pub(crate) fn normalize_coherent_orientation(&mut self) -> Result<(), TdsError> {
let mut flip_assignment: FastHashMap<SimplexKey, bool> =
fast_hash_map_with_capacity(self.simplices.len());
for root_simplex_key in self.simplices.keys() {
if flip_assignment.contains_key(&root_simplex_key) {
continue;
}
flip_assignment.insert(root_simplex_key, false);
let mut queue = VecDeque::new();
queue.push_back(root_simplex_key);
while let Some(simplex_key) = queue.pop_front() {
let this_flip_state = *flip_assignment.get(&simplex_key).ok_or_else(|| {
TdsError::InconsistentDataStructure {
message: format!(
"Missing flip assignment for simplex {simplex_key:?} during orientation normalization",
),
}
})?;
let simplex =
self.simplices
.get(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: "orientation normalization traversal".to_string(),
})?;
let Some(neighbors) = simplex.neighbor_keys() else {
continue;
};
for (facet_idx, neighbor_key_opt) in neighbors.enumerate() {
let Some(neighbor_key) = neighbor_key_opt else {
continue;
};
if neighbor_key == simplex_key && Self::allows_periodic_self_neighbor(simplex) {
continue;
}
let neighbor_simplex =
self.simplices
.get(neighbor_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key: neighbor_key,
context: format!(
"neighbor of simplex {simplex_key:?} during orientation normalization"
),
})?;
if simplex.periodic_vertex_offsets().is_some()
|| neighbor_simplex.periodic_vertex_offsets().is_some()
{
continue;
}
let mirror_idx = simplex
.mirror_facet_index(facet_idx, neighbor_simplex)
.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetMissing {
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_uuid: neighbor_simplex.uuid(),
context: "orientation normalization".to_string(),
},
})?;
let (currently_coherent, _, _) = Self::facet_permutation_parity(
simplex,
facet_idx,
neighbor_simplex,
mirror_idx,
)?;
let requires_relative_flip = !currently_coherent;
let required_neighbor_flip_state = this_flip_state ^ requires_relative_flip;
if let Some(existing_neighbor_flip_state) = flip_assignment.get(&neighbor_key) {
if *existing_neighbor_flip_state != required_neighbor_flip_state {
return Err(TdsError::InconsistentDataStructure {
message: format!(
"Contradictory orientation constraints while normalizing simplices {:?} and {:?}",
simplex.uuid(),
neighbor_simplex.uuid(),
),
});
}
} else {
flip_assignment.insert(neighbor_key, required_neighbor_flip_state);
queue.push_back(neighbor_key);
}
}
}
}
let mut flipped_any = false;
for (simplex_key, should_flip) in flip_assignment {
if !should_flip {
continue;
}
let simplex =
self.simplices
.get_mut(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: "applying orientation normalization".to_string(),
})?;
if simplex.number_of_vertices() >= 2 {
simplex.swap_vertex_slots(0, 1);
flipped_any = true;
}
}
if flipped_any {
self.bump_generation();
}
Ok(())
}
pub(crate) fn validate_coherent_orientation_for_simplices(
&self,
simplices: &[SimplexKey],
) -> Result<(), TdsError> {
for &simplex_key in simplices {
let simplex =
self.simplices
.get(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: "local orientation validation scope".to_string(),
})?;
let Some(neighbors) = simplex.neighbor_keys() else {
continue;
};
for (facet_idx, neighbor_key_opt) in neighbors.enumerate() {
let Some(neighbor_key) = neighbor_key_opt else {
continue;
};
if neighbor_key == simplex_key && Self::allows_periodic_self_neighbor(simplex) {
continue;
}
let neighbor_simplex =
self.simplices
.get(neighbor_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key: neighbor_key,
context: format!(
"neighbor of simplex {simplex_key:?} during local orientation validation",
),
})?;
let (mirror_idx, uses_periodic_offsets) = Self::orientation_mirror_facet_index(
simplex,
facet_idx,
neighbor_simplex,
"local orientation validation",
)?;
let observed_back_reference = neighbor_simplex.neighbor_key(mirror_idx).flatten();
if observed_back_reference != Some(simplex_key) {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::BackReferenceMismatch {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_key,
neighbor_uuid: neighbor_simplex.uuid(),
mirror_index: mirror_idx,
observed: observed_back_reference,
context: "local orientation validation".to_string(),
},
});
}
if uses_periodic_offsets {
continue;
}
let simplex1_facet_vertices =
Self::facet_vertices_in_simplex_order(simplex, facet_idx)?;
let simplex2_facet_vertices =
Self::facet_vertices_in_simplex_order(neighbor_simplex, mirror_idx)?;
let (coherent, observed_odd_permutation, expected_odd_permutation) =
Self::facet_permutation_parity(
simplex,
facet_idx,
neighbor_simplex,
mirror_idx,
)?;
if !coherent {
return Err(TdsError::OrientationViolation {
simplex1_key: simplex_key,
simplex1_uuid: simplex.uuid(),
simplex2_key: neighbor_key,
simplex2_uuid: neighbor_simplex.uuid(),
simplex1_facet_index: facet_idx,
simplex2_facet_index: mirror_idx,
facet_vertices: simplex1_facet_vertices.into_iter().collect(),
simplex2_facet_vertices: simplex2_facet_vertices.into_iter().collect(),
observed_odd_permutation,
expected_odd_permutation,
});
}
}
}
Ok(())
}
}
impl<T, U, V, const D: usize> Tds<T, U, V, D> {
pub fn build_facet_to_simplices_map(&self) -> Result<FacetToSimplicesMap, TdsError> {
debug_assert!(
D <= 255,
"Dimension D must be <= 255 to fit facet indices in u8 (indices 0..=D)"
);
let cap = self.simplices.len().saturating_mul(D.saturating_add(1));
let mut facet_to_simplices: FacetToSimplicesMap = fast_hash_map_with_capacity(cap);
for (simplex_id, simplex) in &self.simplices {
let vertices = self.simplex_vertices(simplex_id)?;
for i in 0..vertices.len() {
let facet_key =
Self::periodic_facet_key_from_simplex_vertices(simplex, &vertices, i)?;
let Ok(facet_index_u8) = usize_to_u8(i, vertices.len()) else {
return Err(TdsError::IndexOutOfBounds {
index: i,
bound: u8::MAX as usize + 1,
context: format!("facet index exceeds u8 range for {D}D"),
});
};
facet_to_simplices
.entry(facet_key)
.or_default()
.push(FacetHandle::new(simplex_id, facet_index_u8));
}
}
Ok(facet_to_simplices)
}
}
impl<T, U, V, const D: usize> Tds<T, U, V, D> {
pub fn remove_duplicate_simplices(&mut self) -> Result<usize, TdsMutationError>
where
T: Clone,
U: Clone,
V: Clone,
{
let mut unique_simplices = FastHashMap::default();
let mut simplices_to_remove = SimplexRemovalBuffer::new();
for simplex_key in self.simplices.keys() {
let vertices = self.simplex_vertices(simplex_key)?;
let vertex_uuid_offsets =
self.build_periodic_vertex_uuid_offsets(simplex_key, &vertices)?;
match unique_simplices.entry(vertex_uuid_offsets) {
Entry::Occupied(_) => {
simplices_to_remove.push(simplex_key);
}
Entry::Vacant(e) => {
e.insert(simplex_key);
}
}
}
let duplicate_count = simplices_to_remove.len();
if duplicate_count == 0 {
return Ok(0);
}
let original_generation = self.generation();
let mut trial = self.clone_for_rollback();
trial.generation = Arc::new(AtomicU64::new(original_generation));
let removed = trial.remove_simplices_by_keys(&simplices_to_remove);
let rebuild_result = (|| -> Result<(), TdsMutationError> {
trial.assign_neighbors().map_err(TdsMutationError::from)?;
trial.assign_incident_simplices()?;
trial.is_valid().map_err(TdsMutationError::from)?;
Ok(())
})();
if let Err(error) = rebuild_result {
self.generation
.store(original_generation, Ordering::Relaxed);
return Err(error);
}
*self = trial;
Ok(removed)
}
pub(crate) fn validate_vertex_mappings(&self) -> Result<(), TdsError> {
if self.uuid_to_vertex_key.len() != self.vertices.len() {
return Err(TdsError::MappingInconsistency {
entity: EntityKind::Vertex,
message: format!(
"Number of mapping entries ({}) doesn't match number of vertices ({})",
self.uuid_to_vertex_key.len(),
self.vertices.len()
),
});
}
for (vertex_key, vertex) in &self.vertices {
let vertex_uuid = vertex.uuid();
if self.vertex_uuid_from_key(vertex_key) != Some(vertex_uuid) {
return Err(TdsError::MappingInconsistency {
entity: EntityKind::Vertex,
message: format!(
"Inconsistent or missing key-to-UUID mapping for key {vertex_key:?}"
),
});
}
if self.uuid_to_vertex_key.get(&vertex_uuid) != Some(&vertex_key) {
return Err(TdsError::MappingInconsistency {
entity: EntityKind::Vertex,
message: format!(
"Inconsistent or missing UUID-to-key mapping for UUID {vertex_uuid:?}"
),
});
}
}
Ok(())
}
pub(crate) fn validate_simplex_mappings(&self) -> Result<(), TdsError> {
if self.uuid_to_simplex_key.len() != self.simplices.len() {
return Err(TdsError::MappingInconsistency {
entity: EntityKind::Simplex,
message: format!(
"Number of mapping entries ({}) doesn't match number of simplices ({})",
self.uuid_to_simplex_key.len(),
self.simplices.len()
),
});
}
for (simplex_key, simplex) in &self.simplices {
let simplex_uuid = simplex.uuid();
if self.simplex_uuid_from_key(simplex_key) != Some(simplex_uuid) {
return Err(TdsError::MappingInconsistency {
entity: EntityKind::Simplex,
message: format!(
"Inconsistent or missing key-to-UUID mapping for key {simplex_key:?}"
),
});
}
if self.uuid_to_simplex_key.get(&simplex_uuid) != Some(&simplex_key) {
return Err(TdsError::MappingInconsistency {
entity: EntityKind::Simplex,
message: format!(
"Inconsistent or missing UUID-to-key mapping for UUID {simplex_uuid:?}"
),
});
}
}
Ok(())
}
pub(crate) fn validate_simplex_vertex_keys(&self) -> Result<(), TdsError> {
for (simplex_key, simplex) in &self.simplices {
let simplex_uuid = simplex.uuid();
for (vertex_idx, &vertex_key) in simplex.vertices().iter().enumerate() {
if !self.vertices.contains_key(vertex_key) {
return Err(TdsError::VertexNotFound {
vertex_key,
context: format!(
"referenced by simplex {simplex_uuid} (key {simplex_key:?}) at position {vertex_idx}"
),
});
}
}
}
Ok(())
}
fn validate_vertex_incidence(&self) -> Result<(), TdsError> {
for (vertex_key, vertex) in &self.vertices {
let Some(incident_simplex_key) = vertex.incident_simplex() else {
continue;
};
let Some(incident_simplex) = self.simplices.get(incident_simplex_key) else {
return Err(TdsError::SimplexNotFound {
simplex_key: incident_simplex_key,
context: format!(
"dangling incident_simplex pointer from vertex {vertex_key:?}"
),
});
};
if !incident_simplex.contains_vertex(vertex_key) {
return Err(TdsError::InconsistentDataStructure {
message: format!(
"Vertex {vertex_key:?} incident_simplex {incident_simplex_key:?} does not contain the vertex"
),
});
}
}
Ok(())
}
fn validate_no_duplicate_simplices(&self) -> Result<(), TdsError> {
let mut unique_simplices: FastHashMap<Vec<(Uuid, [i8; D])>, SimplexKey> =
fast_hash_map_with_capacity(self.simplices.len());
let mut duplicates = Vec::new();
for (simplex_key, _simplex) in &self.simplices {
let vertices = self.simplex_vertices(simplex_key)?;
let vertex_uuid_offsets =
self.build_periodic_vertex_uuid_offsets(simplex_key, &vertices)?;
if let Some(existing_simplex_key) = unique_simplices.get(&vertex_uuid_offsets) {
duplicates.push((
simplex_key,
*existing_simplex_key,
vertex_uuid_offsets.clone(),
));
} else {
unique_simplices.insert(vertex_uuid_offsets, simplex_key);
}
}
if !duplicates.is_empty() {
let duplicate_descriptions: Vec<String> = duplicates
.iter()
.map(|(simplex1, simplex2, vertex_uuids)| {
format!(
"simplices {simplex1:?} and {simplex2:?} with vertex UUIDs {vertex_uuids:?}"
)
})
.collect();
return Err(TdsError::DuplicateSimplices {
message: format!(
"Found {} duplicate simplex(s): {}",
duplicates.len(),
duplicate_descriptions.join(", ")
),
});
}
Ok(())
}
fn validate_simplex_coordinate_uniqueness(&self) -> Result<(), TdsError>
where
T: CoordinateScalar,
{
for (_simplex_key, simplex) in &self.simplices {
let vkeys = simplex.vertices();
for i in 0..vkeys.len() {
let Some(vi) = self.vertex(vkeys[i]) else {
continue; };
for j in (i + 1)..vkeys.len() {
if vkeys[i] == vkeys[j] {
continue;
}
let Some(vj) = self.vertex(vkeys[j]) else {
continue;
};
if coords_equal_exact(vi.point().coords(), vj.point().coords()) {
return Err(TdsError::DuplicateCoordinatesInSimplex {
simplex_id: simplex.uuid(),
message: format!(
"vertices {:?} and {:?} (keys {:?}, {:?}) have identical coordinates {:?}",
vi.uuid(),
vj.uuid(),
vkeys[i],
vkeys[j],
vi.point().coords(),
),
});
}
}
}
}
Ok(())
}
pub(crate) fn validate_facet_sharing(&self) -> Result<(), TdsError> {
let facet_to_simplices = self.build_facet_to_simplices_map()?;
self.validate_facet_sharing_with_facet_to_simplices_map(&facet_to_simplices)
}
#[must_use]
pub fn is_coherently_oriented(&self) -> bool {
self.validate_coherent_orientation().is_ok()
}
fn validate_coherent_orientation(&self) -> Result<(), TdsError> {
for (simplex_key, simplex) in &self.simplices {
let Some(neighbors) = simplex.neighbor_keys() else {
continue;
};
for (facet_idx, neighbor_key_opt) in neighbors.enumerate() {
let Some(neighbor_key) = neighbor_key_opt else {
continue; };
if neighbor_key == simplex_key && Self::allows_periodic_self_neighbor(simplex) {
continue;
}
let neighbor_simplex =
self.simplices
.get(neighbor_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key: neighbor_key,
context: format!(
"neighbor of simplex {simplex_key:?} during orientation validation",
),
})?;
let (mirror_idx, uses_periodic_offsets) = Self::orientation_mirror_facet_index(
simplex,
facet_idx,
neighbor_simplex,
"orientation validation",
)?;
let back_neighbor = neighbor_simplex
.neighbor_key(mirror_idx)
.flatten()
.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::BackReferenceMismatch {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_key,
neighbor_uuid: neighbor_simplex.uuid(),
mirror_index: mirror_idx,
observed: None,
context: "orientation validation".to_string(),
},
})?;
if back_neighbor != simplex_key {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::BackReferenceMismatch {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_key,
neighbor_uuid: neighbor_simplex.uuid(),
mirror_index: mirror_idx,
observed: Some(back_neighbor),
context: "orientation validation".to_string(),
},
});
}
if uses_periodic_offsets {
continue;
}
let simplex1_facet_vertices =
Self::facet_vertices_in_simplex_order(simplex, facet_idx)?;
let simplex2_facet_vertices =
Self::facet_vertices_in_simplex_order(neighbor_simplex, mirror_idx)?;
let (currently_coherent, observed_odd_permutation, expected_odd_permutation) =
Self::facet_permutation_parity(
simplex,
facet_idx,
neighbor_simplex,
mirror_idx,
)?;
if !currently_coherent {
return Err(TdsError::OrientationViolation {
simplex1_key: simplex_key,
simplex1_uuid: simplex.uuid(),
simplex2_key: neighbor_key,
simplex2_uuid: neighbor_simplex.uuid(),
simplex1_facet_index: facet_idx,
simplex2_facet_index: mirror_idx,
facet_vertices: simplex1_facet_vertices.into_iter().collect(),
simplex2_facet_vertices: simplex2_facet_vertices.into_iter().collect(),
observed_odd_permutation,
expected_odd_permutation,
});
}
}
}
Ok(())
}
fn orientation_mirror_facet_index(
simplex: &Simplex<T, U, V, D>,
facet_idx: usize,
neighbor_simplex: &Simplex<T, U, V, D>,
context: &str,
) -> Result<(usize, bool), TdsError> {
let uses_periodic_offsets = simplex.periodic_vertex_offsets().is_some()
|| neighbor_simplex.periodic_vertex_offsets().is_some();
let mirror_idx = if uses_periodic_offsets {
Self::matching_lifted_mirror_facet_index(simplex, facet_idx, neighbor_simplex, context)?
} else {
simplex
.mirror_facet_index(facet_idx, neighbor_simplex)
.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetMissing {
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_uuid: neighbor_simplex.uuid(),
context: context.to_string(),
},
})?
};
Ok((mirror_idx, uses_periodic_offsets))
}
fn facet_vertices_in_simplex_order(
simplex: &Simplex<T, U, V, D>,
omit_idx: usize,
) -> Result<SmallBuffer<VertexKey, MAX_PRACTICAL_DIMENSION_SIZE>, TdsError> {
if omit_idx >= simplex.number_of_vertices() {
return Err(TdsError::IndexOutOfBounds {
index: omit_idx,
bound: simplex.number_of_vertices(),
context: format!(
"facet index for simplex {:?} during orientation validation",
simplex.uuid(),
),
});
}
let mut facet_vertices = SmallBuffer::new();
for (idx, &vkey) in simplex.vertices().iter().enumerate() {
if idx != omit_idx {
facet_vertices.push(vkey);
}
}
Ok(facet_vertices)
}
fn facet_vertex_identities_in_simplex_order(
simplex: &Simplex<T, U, V, D>,
omit_idx: usize,
) -> Result<SmallBuffer<(VertexKey, [i16; D]), MAX_PRACTICAL_DIMENSION_SIZE>, TdsError> {
if omit_idx >= simplex.number_of_vertices() {
return Err(TdsError::IndexOutOfBounds {
index: omit_idx,
bound: simplex.number_of_vertices(),
context: format!(
"facet index for simplex {:?} during orientation validation",
simplex.uuid(),
),
});
}
let periodic_offsets = simplex.periodic_vertex_offsets();
if let Some(offsets) = periodic_offsets
&& offsets.len() != simplex.number_of_vertices()
{
return Err(TdsError::DimensionMismatch {
expected: simplex.number_of_vertices(),
actual: offsets.len(),
context: format!(
"periodic offset count for simplex {:?} during orientation validation",
simplex.uuid(),
),
});
}
let mut facet_identities: SmallBuffer<(VertexKey, [i16; D]), MAX_PRACTICAL_DIMENSION_SIZE> =
SmallBuffer::new();
for (idx, &vkey) in simplex.vertices().iter().enumerate() {
if idx == omit_idx {
continue;
}
let raw_offset = periodic_offsets.map_or([0_i8; D], |offsets| offsets[idx]);
let mut offset = [0_i16; D];
for axis in 0..D {
offset[axis] = i16::from(raw_offset[axis]);
}
facet_identities.push((vkey, offset));
}
let mut anchor_key = u64::MAX;
let mut anchor_offset = [0_i16; D];
for (vkey, offset) in &facet_identities {
let key_value = vkey.data().as_ffi();
if key_value < anchor_key || (key_value == anchor_key && *offset < anchor_offset) {
anchor_key = key_value;
anchor_offset = *offset;
}
}
for (_, offset) in &mut facet_identities {
for axis in 0..D {
offset[axis] -= anchor_offset[axis];
}
}
Ok(facet_identities)
}
fn facet_permutation_parity(
simplex: &Simplex<T, U, V, D>,
facet_idx: usize,
neighbor_simplex: &Simplex<T, U, V, D>,
mirror_idx: usize,
) -> Result<(bool, bool, bool), TdsError> {
let simplex_facet_identities =
Self::facet_vertex_identities_in_simplex_order(simplex, facet_idx)?;
let neighbor_facet_identities =
Self::facet_vertex_identities_in_simplex_order(neighbor_simplex, mirror_idx)?;
let observed_odd_permutation = Self::permutation_is_odd(
&simplex_facet_identities[..],
&neighbor_facet_identities[..],
)
.ok_or_else(|| TdsError::InconsistentDataStructure {
message: format!(
"Could not derive facet-order permutation parity between simplices {:?} and {:?}",
simplex.uuid(),
neighbor_simplex.uuid(),
),
})?;
let expected_odd_permutation = (facet_idx + mirror_idx).is_multiple_of(2);
Ok((
observed_odd_permutation == expected_odd_permutation,
observed_odd_permutation,
expected_odd_permutation,
))
}
fn permutation_is_odd<Id: PartialEq>(source_order: &[Id], target_order: &[Id]) -> Option<bool> {
if source_order.len() != target_order.len() {
return None;
}
let mut target_positions: SmallBuffer<usize, MAX_PRACTICAL_DIMENSION_SIZE> =
SmallBuffer::with_capacity(source_order.len());
let mut used_target_indices: SmallBuffer<bool, MAX_PRACTICAL_DIMENSION_SIZE> =
SmallBuffer::from_elem(false, target_order.len());
for source_vertex in source_order {
let mut matched_target_position = None;
for (target_idx, target_vertex) in target_order.iter().enumerate() {
if target_vertex == source_vertex && !used_target_indices[target_idx] {
matched_target_position = Some(target_idx);
used_target_indices[target_idx] = true;
break;
}
}
target_positions.push(matched_target_position?);
}
if used_target_indices.iter().any(|used| !*used) {
return None;
}
let mut is_odd = false;
for i in 0..target_positions.len() {
for j in (i + 1)..target_positions.len() {
if target_positions[i] > target_positions[j] {
is_odd = !is_odd;
}
}
}
Some(is_odd)
}
fn validate_facet_sharing_with_facet_to_simplices_map(
&self,
facet_to_simplices: &FacetToSimplicesMap,
) -> Result<(), TdsError> {
for (facet_key, simplex_facet_pairs) in facet_to_simplices {
let [_, _, candidate, ..] = simplex_facet_pairs.as_slice() else {
continue;
};
let candidate_simplex =
self.simplex(candidate.simplex_key())
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key: candidate.simplex_key(),
context: format!(
"facet-sharing validation for over-shared facet {facet_key}"
),
})?;
return Err(TdsError::FacetSharingViolation {
facet_key: *facet_key,
existing_incident_count: simplex_facet_pairs.len() - 1,
attempted_incident_count: simplex_facet_pairs.len(),
max_incident_count: 2,
candidate_simplex_uuid: candidate_simplex.uuid(),
candidate_facet_index: usize::from(candidate.facet_index()),
});
}
Ok(())
}
pub fn is_valid(&self) -> Result<(), TdsError> {
self.validate_vertex_mappings()?;
self.validate_simplex_mappings()?;
self.validate_simplex_vertex_keys()?;
self.validate_vertex_incidence()?;
self.validate_no_duplicate_simplices()?;
let facet_to_simplices = self.build_facet_to_simplices_map()?;
self.validate_facet_sharing_with_facet_to_simplices_map(&facet_to_simplices)?;
self.validate_neighbors_with_facet_to_simplices_map(&facet_to_simplices)?;
self.validate_coherent_orientation()?;
Ok(())
}
pub fn validate(&self) -> Result<(), TdsError>
where
T: CoordinateScalar,
{
for (_vertex_key, vertex) in &self.vertices {
if let Err(source) = (*vertex).is_valid() {
return Err(TdsError::InvalidVertex {
vertex_id: vertex.uuid(),
source,
});
}
}
for (simplex_key, simplex) in &self.simplices {
if let Err(source) = simplex.is_valid() {
let Some(simplex_id) = self.simplex_uuid_from_key(simplex_key) else {
return Err(TdsError::InconsistentDataStructure {
message: format!(
"Simplex key {simplex_key:?} has no UUID mapping during validation",
),
});
};
return Err(TdsError::InvalidSimplex { simplex_id, source });
}
}
if self.validate_simplex_vertex_keys().is_ok() {
self.validate_simplex_coordinate_uniqueness()?;
}
self.is_valid()
}
#[expect(
clippy::too_many_lines,
reason = "validation report aggregation is intentionally linear and simplex nomenclature makes existing names longer"
)]
pub(crate) fn validation_report(&self) -> Result<(), TriangulationValidationReport>
where
T: CoordinateScalar,
{
let mut violations = Vec::new();
if let Err(e) = self.validate_vertex_mappings() {
violations.push(InvariantViolation {
kind: InvariantKind::VertexMappings,
error: e.into(),
});
}
if let Err(e) = self.validate_simplex_mappings() {
violations.push(InvariantViolation {
kind: InvariantKind::SimplexMappings,
error: e.into(),
});
}
if !violations.is_empty() {
return Err(TriangulationValidationReport { violations });
}
let mut simplex_vertex_keys_ok = true;
if let Err(e) = self.validate_simplex_vertex_keys() {
simplex_vertex_keys_ok = false;
violations.push(InvariantViolation {
kind: InvariantKind::SimplexVertexKeys,
error: e.into(),
});
}
if simplex_vertex_keys_ok && let Err(e) = self.validate_simplex_coordinate_uniqueness() {
violations.push(InvariantViolation {
kind: InvariantKind::SimplexCoordinateUniqueness,
error: e.into(),
});
}
if let Err(e) = self.validate_vertex_incidence() {
violations.push(InvariantViolation {
kind: InvariantKind::VertexIncidence,
error: e.into(),
});
}
if !simplex_vertex_keys_ok {
return Err(TriangulationValidationReport { violations });
}
if let Err(e) = self.validate_no_duplicate_simplices() {
violations.push(InvariantViolation {
kind: InvariantKind::DuplicateSimplices,
error: e.into(),
});
}
let mut neighbor_consistency_ok = false;
match self.build_facet_to_simplices_map() {
Ok(facet_to_simplices) => {
if let Err(e) =
self.validate_facet_sharing_with_facet_to_simplices_map(&facet_to_simplices)
{
violations.push(InvariantViolation {
kind: InvariantKind::FacetSharing,
error: e.into(),
});
}
if let Err(e) =
self.validate_neighbors_with_facet_to_simplices_map(&facet_to_simplices)
{
violations.push(InvariantViolation {
kind: InvariantKind::NeighborConsistency,
error: e.into(),
});
} else {
neighbor_consistency_ok = true;
}
}
Err(e) => {
violations.push(InvariantViolation {
kind: InvariantKind::FacetSharing,
error: e.clone().into(),
});
violations.push(InvariantViolation {
kind: InvariantKind::NeighborConsistency,
error: e.into(),
});
}
}
if neighbor_consistency_ok && let Err(e) = self.validate_coherent_orientation() {
violations.push(InvariantViolation {
kind: InvariantKind::CoherentOrientation,
error: e.into(),
});
}
if !self.is_connected() {
violations.push(InvariantViolation {
kind: InvariantKind::Connectedness,
error: TdsError::InconsistentDataStructure {
message: format!(
"Disconnected triangulation: simplex neighbor graph is not a single \
connected component ({} simplices total)",
self.simplices.len()
),
}
.into(),
});
}
if violations.is_empty() {
Ok(())
} else {
Err(TriangulationValidationReport { violations })
}
}
fn validate_neighbors_with_facet_to_simplices_map(
&self,
facet_to_simplices: &FacetToSimplicesMap,
) -> Result<(), TdsError> {
self.validate_neighbor_pointers_match_facet_to_simplices_map(facet_to_simplices)?;
let simplex_vertices = self.build_simplex_vertex_sets()?;
self.validate_neighbors_with_precomputed_vertex_sets(&simplex_vertices)
}
fn validate_neighbor_pointers_match_facet_to_simplices_map(
&self,
facet_to_simplices: &FacetToSimplicesMap,
) -> Result<(), TdsError> {
for (facet_key, simplex_facet_pairs) in facet_to_simplices {
match simplex_facet_pairs.as_slice() {
[handle] => self.validate_boundary_facet_neighbor_pointer(*facet_key, *handle)?,
[a, b] => self.validate_interior_facet_neighbor_pointer(*facet_key, *a, *b)?,
_ => {
return Err(TdsError::InconsistentDataStructure {
message: format!(
"Facet with key {facet_key} is shared by {} simplices, but should be shared by at most 2 simplices in a valid triangulation",
simplex_facet_pairs.len()
),
});
}
}
}
Ok(())
}
fn validate_boundary_facet_neighbor_pointer(
&self,
facet_key: u64,
handle: FacetHandle,
) -> Result<(), TdsError> {
let simplex_key = handle.simplex_key();
let facet_index = handle.facet_index() as usize;
let simplex = self
.simplices
.get(simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key,
context: "neighbor validation (boundary facet)".to_string(),
})?;
let Some(neighbor_slots) = simplex.neighbor_slots() else {
return Ok(());
};
let Some(neighbor_slot) = neighbor_slots.get(facet_index).copied() else {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::LengthMismatch {
actual: neighbor_slots.len(),
expected: D + 1,
context: "neighbor validation (boundary facet)".to_string(),
},
});
};
match neighbor_slot {
NeighborSlot::Unassigned => Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::UnassignedNeighborSlot {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index,
context: "neighbor validation (boundary facet)".to_string(),
},
}),
NeighborSlot::Boundary => Ok(()),
NeighborSlot::Neighbor(neighbor) if neighbor == simplex_key => {
if Self::allows_periodic_self_neighbor(simplex) {
return Ok(());
}
Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::BoundaryFacetHasNonPeriodicSelfNeighbor {
facet_key,
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index,
},
})
}
NeighborSlot::Neighbor(neighbor) => Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::BoundaryFacetHasNeighbor {
facet_key,
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index,
neighbor_key: neighbor,
},
}),
}
}
fn validate_interior_facet_neighbor_pointer(
&self,
facet_key: u64,
first: FacetHandle,
second: FacetHandle,
) -> Result<(), TdsError> {
let first_simplex_key = first.simplex_key();
let first_facet_index = first.facet_index() as usize;
let second_simplex_key = second.simplex_key();
let second_facet_index = second.facet_index() as usize;
let first_simplex =
self.simplices
.get(first_simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key: first_simplex_key,
context: "neighbor validation (interior facet, first simplex)".to_string(),
})?;
let second_simplex =
self.simplices
.get(second_simplex_key)
.ok_or_else(|| TdsError::SimplexNotFound {
simplex_key: second_simplex_key,
context: "neighbor validation (interior facet, second simplex)".to_string(),
})?;
let first_neighbor = first_simplex.neighbor_key(first_facet_index).flatten();
let second_neighbor = second_simplex.neighbor_key(second_facet_index).flatten();
if first_neighbor == Some(second_simplex_key) && second_neighbor == Some(first_simplex_key)
{
return Ok(());
}
Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::InteriorFacetNeighborMismatch {
facet_key,
first_simplex_key,
first_simplex_uuid: first_simplex.uuid(),
first_facet_index,
first_neighbor,
second_simplex_key,
second_simplex_uuid: second_simplex.uuid(),
second_facet_index,
second_neighbor,
},
})
}
fn validate_neighbors_with_precomputed_vertex_sets(
&self,
simplex_vertices: &SimplexVerticesMap,
) -> Result<(), TdsError> {
for (simplex_key, simplex) in &self.simplices {
let Some(neighbor_keys) = simplex.neighbor_keys() else {
continue; };
let neighbors_buf: NeighborBuffer<Option<SimplexKey>> = neighbor_keys.collect();
self.validate_neighbor_topology(simplex_key, &neighbors_buf)?;
let this_vertices = simplex_vertices.get(&simplex_key).ok_or_else(|| {
TdsError::InconsistentDataStructure {
message: format!(
"Simplex {} (key {simplex_key:?}) missing from precomputed vertex set map during neighbor validation",
simplex.uuid()
),
}
})?;
for (facet_idx, neighbor_key_opt) in neighbors_buf.iter().copied().enumerate() {
let Some(neighbor_key) = neighbor_key_opt else {
continue;
};
if neighbor_key == simplex_key {
if Self::allows_periodic_self_neighbor(simplex) {
continue;
}
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::NonPeriodicSelfNeighbor {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
},
});
}
let Some(neighbor_simplex) = self.simplices.get(neighbor_key) else {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::MissingNeighborSimplex {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_key,
context: "precomputed neighbor validation".to_string(),
},
});
};
if simplex.periodic_vertex_offsets().is_some()
|| neighbor_simplex.periodic_vertex_offsets().is_some()
{
continue;
}
let neighbor_vertices = simplex_vertices.get(&neighbor_key).ok_or_else(|| {
TdsError::InconsistentDataStructure {
message: format!(
"Neighbor simplex {} (key {neighbor_key:?}) missing from precomputed vertex set map during neighbor validation",
neighbor_simplex.uuid()
),
}
})?;
Self::validate_shared_facet_count(
simplex,
neighbor_simplex,
this_vertices,
neighbor_vertices,
)?;
let mirror_idx = Self::verified_mirror_facet_index(
simplex,
facet_idx,
neighbor_simplex,
this_vertices,
)?;
Self::validate_shared_facet_vertices(
simplex,
facet_idx,
neighbor_simplex,
mirror_idx,
this_vertices,
neighbor_vertices,
)?;
Self::validate_mutual_neighbor_back_reference(
simplex_key,
simplex,
facet_idx,
neighbor_key,
neighbor_simplex,
mirror_idx,
)?;
}
}
Ok(())
}
fn build_simplex_vertex_sets(&self) -> Result<SimplexVerticesMap, TdsError> {
let mut simplex_vertices: SimplexVerticesMap =
fast_hash_map_with_capacity(self.simplices.len());
for simplex_key in self.simplices.keys() {
let vertices = self.simplex_vertices(simplex_key)?;
let vertex_set: VertexKeySet = vertices.iter().copied().collect();
simplex_vertices.insert(simplex_key, vertex_set);
}
Ok(simplex_vertices)
}
fn validate_shared_facet_count(
simplex: &Simplex<T, U, V, D>,
neighbor_simplex: &Simplex<T, U, V, D>,
this_vertices: &VertexKeySet,
neighbor_vertices: &VertexKeySet,
) -> Result<(), TdsError> {
let shared_count = this_vertices.intersection(neighbor_vertices).count();
if shared_count != D {
return Err(TdsError::NotNeighbors {
simplex1: simplex.uuid(),
simplex2: neighbor_simplex.uuid(),
});
}
Ok(())
}
fn verified_mirror_facet_index(
simplex: &Simplex<T, U, V, D>,
facet_idx: usize,
neighbor_simplex: &Simplex<T, U, V, D>,
this_vertices: &VertexKeySet,
) -> Result<usize, TdsError> {
let mirror_idx = simplex
.mirror_facet_index(facet_idx, neighbor_simplex)
.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetMissing {
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_uuid: neighbor_simplex.uuid(),
context: "neighbor validation".to_string(),
},
})?;
let expected_mirror_idx =
Self::expected_mirror_facet_index(simplex, neighbor_simplex, this_vertices)?;
if mirror_idx != expected_mirror_idx {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetIndexMismatch {
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_uuid: neighbor_simplex.uuid(),
observed_mirror_index: mirror_idx,
expected_mirror_index: expected_mirror_idx,
},
});
}
Ok(mirror_idx)
}
fn expected_mirror_facet_index(
simplex: &Simplex<T, U, V, D>,
neighbor_simplex: &Simplex<T, U, V, D>,
this_vertices: &VertexKeySet,
) -> Result<usize, TdsError> {
let mut expected_mirror_idx: Option<usize> = None;
for (idx, &neighbor_vkey) in neighbor_simplex.vertices().iter().enumerate() {
if !this_vertices.contains(&neighbor_vkey) {
if expected_mirror_idx.is_some() {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetAmbiguous {
simplex_uuid: simplex.uuid(),
neighbor_uuid: neighbor_simplex.uuid(),
},
});
}
expected_mirror_idx = Some(idx);
}
}
expected_mirror_idx.ok_or_else(|| TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetDuplicateSimplices {
simplex_uuid: simplex.uuid(),
neighbor_uuid: neighbor_simplex.uuid(),
},
})
}
fn validate_shared_facet_vertices(
simplex: &Simplex<T, U, V, D>,
facet_idx: usize,
neighbor_simplex: &Simplex<T, U, V, D>,
mirror_idx: usize,
this_vertices: &VertexKeySet,
neighbor_vertices: &VertexKeySet,
) -> Result<(), TdsError> {
for (idx, &vkey) in simplex.vertices().iter().enumerate() {
if idx == facet_idx {
continue;
}
if !neighbor_vertices.contains(&vkey) {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::SharedFacetMissingVertex {
side: SharedFacetMismatchSide::SourceFacet,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_uuid: neighbor_simplex.uuid(),
mirror_index: mirror_idx,
missing_vertex: vkey,
},
});
}
}
for (idx, &vkey) in neighbor_simplex.vertices().iter().enumerate() {
if idx == mirror_idx {
continue;
}
if !this_vertices.contains(&vkey) {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::SharedFacetMissingVertex {
side: SharedFacetMismatchSide::NeighborFacet,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_uuid: neighbor_simplex.uuid(),
mirror_index: mirror_idx,
missing_vertex: vkey,
},
});
}
}
Ok(())
}
fn validate_mutual_neighbor_back_reference(
simplex_key: SimplexKey,
simplex: &Simplex<T, U, V, D>,
facet_idx: usize,
neighbor_key: SimplexKey,
neighbor_simplex: &Simplex<T, U, V, D>,
mirror_idx: usize,
) -> Result<(), TdsError> {
let Some(back_ref) = neighbor_simplex.neighbor_key(mirror_idx) else {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::BackReferenceMismatch {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_key,
neighbor_uuid: neighbor_simplex.uuid(),
mirror_index: mirror_idx,
observed: None,
context: "neighbor validation; neighbor has no neighbor buffer".to_string(),
},
});
};
if back_ref != Some(simplex_key) {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::BackReferenceMismatch {
simplex_key,
simplex_uuid: simplex.uuid(),
facet_index: facet_idx,
neighbor_key,
neighbor_uuid: neighbor_simplex.uuid(),
mirror_index: mirror_idx,
observed: back_ref,
context: "neighbor validation".to_string(),
},
});
}
Ok(())
}
}
type SimplexUuidSortKey<const D: usize> = Vec<(Uuid, [i8; D])>;
type SimplexUuidSortEntry<'a, T, U, V, const D: usize> =
(SimplexUuidSortKey<D>, &'a Simplex<T, U, V, D>);
fn simplex_uuid_sort_entries<T, U, V, const D: usize>(
tds: &Tds<T, U, V, D>,
) -> Option<Vec<SimplexUuidSortEntry<'_, T, U, V, D>>>
where
T: CoordinateScalar,
U: DataType,
V: DataType,
{
tds.simplices
.values()
.map(|simplex| {
let offsets = simplex.periodic_vertex_offsets();
if let Some(offsets) = offsets
&& offsets.len() != simplex.number_of_vertices()
{
return None;
}
let mut ids = Vec::with_capacity(simplex.number_of_vertices());
for (idx, &vkey) in simplex.vertices().iter().enumerate() {
let uuid = tds.vertex(vkey).map(Vertex::uuid)?;
let offset = offsets.map_or([0_i8; D], |offsets| offsets[idx]);
ids.push((uuid, offset));
}
ids.sort_unstable();
Some((ids, simplex))
})
.collect()
}
impl<T, U, V, const D: usize> PartialEq for Tds<T, U, V, D>
where
T: CoordinateScalar,
U: DataType,
V: DataType,
{
fn eq(&self, other: &Self) -> bool {
if self.vertices.len() != other.vertices.len()
|| self.simplices.len() != other.simplices.len()
|| self.uuid_to_vertex_key.len() != other.uuid_to_vertex_key.len()
|| self.uuid_to_simplex_key.len() != other.uuid_to_simplex_key.len()
{
return false;
}
let mut self_vertices: Vec<_> = self.vertices.values().collect();
let mut other_vertices: Vec<_> = other.vertices.values().collect();
self_vertices.sort_by(|a, b| {
let a_coords = *a.point().coords();
let b_coords = *b.point().coords();
a_coords
.partial_cmp(&b_coords)
.unwrap_or(CmpOrdering::Equal)
});
other_vertices.sort_by(|a, b| {
let a_coords = *a.point().coords();
let b_coords = *b.point().coords();
a_coords
.partial_cmp(&b_coords)
.unwrap_or(CmpOrdering::Equal)
});
if self_vertices != other_vertices {
return false;
}
let (Some(mut self_simplices), Some(mut other_simplices)) = (
simplex_uuid_sort_entries(self),
simplex_uuid_sort_entries(other),
) else {
return false;
};
self_simplices.sort_by(|(a_ids, _), (b_ids, _)| a_ids.cmp(b_ids));
other_simplices.sort_by(|(a_ids, _), (b_ids, _)| a_ids.cmp(b_ids));
if self_simplices.len() != other_simplices.len() {
return false;
}
for ((_, self_simplex), (_, other_simplex)) in
self_simplices.iter().zip(other_simplices.iter())
{
if !self_simplex.eq_by_vertices(self, other_simplex, other) {
return false;
}
}
true
}
}
impl<T, U, V, const D: usize> Eq for Tds<T, U, V, D>
where
T: CoordinateScalar,
U: DataType,
V: DataType,
{
}
impl<T, U, V, const D: usize> Serialize for Tds<T, U, V, D>
where
T: CoordinateScalar,
U: DataType,
V: DataType,
{
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: serde::Serializer,
{
let simplex_vertices: FastHashMap<Uuid, Vec<Uuid>> = self
.simplices
.iter()
.map(|(_simplex_key, simplex)| {
let simplex_uuid = simplex.uuid();
let vertex_uuids = simplex
.vertex_uuids(self)
.map_err(serde::ser::Error::custom)?;
Ok((simplex_uuid, vertex_uuids.to_vec()))
})
.collect::<Result<_, _>>()?;
let mut state = serializer.serialize_struct("Tds", 3)?;
state.serialize_field("vertices", &self.vertices)?;
state.serialize_field("simplices", &self.simplices)?;
state.serialize_field("simplex_vertices", &simplex_vertices)?;
state.end()
}
}
impl<'de, T, U, V, const D: usize> Deserialize<'de> for Tds<T, U, V, D>
where
T: CoordinateScalar,
U: DataType,
V: DataType,
{
fn deserialize<D2>(deserializer: D2) -> Result<Self, D2::Error>
where
D2: Deserializer<'de>,
{
#[derive(Deserialize)]
#[serde(field_identifier, rename_all = "snake_case")]
enum Field {
Vertices,
Simplices,
SimplexVertices,
}
struct TdsVisitor<T, U, V, const D: usize>(PhantomData<(T, U, V)>);
impl<'de, T, U, V, const D: usize> Visitor<'de> for TdsVisitor<T, U, V, D>
where
T: CoordinateScalar,
U: DataType,
V: DataType,
{
type Value = Tds<T, U, V, D>;
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
formatter.write_str("struct Tds")
}
fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
where
A: MapAccess<'de>,
{
let mut vertices: Option<StorageMap<VertexKey, Vertex<T, U, D>>> = None;
let mut simplices: Option<StorageMap<SimplexKey, Simplex<T, U, V, D>>> = None;
let mut simplex_vertices: Option<FastHashMap<Uuid, Vec<Uuid>>> = 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()?);
}
Field::Simplices => {
if simplices.is_some() {
return Err(de::Error::duplicate_field("simplices"));
}
simplices = Some(map.next_value()?);
}
Field::SimplexVertices => {
if simplex_vertices.is_some() {
return Err(de::Error::duplicate_field("simplex_vertices"));
}
simplex_vertices = Some(map.next_value()?);
}
}
}
let vertices = vertices.ok_or_else(|| de::Error::missing_field("vertices"))?;
let mut simplices =
simplices.ok_or_else(|| de::Error::missing_field("simplices"))?;
let simplex_vertices =
simplex_vertices.ok_or_else(|| de::Error::missing_field("simplex_vertices"))?;
let mut uuid_to_vertex_key = fast_hash_map_with_capacity(vertices.len());
for (vertex_key, vertex) in &vertices {
uuid_to_vertex_key.insert(vertex.uuid(), vertex_key);
}
let mut uuid_to_simplex_key = fast_hash_map_with_capacity(simplices.len());
for (simplex_key, simplex) in &simplices {
uuid_to_simplex_key.insert(simplex.uuid(), simplex_key);
}
for (_simplex_key, simplex) in &mut simplices {
let simplex_uuid = simplex.uuid();
if let Some(vertex_uuids) = simplex_vertices.get(&simplex_uuid) {
simplex.clear_vertex_keys();
for &vertex_uuid in vertex_uuids {
if let Some(&vertex_key) = uuid_to_vertex_key.get(&vertex_uuid) {
simplex.push_vertex_key(vertex_key);
} else {
return Err(de::Error::custom(format!(
"Vertex UUID {vertex_uuid} referenced by simplex {simplex_uuid} not found in vertices"
)));
}
}
} else {
return Err(de::Error::custom(format!(
"No vertex UUIDs found for simplex {simplex_uuid}"
)));
}
}
let mut tds = Tds {
vertices,
simplices,
uuid_to_vertex_key,
uuid_to_simplex_key,
construction_state: TriangulationConstructionState::Constructed,
generation: Arc::new(AtomicU64::new(0)),
identity: Arc::new(Uuid::new_v4()),
};
tds.assign_neighbors().map_err(de::Error::custom)?;
tds.assign_incident_simplices().map_err(de::Error::custom)?;
Ok(tds)
}
}
const FIELDS: &[&str] = &["vertices", "simplices", "simplex_vertices"];
deserializer.deserialize_struct("Tds", FIELDS, TdsVisitor(PhantomData))
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::DelaunayTriangulation;
use crate::builder::DelaunayTriangulationBuilder;
use crate::core::algorithms::flips::DelaunayRepairError;
use crate::core::algorithms::incremental_insertion::InsertionError;
use crate::core::collections::NeighborBuffer;
use crate::core::facet::FacetError;
use crate::core::simplex::Simplex;
use crate::core::util::uuid::UuidValidationError;
use crate::core::validation::TriangulationValidationError;
use crate::core::vertex::VertexBuilder;
use crate::geometry::point::Point;
use crate::geometry::traits::coordinate::Coordinate;
use crate::repair::DelaunayRepairOperation;
use crate::topology::characteristics::euler::TopologyClassification;
use crate::validation::DelaunayTriangulationValidationError;
use crate::vertex;
use slotmap::KeyData;
use std::sync::Arc;
#[cfg(test)]
fn vertex_with_uuid<T, U, const D: usize>(
point: Point<T, D>,
uuid: Uuid,
data: Option<U>,
) -> Vertex<T, U, D>
where
T: CoordinateScalar,
U: DataType,
{
let mut vertex = data.map_or_else(
|| {
VertexBuilder::default()
.point(point)
.build()
.expect("Failed to build vertex")
},
|data_value| {
VertexBuilder::default()
.point(point)
.data(data_value)
.build()
.expect("Failed to build vertex")
},
);
vertex.set_uuid(uuid).expect("Failed to set UUID");
vertex
}
fn initial_simplex_vertices_3d() -> [Vertex<f64, (), 3>; 4] {
[
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
]
}
fn assert_tds_error_kind(source: &TdsError, expected: TdsErrorKind) {
assert_eq!(TdsErrorKind::from(source), expected);
}
#[test]
fn tds_error_kind_from_error_preserves_validation_variants() {
let simplex_key = SimplexKey::from(KeyData::from_ffi(1));
let other_simplex_key = SimplexKey::from(KeyData::from_ffi(2));
let vertex_key = VertexKey::from(KeyData::from_ffi(3));
let uuid = Uuid::new_v4();
assert_tds_error_kind(
&TdsError::InvalidVertex {
vertex_id: uuid,
source: VertexValidationError::InvalidUuid {
source: UuidValidationError::NilUuid,
},
},
TdsErrorKind::InvalidVertex,
);
assert_tds_error_kind(
&TdsError::InvalidSimplex {
simplex_id: uuid,
source: SimplexValidationError::DuplicateVertices,
},
TdsErrorKind::InvalidSimplex,
);
assert_tds_error_kind(
&TdsError::InvalidNeighbors {
reason: NeighborValidationError::Other {
message: "neighbor invariant failed".to_string(),
},
},
TdsErrorKind::InvalidNeighbors,
);
assert_tds_error_kind(
&TdsError::OrientationViolation {
simplex1_key: simplex_key,
simplex1_uuid: uuid,
simplex2_key: other_simplex_key,
simplex2_uuid: Uuid::new_v4(),
simplex1_facet_index: 0,
simplex2_facet_index: 1,
facet_vertices: vec![vertex_key],
simplex2_facet_vertices: vec![vertex_key],
observed_odd_permutation: false,
expected_odd_permutation: true,
},
TdsErrorKind::OrientationViolation,
);
assert_tds_error_kind(
&TdsError::Geometric(GeometricError::DegenerateOrientation {
message: "zero determinant".to_string(),
}),
TdsErrorKind::Geometric,
);
assert_tds_error_kind(
&TdsError::FacetError(FacetError::InvalidFacetIndex {
index: 4,
facet_count: 4,
}),
TdsErrorKind::FacetError,
);
assert_tds_error_kind(
&TdsError::DuplicateCoordinatesInSimplex {
simplex_id: uuid,
message: "two vertices share coordinates".to_string(),
},
TdsErrorKind::DuplicateCoordinatesInSimplex,
);
}
#[test]
fn tds_error_kind_from_error_preserves_lookup_and_operation_variants() {
let simplex_key = SimplexKey::from(KeyData::from_ffi(1));
let vertex_key = VertexKey::from(KeyData::from_ffi(3));
let uuid = Uuid::new_v4();
assert_tds_error_kind(
&TdsError::DuplicateSimplices {
message: "duplicate simplex vertex set".to_string(),
},
TdsErrorKind::DuplicateSimplices,
);
assert_tds_error_kind(
&TdsError::FacetSharingViolation {
facet_key: 42,
existing_incident_count: 2,
attempted_incident_count: 3,
max_incident_count: 2,
candidate_simplex_uuid: uuid,
candidate_facet_index: 1,
},
TdsErrorKind::FacetSharingViolation,
);
assert_tds_error_kind(
&TdsError::FailedToCreateSimplex {
message: "simplex validation failed".to_string(),
},
TdsErrorKind::FailedToCreateSimplex,
);
assert_tds_error_kind(
&TdsError::NotNeighbors {
simplex1: uuid,
simplex2: Uuid::new_v4(),
},
TdsErrorKind::NotNeighbors,
);
assert_tds_error_kind(
&TdsError::MappingInconsistency {
entity: EntityKind::Simplex,
message: "uuid mapping was stale".to_string(),
},
TdsErrorKind::MappingInconsistency,
);
assert_tds_error_kind(
&TdsError::VertexKeyRetrievalFailed {
simplex_id: uuid,
message: "simplex vertices unavailable".to_string(),
},
TdsErrorKind::VertexKeyRetrievalFailed,
);
assert_tds_error_kind(
&TdsError::SimplexNotFound {
simplex_key,
context: "simplex lookup".to_string(),
},
TdsErrorKind::SimplexNotFound,
);
assert_tds_error_kind(
&TdsError::VertexNotFound {
vertex_key,
context: "vertex lookup".to_string(),
},
TdsErrorKind::VertexNotFound,
);
assert_tds_error_kind(
&TdsError::DimensionMismatch {
expected: 4,
actual: 3,
context: "simplex arity".to_string(),
},
TdsErrorKind::DimensionMismatch,
);
assert_tds_error_kind(
&TdsError::IndexOutOfBounds {
index: 4,
bound: 4,
context: "facet index".to_string(),
},
TdsErrorKind::IndexOutOfBounds,
);
assert_tds_error_kind(
&TdsError::InconsistentDataStructure {
message: "dangling neighbor".to_string(),
},
TdsErrorKind::InconsistentDataStructure,
);
}
#[test]
fn triangulation_validation_error_kind_from_error_preserves_all_variants() {
let vertex_key = VertexKey::from(KeyData::from_ffi(3));
let cases = [
(
TriangulationValidationError::ManifoldFacetMultiplicity {
facet_key: 0xabc,
simplex_count: 3,
},
TriangulationValidationErrorKind::ManifoldFacetMultiplicity,
),
(
TriangulationValidationError::BoundaryRidgeMultiplicity {
ridge_key: 0xdef,
boundary_facet_count: 3,
},
TriangulationValidationErrorKind::BoundaryRidgeMultiplicity,
),
(
TriangulationValidationError::RidgeLinkNotManifold {
ridge_key: 0x123,
link_vertex_count: 4,
link_edge_count: 2,
max_degree: 3,
degree_one_vertices: 1,
connected: false,
},
TriangulationValidationErrorKind::RidgeLinkNotManifold,
),
(
TriangulationValidationError::VertexLinkNotManifold {
vertex_key,
link_vertex_count: 4,
link_simplex_count: 2,
boundary_facet_count: 1,
max_degree: 3,
connected: false,
interior_vertex: true,
},
TriangulationValidationErrorKind::VertexLinkNotManifold,
),
(
TriangulationValidationError::EulerCharacteristicMismatch {
computed: 0,
expected: 1,
classification: TopologyClassification::Ball(3),
},
TriangulationValidationErrorKind::EulerCharacteristicMismatch,
),
(
TriangulationValidationError::IsolatedVertex {
vertex_key,
vertex_uuid: Uuid::new_v4(),
},
TriangulationValidationErrorKind::IsolatedVertex,
),
(
TriangulationValidationError::Disconnected { simplex_count: 2 },
TriangulationValidationErrorKind::Disconnected,
),
(
TriangulationValidationError::OrientationPromotionNonConvergence {
residual_count: 1,
sampled: vec![SimplexKey::from(KeyData::from_ffi(4))],
},
TriangulationValidationErrorKind::OrientationPromotionNonConvergence,
),
];
for (source, expected) in cases {
assert_eq!(TriangulationValidationErrorKind::from(&source), expected);
}
}
#[test]
fn delaunay_validation_error_kind_from_error_preserves_all_variants() {
let cases = [
(
DelaunayTriangulationValidationError::from(TdsError::InconsistentDataStructure {
message: "dangling simplex".to_string(),
}),
DelaunayValidationErrorKind::Tds,
),
(
DelaunayTriangulationValidationError::from(
TriangulationValidationError::Disconnected { simplex_count: 2 },
),
DelaunayValidationErrorKind::Triangulation,
),
(
DelaunayTriangulationValidationError::VerificationFailed {
message: "non-Delaunay facet".to_string(),
},
DelaunayValidationErrorKind::VerificationFailed,
),
(
DelaunayTriangulationValidationError::RepairFailed {
message: "repair did not converge".to_string(),
},
DelaunayValidationErrorKind::RepairFailed,
),
(
DelaunayTriangulationValidationError::RepairOperationFailed {
operation: DelaunayRepairOperation::VertexRemoval,
source: Box::new(DelaunayRepairError::PostconditionFailed {
message: "remaining violation".to_string(),
}),
},
DelaunayValidationErrorKind::RepairOperationFailed,
),
];
for (source, expected) in cases {
assert_eq!(DelaunayValidationErrorKind::from(&source), expected);
}
}
#[test]
fn test_facet_key_for_simplex_facet_maps_periodic_derivation_errors() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
tds.simplex_mut(simplex_key)
.unwrap()
.set_periodic_vertex_offsets(vec![[-128_i8, 0_i8], [127_i8, 0_i8], [0_i8, 0_i8]])
.unwrap();
let err = tds.facet_key_for_simplex_facet(simplex_key, 2).unwrap_err();
assert!(matches!(
err,
TdsError::InconsistentDataStructure { message }
if message.contains("Failed to derive periodic facet key")
&& message.contains("facet 2")
));
}
#[test]
fn test_facet_vertex_identities_anchor_uses_lexicographic_key_offset() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
{
let simplex = tds.simplex_mut(simplex_key).unwrap();
simplex.push_vertex_key(v_a);
simplex
.set_periodic_vertex_offsets(vec![[5, 0], [9, 0], [8, 0], [1, 0]])
.unwrap();
}
let simplex = tds.simplex(simplex_key).unwrap();
let identities =
Tds::<f64, (), (), 2>::facet_vertex_identities_in_simplex_order(simplex, 2).unwrap();
assert_eq!(identities.len(), 3);
let mut offsets_for_a: Vec<[i16; 2]> = identities
.iter()
.filter_map(|(vkey, offset)| (*vkey == v_a).then_some(*offset))
.collect();
offsets_for_a.sort_unstable();
assert_eq!(offsets_for_a, vec![[0, 0], [4, 0]]);
let b_offset = identities
.iter()
.find_map(|(vkey, offset)| (*vkey == v_b).then_some(*offset))
.expect("identity list should include v_b");
assert_eq!(b_offset, [8, 0]);
}
#[test]
fn test_facet_permutation_parity_derives_coherent_and_incoherent_cases() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex: Simplex<f64, (), (), 2> = Simplex::new(vec![v_a, v_b, v_c], None).unwrap();
let coherent_neighbor: Simplex<f64, (), (), 2> =
Simplex::new(vec![v_b, v_a, v_d], None).unwrap();
let coherent_mirror_idx = simplex.mirror_facet_index(2, &coherent_neighbor).unwrap();
let (currently_coherent, observed_odd_permutation, expected_odd_permutation) =
Tds::facet_permutation_parity(&simplex, 2, &coherent_neighbor, coherent_mirror_idx)
.unwrap();
assert!(currently_coherent);
assert!(observed_odd_permutation);
assert!(expected_odd_permutation);
let incoherent_neighbor: Simplex<f64, (), (), 2> =
Simplex::new(vec![v_a, v_b, v_d], None).unwrap();
let incoherent_mirror_idx = simplex.mirror_facet_index(2, &incoherent_neighbor).unwrap();
let (currently_coherent, observed_odd_permutation, expected_odd_permutation) =
Tds::facet_permutation_parity(&simplex, 2, &incoherent_neighbor, incoherent_mirror_idx)
.unwrap();
assert!(!currently_coherent);
assert!(!observed_odd_permutation);
assert!(expected_odd_permutation);
}
#[test]
fn test_facet_permutation_parity_smoke_4d() {
let mut tds: Tds<f64, (), (), 4> = Tds::empty();
let v_a = tds
.insert_vertex_with_mapping(vertex!([0.0, 0.0, 0.0, 0.0]))
.unwrap();
let v_b = tds
.insert_vertex_with_mapping(vertex!([1.0, 0.0, 0.0, 0.0]))
.unwrap();
let v_c = tds
.insert_vertex_with_mapping(vertex!([0.0, 1.0, 0.0, 0.0]))
.unwrap();
let v_d = tds
.insert_vertex_with_mapping(vertex!([0.0, 0.0, 1.0, 0.0]))
.unwrap();
let v_e = tds
.insert_vertex_with_mapping(vertex!([0.0, 0.0, 0.0, 1.0]))
.unwrap();
let v_f = tds
.insert_vertex_with_mapping(vertex!([1.0, 1.0, 1.0, 1.0]))
.unwrap();
let simplex: Simplex<f64, (), (), 4> =
Simplex::new(vec![v_a, v_b, v_c, v_d, v_e], None).unwrap();
let coherent_neighbor: Simplex<f64, (), (), 4> =
Simplex::new(vec![v_b, v_a, v_c, v_d, v_f], None).unwrap();
let coherent_mirror_idx = simplex.mirror_facet_index(4, &coherent_neighbor).unwrap();
let (currently_coherent, observed_odd_permutation, expected_odd_permutation) =
Tds::facet_permutation_parity(&simplex, 4, &coherent_neighbor, coherent_mirror_idx)
.unwrap();
assert!(currently_coherent);
assert!(observed_odd_permutation);
assert!(expected_odd_permutation);
let incoherent_neighbor: Simplex<f64, (), (), 4> =
Simplex::new(vec![v_a, v_b, v_c, v_d, v_f], None).unwrap();
let incoherent_mirror_idx = simplex.mirror_facet_index(4, &incoherent_neighbor).unwrap();
let (currently_coherent, observed_odd_permutation, expected_odd_permutation) =
Tds::facet_permutation_parity(&simplex, 4, &incoherent_neighbor, incoherent_mirror_idx)
.unwrap();
assert!(!currently_coherent);
assert!(!observed_odd_permutation);
assert!(expected_odd_permutation);
}
#[test]
fn test_repair_degenerate_simplices() {
let vertices = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
vertex!([1.0, 1.0]),
];
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_keys: Vec<_> = vertices
.iter()
.copied()
.map(|v| tds.insert_vertex_with_mapping(v).unwrap())
.collect();
let good_simplex = Simplex::new(vec![v_keys[0], v_keys[1], v_keys[2]], None).unwrap();
let good_simplex_key = tds.insert_simplex_with_mapping(good_simplex).unwrap();
let bad_simplex = Simplex::new(vec![v_keys[0], v_keys[1], v_keys[3]], None).unwrap();
let bad_simplex_key = tds.insert_simplex_with_mapping(bad_simplex).unwrap();
let removed_target_simplex =
Simplex::new(vec![v_keys[1], v_keys[2], v_keys[3]], None).unwrap();
let removed_target_key = tds
.insert_simplex_with_mapping(removed_target_simplex)
.unwrap();
assert_eq!(tds.remove_simplices_by_keys(&[removed_target_key]), 1);
{
let bad_simplex_mut = tds.simplex_mut(bad_simplex_key).unwrap();
let mut neighbors = NeighborBuffer::new();
neighbors.push(Some(removed_target_key));
neighbors.push(None);
neighbors.push(None);
bad_simplex_mut.set_neighbors_from_keys(neighbors).unwrap();
}
let removed_count = tds.repair_degenerate_simplices();
assert_eq!(
removed_count, 1,
"Expected exactly 1 degenerate simplex removed (bad_simplex with dangling neighbor), got {removed_count}",
);
assert_eq!(tds.number_of_simplices(), 1);
assert!(tds.simplices.contains_key(good_simplex_key));
assert!(!tds.simplices.contains_key(bad_simplex_key));
assert_eq!(tds.repair_degenerate_simplices(), 0);
assert!(tds.is_valid().is_ok());
println!("✓ repair_degenerate_simplices removes simplices with dangling neighbor pointers");
}
#[test]
fn test_add_vertex_basic_insertion_succeeds() {
let initial_vertices = initial_simplex_vertices_3d();
let mut dt = DelaunayTriangulation::new(&initial_vertices).unwrap();
let vertex = vertex!([1.0, 2.0, 3.0]);
let result = dt.insert(vertex);
assert!(result.is_ok(), "Basic vertex addition should succeed");
assert_eq!(dt.number_of_vertices(), 5);
}
#[test]
fn test_add_vertex_duplicate_coordinates_rejected() {
let initial_vertices = initial_simplex_vertices_3d();
let mut dt = DelaunayTriangulation::new(&initial_vertices).unwrap();
let vertex = vertex!([1.0, 2.0, 3.0]);
let duplicate = vertex!([1.0, 2.0, 3.0]);
dt.insert(vertex).unwrap();
let result = dt.insert(duplicate);
assert!(
matches!(result, Err(InsertionError::DuplicateCoordinates { .. })),
"insert() should reject duplicate coordinates created via vertex! (before UUID), got: {result:?}"
);
}
#[test]
fn test_add_vertex_duplicate_uuid_rejected() {
let initial_vertices = initial_simplex_vertices_3d();
let mut dt = DelaunayTriangulation::new(&initial_vertices).unwrap();
let vertex1 = vertex!([1.0, 2.0, 3.0]);
let uuid1 = vertex1.uuid();
dt.insert(vertex1).unwrap();
let vertex2 = vertex_with_uuid(Point::new([4.0, 5.0, 6.0]), uuid1, None);
let result = dt.insert(vertex2);
assert!(
matches!(
result,
Err(InsertionError::DuplicateUuid {
entity: EntityKind::Vertex,
..
})
),
"Same UUID with different coordinates should fail with DuplicateUuid"
);
}
#[test]
fn test_add_vertex_increases_counts_and_leaves_tds_valid() {
let initial_vertices = initial_simplex_vertices_3d();
let mut dt = DelaunayTriangulation::new(&initial_vertices).unwrap();
let initial_simplex_count = dt.number_of_simplices();
let new_vertex = vertex!([0.5, 0.5, 0.5]);
dt.insert(new_vertex).unwrap();
assert_eq!(dt.number_of_vertices(), 5);
assert!(
dt.number_of_simplices() >= initial_simplex_count,
"Simplex count should not decrease"
);
assert!(
dt.as_triangulation().tds.is_valid().is_ok(),
"TDS should remain valid"
);
}
#[test]
fn test_add_vertex_is_accessible_by_uuid_and_coordinates() {
let initial_vertices = initial_simplex_vertices_3d();
let mut dt = DelaunayTriangulation::new(&initial_vertices).unwrap();
let vertex = vertex!([1.0, 2.0, 3.0]);
let uuid = vertex.uuid();
dt.insert(vertex).unwrap();
let vertex_key = dt.as_triangulation().tds.vertex_key_from_uuid(&uuid);
assert!(
vertex_key.is_some(),
"Added vertex should be findable by UUID"
);
let stored_vertex = dt
.as_triangulation()
.tds
.vertex(vertex_key.unwrap())
.unwrap();
let coords = *stored_vertex.point().coords();
let expected = [1.0, 2.0, 3.0];
assert!(
coords
.iter()
.zip(expected.iter())
.all(|(a, b)| (a - b).abs() < 1e-10),
"Stored coordinates should match: got {coords:?}, expected {expected:?}"
);
}
#[test]
fn test_remove_vertex_maintains_topology_consistency() {
let vertices = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.5, 1.0]),
vertex!([1.5, 1.0]),
];
let mut dt = DelaunayTriangulation::new(&vertices).unwrap();
let initial_vertices = dt.number_of_vertices();
let initial_simplices = dt.number_of_simplices();
assert_eq!(initial_vertices, 4);
assert!(initial_simplices > 0);
let (vertex_key, vertex_ref) = dt.vertices().next().unwrap();
let vertex_uuid = vertex_ref.uuid();
let simplices_removed = dt.remove_vertex(vertex_key).unwrap();
assert!(
dt.as_triangulation()
.tds
.vertex_key_from_uuid(&vertex_uuid)
.is_none(),
"Vertex should be removed from TDS"
);
assert!(
simplices_removed > 0,
"At least one simplex should have been removed"
);
assert_eq!(
dt.number_of_vertices(),
initial_vertices - 1,
"Vertex count should decrease by 1"
);
assert!(
dt.number_of_simplices() < initial_simplices,
"Simplex count should decrease"
);
for (simplex_key, simplex) in dt.simplices() {
if let Some(neighbors) = simplex.neighbors() {
for (i, neighbor_opt) in neighbors.enumerate() {
if let Some(neighbor_key) = neighbor_opt {
assert!(
dt.as_triangulation()
.tds
.simplices
.contains_key(neighbor_key),
"Simplex {simplex_key:?} has dangling neighbor reference at index {i}: {neighbor_key:?}"
);
}
}
}
}
assert!(
dt.as_triangulation().tds.is_valid().is_ok(),
"TDS should be valid after removing vertex"
);
println!("✓ remove_vertex maintains topology consistency");
}
#[test]
fn test_remove_vertex_nonexistent() {
let vertices = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt = DelaunayTriangulation::new(&vertices).unwrap();
let nonexistent_key = VertexKey::from(KeyData::from_ffi(u64::MAX));
let initial_vertices = dt.number_of_vertices();
let initial_simplices = dt.number_of_simplices();
let simplices_removed = dt.remove_vertex(nonexistent_key).unwrap();
assert_eq!(simplices_removed, 0, "No simplices should be removed");
assert_eq!(
dt.number_of_vertices(),
initial_vertices,
"Vertex count should not change"
);
assert_eq!(
dt.number_of_simplices(),
initial_simplices,
"Simplex count should not change"
);
println!("✓ remove_vertex handles nonexistent vertex correctly");
}
#[test]
fn test_remove_vertex_stale_key_is_idempotent() {
let vertices = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
vertex!([1.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
let vertex_key = dt.vertices().next().unwrap().0;
let simplices_removed = dt.remove_vertex(vertex_key).unwrap();
assert!(simplices_removed > 0);
let vertices_after = dt.number_of_vertices();
let simplices_after = dt.number_of_simplices();
let simplices_removed_again = dt.remove_vertex(vertex_key).unwrap();
assert_eq!(
simplices_removed_again, 0,
"Stale key should remove nothing"
);
assert_eq!(dt.number_of_vertices(), vertices_after);
assert_eq!(dt.number_of_simplices(), simplices_after);
}
#[test]
fn test_remove_vertex_multiple_dimensions() {
{
let vertices_2d = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
vertex!([1.0, 1.0]),
];
let mut dt_2d: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices_2d).unwrap();
let vertex_key = dt_2d.vertices().next().unwrap().0;
let simplices_removed = dt_2d.remove_vertex(vertex_key).unwrap();
assert!(simplices_removed > 0);
assert!(dt_2d.as_triangulation().tds.is_valid().is_ok());
}
{
let vertices_3d = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.2, 0.2, 0.2]),
];
let mut dt_3d: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices_3d).unwrap();
let vertex_key = dt_3d
.vertices()
.find(|(_, vertex)| {
let coords = vertex.point().coords();
coords
.iter()
.zip([0.2, 0.2, 0.2])
.all(|(coord, expected)| (*coord - expected).abs() < 1e-12)
})
.unwrap()
.0;
let simplices_removed = dt_3d.remove_vertex(vertex_key).unwrap();
assert!(simplices_removed > 0);
assert!(dt_3d.as_triangulation().tds.is_valid().is_ok());
}
{
let vertices_4d = [
vertex!([0.0, 0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0, 0.0]),
vertex!([0.0, 0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 0.0, 1.0]),
vertex!([0.2, 0.2, 0.2, 0.2]),
];
let mut dt_4d: DelaunayTriangulation<_, (), (), 4> =
DelaunayTriangulation::new(&vertices_4d).unwrap();
let vertex_key = dt_4d
.vertices()
.find(|(_, vertex)| {
let coords = vertex.point().coords();
coords
.iter()
.zip([0.2, 0.2, 0.2, 0.2])
.all(|(coord, expected)| (*coord - expected).abs() < 1e-12)
})
.unwrap()
.0;
let simplices_removed = dt_4d.remove_vertex(vertex_key).unwrap();
assert!(simplices_removed > 0);
assert!(dt_4d.as_triangulation().tds.is_valid().is_ok());
}
println!("✓ remove_vertex works correctly in multiple dimensions");
}
#[test]
fn test_remove_vertex_no_dangling_references() {
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.2, 0.2, 0.2]),
];
let mut dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
let interior_coords = [0.2, 0.2, 0.2];
let (removed_vertex_key, removed_vertex_uuid) = dt
.vertices()
.find(|(_, v)| {
v.point()
.coords()
.as_slice()
.iter()
.zip(&interior_coords)
.all(|(a, b)| (a - b).abs() < 1e-10)
})
.map(|(k, v)| (k, v.uuid()))
.expect("Interior vertex should exist");
let simplices_removed = dt.remove_vertex(removed_vertex_key).unwrap();
assert!(
simplices_removed > 0,
"Should have removed at least one simplex"
);
for (simplex_key, simplex) in dt.simplices() {
for &vk in simplex.vertices() {
assert_ne!(
vk, removed_vertex_key,
"Simplex {simplex_key:?} still references deleted vertex {removed_vertex_key:?}"
);
}
}
assert!(
dt.as_triangulation()
.tds
.vertex_key_from_uuid(&removed_vertex_uuid)
.is_none(),
"Deleted vertex UUID should not be in mapping"
);
assert!(
dt.as_triangulation()
.tds
.vertex(removed_vertex_key)
.is_none(),
"Deleted vertex key should not exist in storage"
);
for (vertex_key, vertex) in dt.vertices() {
if let Some(incident_simplex_key) = vertex.incident_simplex() {
assert!(
dt.as_triangulation()
.tds
.simplices
.contains_key(incident_simplex_key),
"Vertex {vertex_key:?} has dangling incident_simplex pointer to {incident_simplex_key:?}"
);
let incident_simplex = dt
.as_triangulation()
.tds
.simplex(incident_simplex_key)
.unwrap();
assert!(
incident_simplex.contains_vertex(vertex_key),
"Vertex {vertex_key:?} incident_simplex {incident_simplex_key:?} does not contain the vertex"
);
}
}
assert!(
dt.as_triangulation().tds.is_valid().is_ok(),
"TDS should be valid after vertex removal"
);
println!("✓ remove_vertex leaves no dangling references to deleted vertex");
}
#[test]
fn test_find_simplices_containing_vertex() {
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.5, 0.5, 0.5]), ];
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
let first_simplex_key = dt.simplices().next().unwrap().0;
let some_vertex_key = dt
.as_triangulation()
.tds
.simplex_vertices(first_simplex_key)
.unwrap()[0];
let simplices_with_vertex = dt
.as_triangulation()
.tds
.find_simplices_containing_vertex(some_vertex_key);
assert!(
!simplices_with_vertex.is_empty(),
"Vertex should be in at least one simplex"
);
for &simplex_key in &simplices_with_vertex {
let simplex = dt.as_triangulation().tds.simplex(simplex_key).unwrap();
assert!(
simplex.contains_vertex(some_vertex_key),
"Simplex {simplex_key:?} should contain vertex {some_vertex_key:?}"
);
}
let expected_count = dt
.simplices()
.filter(|(_, simplex)| simplex.contains_vertex(some_vertex_key))
.count();
assert_eq!(
simplices_with_vertex.len(),
expected_count,
"Should find all simplices containing the vertex"
);
let another_vertex_key = dt.vertices().nth(1).map(|(k, _)| k).unwrap();
let simplices_with_another = dt
.as_triangulation()
.tds
.find_simplices_containing_vertex(another_vertex_key);
assert!(
!simplices_with_another.is_empty(),
"Another vertex should also be in at least one simplex"
);
println!(
"✓ find_simplices_containing_vertex correctly identifies all simplices containing a vertex"
);
}
#[test]
fn test_assign_neighbors_errors_on_missing_vertex_key() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![a, b, c], None).unwrap())
.unwrap();
let invalid_vkey = VertexKey::from(KeyData::from_ffi(u64::MAX));
tds.simplex_mut(simplex_key)
.unwrap()
.push_vertex_key(invalid_vkey);
let err = tds.assign_neighbors().unwrap_err();
assert!(matches!(err, TdsError::VertexKeyRetrievalFailed { .. }));
}
#[test]
fn test_assign_neighbors_errors_on_non_manifold_facet_sharing() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds
.insert_vertex_with_mapping(vertex!([0.0, -1.0]))
.unwrap();
let v_e = tds.insert_vertex_with_mapping(vertex!([2.0, 0.0])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
tds.insert_simplex_bypassing_topology_checks_for_test(
Simplex::new(vec![v_a, v_b, v_e], None).unwrap(),
)
.unwrap();
let err = tds.assign_neighbors().unwrap_err();
assert!(matches!(err, TdsError::InconsistentDataStructure { .. }));
}
#[test]
fn test_remove_simplices_by_keys_empty_is_noop() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let gen_before = tds.generation();
assert_eq!(tds.remove_simplices_by_keys(&[]), 0);
assert_eq!(tds.generation(), gen_before);
}
#[test]
fn test_remove_simplices_by_keys_clears_neighbor_pointers() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1 = tds
.insert_simplex_with_mapping(Simplex::new(vec![a, b, c], None).unwrap())
.unwrap();
let simplex2 = tds
.insert_simplex_with_mapping(Simplex::new(vec![b, d, c], None).unwrap())
.unwrap();
tds.assign_neighbors().unwrap();
assert!(
tds.simplex(simplex1)
.unwrap()
.neighbors()
.is_some_and(|mut n| n.any(|neighbor| neighbor.is_some()))
);
let gen_before = tds.generation();
assert_eq!(tds.remove_simplices_by_keys(&[simplex2]), 1);
assert_eq!(tds.generation(), gen_before + 1);
for (_, simplex) in tds.simplices() {
if let Some(neighbors) = simplex.neighbors() {
for neighbor_opt in neighbors {
assert_ne!(neighbor_opt, Some(simplex2));
}
}
}
}
#[test]
fn test_remove_simplices_by_keys_repairs_incident_simplices_for_affected_vertices() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1 = tds
.insert_simplex_with_mapping(Simplex::new(vec![a, b, c], None).unwrap())
.unwrap();
let simplex2 = tds
.insert_simplex_with_mapping(Simplex::new(vec![b, d, c], None).unwrap())
.unwrap();
tds.assign_neighbors().unwrap();
tds.vertex_mut(a)
.unwrap()
.set_incident_simplex(Some(simplex1));
tds.vertex_mut(b)
.unwrap()
.set_incident_simplex(Some(simplex1));
tds.vertex_mut(c)
.unwrap()
.set_incident_simplex(Some(simplex1));
tds.vertex_mut(d)
.unwrap()
.set_incident_simplex(Some(simplex2));
assert_eq!(tds.remove_simplices_by_keys(&[simplex1]), 1);
assert!(tds.vertex(a).unwrap().incident_simplex().is_none());
for vk in [b, c, d] {
let incident = tds
.vertex(vk)
.unwrap()
.incident_simplex()
.expect("vertex should have an incident simplex after repair");
assert!(tds.simplices.contains_key(incident));
let simplex = tds.simplex(incident).unwrap();
assert!(simplex.contains_vertex(vk));
}
assert!(tds.is_valid().is_ok());
let simplex2_ref = tds.simplex(simplex2).unwrap();
if let Some(mut neighbors) = simplex2_ref.neighbors() {
assert!(neighbors.all(|n| n != Some(simplex1)));
}
}
#[test]
fn test_tds_remove_vertex_returns_zero_when_vertex_not_in_mapping() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let missing_key = VertexKey::from(KeyData::from_ffi(u64::MAX));
assert_eq!(tds.remove_vertex(missing_key).unwrap(), 0);
}
#[test]
fn test_remove_isolated_vertex_noop_on_missing_key() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let missing = VertexKey::from(KeyData::from_ffi(u64::MAX));
let gen_before = tds.generation();
tds.remove_isolated_vertex(missing);
assert_eq!(tds.generation(), gen_before, "No mutation expected");
}
#[test]
fn test_remove_isolated_vertex_noop_when_incident_simplex_set() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let vk = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let fake_simplex_key = SimplexKey::from(KeyData::from_ffi(1));
tds.vertex_mut(vk)
.unwrap()
.set_incident_simplex(Some(fake_simplex_key));
let gen_before = tds.generation();
tds.remove_isolated_vertex(vk);
assert_eq!(
tds.generation(),
gen_before,
"Non-isolated vertex should not be removed"
);
assert!(tds.vertex(vk).is_some());
}
#[test]
fn test_remove_isolated_vertex_removes_truly_isolated() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let vk = tds.insert_vertex_with_mapping(vertex!([1.0, 2.0])).unwrap();
let uuid = tds.vertex(vk).unwrap().uuid();
assert!(tds.vertex(vk).unwrap().incident_simplex().is_none());
let gen_before = tds.generation();
tds.remove_isolated_vertex(vk);
assert!(tds.generation() > gen_before);
assert!(tds.vertex(vk).is_none(), "Vertex should be removed");
assert!(
tds.vertex_key_from_uuid(&uuid).is_none(),
"UUID mapping should be removed"
);
}
#[test]
fn test_tds_remove_vertex_repairs_neighbors_and_incident_simplices_incrementally() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let origin_key = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let east_key = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let north_key = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let diagonal_key = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1 = tds
.insert_simplex_with_mapping(
Simplex::new(vec![origin_key, east_key, north_key], None).unwrap(),
)
.unwrap();
let simplex2 = tds
.insert_simplex_with_mapping(
Simplex::new(vec![east_key, diagonal_key, north_key], None).unwrap(),
)
.unwrap();
tds.assign_neighbors().unwrap();
tds.vertex_mut(origin_key)
.unwrap()
.set_incident_simplex(Some(simplex1));
tds.vertex_mut(east_key)
.unwrap()
.set_incident_simplex(Some(simplex1));
tds.vertex_mut(north_key)
.unwrap()
.set_incident_simplex(Some(simplex1));
tds.vertex_mut(diagonal_key)
.unwrap()
.set_incident_simplex(Some(simplex2));
let origin_uuid = tds.vertex(origin_key).unwrap().uuid();
let removed = tds.remove_vertex(origin_key).unwrap();
assert_eq!(removed, 1);
assert!(tds.vertex_key_from_uuid(&origin_uuid).is_none());
assert!(tds.vertex(origin_key).is_none());
assert!(tds.simplices.contains_key(simplex2));
let simplex2_ref = tds.simplex(simplex2).unwrap();
if let Some(mut neighbors) = simplex2_ref.neighbors() {
assert!(neighbors.all(|n| n != Some(simplex1)));
}
for vertex_key in [east_key, north_key, diagonal_key] {
let v = tds.vertex(vertex_key).unwrap();
let Some(incident) = v.incident_simplex() else {
panic!("vertex {vertex_key:?} should have an incident simplex after removal");
};
assert!(tds.simplices.contains_key(incident));
assert!(tds.simplex(incident).unwrap().contains_vertex(vertex_key));
}
}
#[test]
fn test_find_neighbors_by_key_returns_none_buffer_for_missing_simplex() {
let tds: Tds<f64, (), (), 2> = Tds::empty();
let missing = SimplexKey::from(KeyData::from_ffi(u64::MAX));
let neighbors = tds.find_neighbors_by_key(missing);
assert_eq!(neighbors.len(), 3);
assert!(neighbors.iter().all(Option::is_none));
}
#[test]
fn test_set_neighbors_by_key_rejects_non_neighbor_and_wrong_slot() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let v_e = tds.insert_vertex_with_mapping(vertex!([2.0, 2.0])).unwrap();
let simplex1 = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex_far = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_d, v_e], None).unwrap())
.unwrap();
let err = tds
.set_neighbors_by_key(simplex1, &[Some(simplex_far), None, None])
.unwrap_err()
.0;
assert!(matches!(err, TdsError::InvalidNeighbors { .. }));
let simplex2 = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_b, v_a, v_d], None).unwrap())
.unwrap();
let err = tds
.set_neighbors_by_key(simplex1, &[Some(simplex2), None, None])
.unwrap_err()
.0;
assert!(matches!(err, TdsError::InvalidNeighbors { .. }));
}
#[test]
fn test_set_neighbors_by_key_updates_reciprocal_back_reference() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1 = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2 = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
tds.set_neighbors_by_key(simplex1, &[None, None, Some(simplex2)])
.unwrap();
assert_eq!(
tds.simplex(simplex1).unwrap().neighbor_key(2).flatten(),
Some(simplex2)
);
assert_eq!(
tds.simplex(simplex2).unwrap().neighbor_key(2).flatten(),
Some(simplex1)
);
let facet_to_simplices = tds.build_facet_to_simplices_map().unwrap();
tds.validate_neighbors_with_facet_to_simplices_map(&facet_to_simplices)
.unwrap();
}
#[test]
fn test_set_neighbors_by_key_rejects_unpaired_interior_facet() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1 = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v_b, v_a, v_d], None).unwrap())
.unwrap();
tds.assign_neighbors().unwrap();
let err = tds
.set_neighbors_by_key(simplex1, &[None, None, None])
.unwrap_err()
.0;
assert!(matches!(err, TdsError::InvalidNeighbors { .. }));
assert!(tds.is_valid().is_ok());
}
#[test]
fn test_build_simplex_vertex_sets_success() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1 = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2 = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_c, v_d], None).unwrap())
.unwrap();
let map = tds.build_simplex_vertex_sets().unwrap();
assert_eq!(map.len(), 2);
let expected1: VertexKeySet = [v_a, v_b, v_c].into_iter().collect();
let expected2: VertexKeySet = [v_a, v_c, v_d].into_iter().collect();
assert_eq!(map.get(&simplex1), Some(&expected1));
assert_eq!(map.get(&simplex2), Some(&expected2));
}
#[test]
fn test_build_simplex_vertex_sets_errors_on_missing_vertex_key() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let invalid_vkey = VertexKey::from(KeyData::from_ffi(u64::MAX));
tds.simplex_mut(simplex)
.unwrap()
.push_vertex_key(invalid_vkey);
let err = tds.build_simplex_vertex_sets().unwrap_err();
assert!(matches!(err, TdsError::VertexNotFound { .. }));
}
#[test]
fn test_validate_shared_facet_count_ok_for_true_neighbors() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let this_vertices: VertexKeySet = [v_a, v_b, v_c].into_iter().collect();
let neighbor_vertices: VertexKeySet = [v_a, v_b, v_d].into_iter().collect();
assert!(
Tds::validate_shared_facet_count(
simplex1,
simplex2,
&this_vertices,
&neighbor_vertices
)
.is_ok()
);
}
#[test]
fn test_validate_shared_facet_count_errors_for_non_neighbors() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let v_e = tds.insert_vertex_with_mapping(vertex!([2.0, 2.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex_far_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_d, v_e], None).unwrap())
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex_far = tds.simplex(simplex_far_key).unwrap();
let this_vertices: VertexKeySet = [v_a, v_b, v_c].into_iter().collect();
let far_vertices: VertexKeySet = [v_a, v_d, v_e].into_iter().collect();
let simplex1_uuid = simplex1.uuid();
let simplex_far_uuid = simplex_far.uuid();
let err =
Tds::validate_shared_facet_count(simplex1, simplex_far, &this_vertices, &far_vertices)
.unwrap_err();
assert!(matches!(
err,
TdsError::NotNeighbors { simplex1: c1, simplex2: c2 }
if c1 == simplex1_uuid && c2 == simplex_far_uuid
));
}
#[test]
fn test_expected_mirror_facet_index_returns_unique_vertex_index() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_d, v_a, v_b], None).unwrap())
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let this_vertices: VertexKeySet = [v_a, v_b, v_c].into_iter().collect();
let idx = Tds::expected_mirror_facet_index(simplex1, simplex2, &this_vertices).unwrap();
assert_eq!(idx, 0);
}
#[test]
fn test_expected_mirror_facet_index_errors_when_ambiguous() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let v_e = tds.insert_vertex_with_mapping(vertex!([2.0, 2.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_d, v_e], None).unwrap())
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let this_vertices: VertexKeySet = [v_a, v_b, v_c].into_iter().collect();
let err = Tds::expected_mirror_facet_index(simplex1, simplex2, &this_vertices).unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetAmbiguous { .. },
}
));
}
#[test]
fn test_expected_mirror_facet_index_errors_when_duplicate_simplices() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_bypassing_topology_checks_for_test(
Simplex::new(vec![v_a, v_b, v_c], None).unwrap(),
)
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let this_vertices: VertexKeySet = [v_a, v_b, v_c].into_iter().collect();
let err = Tds::expected_mirror_facet_index(simplex1, simplex2, &this_vertices).unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetDuplicateSimplices { .. },
}
));
}
#[test]
fn test_verified_mirror_facet_index_ok() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let this_vertices: VertexKeySet = [v_a, v_b, v_c].into_iter().collect();
let mirror_idx =
Tds::verified_mirror_facet_index(simplex1, 2, simplex2, &this_vertices).unwrap();
assert_eq!(mirror_idx, 2);
}
#[test]
fn test_verified_mirror_facet_index_errors_when_no_shared_facet() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let this_vertices: VertexKeySet = [v_a, v_b, v_c].into_iter().collect();
let err =
Tds::verified_mirror_facet_index(simplex1, 0, simplex2, &this_vertices).unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetMissing { .. },
}
));
}
#[test]
fn test_verified_mirror_facet_index_errors_on_mismatch_with_cross_check() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let this_vertices_wrong: VertexKeySet = [v_a, v_c, v_d].into_iter().collect();
let err = Tds::verified_mirror_facet_index(simplex1, 2, simplex2, &this_vertices_wrong)
.unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetIndexMismatch { .. },
}
));
}
#[test]
fn test_validate_neighbors_errors_on_mirror_facet_index_mismatch() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let origin_key = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let east_key = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let north_key = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let diagonal_key = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(
Simplex::new(vec![origin_key, east_key, north_key], None).unwrap(),
)
.unwrap();
let _simplex2_key = tds
.insert_simplex_with_mapping(
Simplex::new(vec![origin_key, east_key, diagonal_key], None).unwrap(),
)
.unwrap();
tds.assign_neighbors().unwrap();
let mut simplex_vertices = tds.build_simplex_vertex_sets().unwrap();
let corrupted_simplex1_vertices: VertexKeySet =
[origin_key, north_key, diagonal_key].into_iter().collect();
simplex_vertices.insert(simplex1_key, corrupted_simplex1_vertices);
let err = tds
.validate_neighbors_with_precomputed_vertex_sets(&simplex_vertices)
.unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::MirrorFacetIndexMismatch { .. },
}
));
}
#[test]
fn test_validate_shared_facet_vertices_ok() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let this_vertices: VertexKeySet = [v_a, v_b, v_c].into_iter().collect();
let neighbor_vertices: VertexKeySet = [v_a, v_b, v_d].into_iter().collect();
assert!(
Tds::validate_shared_facet_vertices(
simplex1,
2, simplex2,
2, &this_vertices,
&neighbor_vertices,
)
.is_ok()
);
}
#[test]
fn test_validate_shared_facet_vertices_errors_when_mirror_index_wrong() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let this_vertices: VertexKeySet = [v_a, v_b, v_c].into_iter().collect();
let neighbor_vertices: VertexKeySet = [v_a, v_b, v_d].into_iter().collect();
let err = Tds::validate_shared_facet_vertices(
simplex1,
2, simplex2,
0, &this_vertices,
&neighbor_vertices,
)
.unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::SharedFacetMissingVertex { .. },
}
));
}
#[test]
fn test_validate_mutual_neighbor_back_reference_ok() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
tds.assign_neighbors().unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
assert!(
Tds::validate_mutual_neighbor_back_reference(
simplex1_key,
simplex1,
2, simplex2_key,
simplex2,
2, )
.is_ok()
);
}
#[test]
fn test_validate_mutual_neighbor_back_reference_errors_when_neighbor_has_no_neighbors() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let err = Tds::validate_mutual_neighbor_back_reference(
simplex1_key,
simplex1,
2,
simplex2_key,
simplex2,
2,
)
.unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::BackReferenceMismatch { observed: None, .. },
}
));
}
#[test]
fn test_validate_mutual_neighbor_back_reference_errors_when_back_reference_missing() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
tds.assign_neighbors().unwrap();
{
let simplex2_mut = tds.simplex_mut(simplex2_key).unwrap();
let neighbors = simplex2_mut
.neighbor_slots_mut()
.expect("simplex2 should have neighbors after assign_neighbors()");
neighbors[2] = NeighborSlot::Boundary;
}
let simplex1 = tds.simplex(simplex1_key).unwrap();
let simplex2 = tds.simplex(simplex2_key).unwrap();
let err = Tds::validate_mutual_neighbor_back_reference(
simplex1_key,
simplex1,
2,
simplex2_key,
simplex2,
2,
)
.unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::BackReferenceMismatch { observed: None, .. },
}
));
}
#[test]
fn test_orientation_validation_rejects_non_periodic_self_neighbor() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
{
let simplex = tds.simplex_mut(simplex_key).unwrap();
simplex
.set_neighbors_from_keys(vec![Some(simplex_key), None, None])
.unwrap();
}
let simplex = tds.simplex(simplex_key).unwrap();
assert!(!Tds::allows_periodic_self_neighbor(simplex));
let err = tds.validate_coherent_orientation().unwrap_err();
assert!(matches!(
err,
TdsError::OrientationViolation {
simplex1_key,
simplex2_key,
..
} if simplex1_key == simplex_key && simplex2_key == simplex_key
));
assert!(!tds.is_coherently_oriented());
let err = tds.normalize_coherent_orientation().unwrap_err();
assert!(matches!(
err,
TdsError::InconsistentDataStructure { message }
if message.contains("Contradictory orientation constraints")
));
}
#[test]
fn test_orientation_validation_allows_periodic_self_neighbor() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
{
let simplex = tds.simplex_mut(simplex_key).unwrap();
simplex
.set_neighbors_from_keys(vec![Some(simplex_key), None, None])
.unwrap();
simplex
.set_periodic_vertex_offsets(vec![[0, 0], [0, 0], [0, 0]])
.unwrap();
}
let simplex = tds.simplex(simplex_key).unwrap();
assert!(Tds::allows_periodic_self_neighbor(simplex));
assert!(tds.validate_coherent_orientation().is_ok());
assert!(tds.is_coherently_oriented());
assert!(tds.normalize_coherent_orientation().is_ok());
}
#[test]
fn test_orientation_validation_rejects_one_sided_periodic_neighbor() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_d], None).unwrap())
.unwrap();
{
let simplex1 = tds.simplex_mut(simplex1_key).unwrap();
simplex1
.set_neighbors_from_keys(vec![None, None, Some(simplex2_key)])
.unwrap();
simplex1
.set_periodic_vertex_offsets(vec![[0, 0], [0, 0], [0, 0]])
.unwrap();
}
{
let simplex2 = tds.simplex_mut(simplex2_key).unwrap();
simplex2
.set_neighbors_from_keys(vec![None, None, None])
.unwrap();
simplex2
.set_periodic_vertex_offsets(vec![[0, 0], [0, 0], [0, 0]])
.unwrap();
}
let err = tds.validate_coherent_orientation().unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::BackReferenceMismatch { observed: None, .. },
}
));
assert!(!tds.is_coherently_oriented());
let err = tds
.validate_coherent_orientation_for_simplices(&[simplex1_key])
.unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::BackReferenceMismatch { observed: None, .. },
}
));
}
#[test]
fn test_boundary_facet_validation_rejects_unassigned_neighbor_slot() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.assign_neighbors().unwrap();
let facet_to_simplices = tds.build_facet_to_simplices_map().unwrap();
{
let simplex = tds.simplex_mut(simplex_key).unwrap();
simplex.ensure_neighbors_buffer_mut()[1] = NeighborSlot::Unassigned;
}
let err = tds
.validate_neighbor_pointers_match_facet_to_simplices_map(&facet_to_simplices)
.unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::UnassignedNeighborSlot {
simplex_key: key,
facet_index: 1,
..
},
} if key == simplex_key
));
}
#[test]
fn test_boundary_facet_validation_rejects_non_periodic_self_neighbor() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.assign_neighbors().unwrap();
let facet_to_simplices = tds.build_facet_to_simplices_map().unwrap();
{
let simplex = tds.simplex_mut(simplex_key).unwrap();
simplex.ensure_neighbors_buffer_mut()[2] = NeighborSlot::Neighbor(simplex_key);
}
let err = tds
.validate_neighbor_pointers_match_facet_to_simplices_map(&facet_to_simplices)
.unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::BoundaryFacetHasNonPeriodicSelfNeighbor {
simplex_key: key,
facet_index: 2,
..
},
} if key == simplex_key
));
}
#[test]
fn test_orientation_validation_rejects_one_way_neighbor_pointer() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v_a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v_b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v_c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v_d = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_a, v_b, v_c], None).unwrap())
.unwrap();
let simplex2_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v_b, v_a, v_d], None).unwrap())
.unwrap();
tds.assign_neighbors().unwrap();
assert!(tds.validate_coherent_orientation().is_ok());
let mirror_idx = {
let simplex1 = tds.simplex(simplex1_key).unwrap();
let mut neighbors = simplex1
.neighbors()
.expect("simplex1 should have neighbors after assign_neighbors()");
let facet_idx = neighbors
.position(|n| n == Some(simplex2_key))
.expect("simplex1 should reference simplex2");
let simplex2 = tds.simplex(simplex2_key).unwrap();
simplex1
.mirror_facet_index(facet_idx, simplex2)
.expect("adjacent simplices should have a mirror facet")
};
{
let simplex2 = tds.simplex_mut(simplex2_key).unwrap();
let neighbors = simplex2
.neighbor_slots_mut()
.expect("simplex2 should have neighbors after assign_neighbors()");
neighbors[mirror_idx] = NeighborSlot::Boundary;
}
let err = tds.validate_coherent_orientation().unwrap_err();
assert!(matches!(
err,
TdsError::InvalidNeighbors {
reason: NeighborValidationError::BackReferenceMismatch { observed: None, .. },
}
));
assert!(!tds.is_coherently_oriented());
}
#[test]
fn test_local_orientation_validation_checks_neighbors_outside_scope() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([2.0, 2.0])).unwrap();
let v3 = tds.insert_vertex_with_mapping(vertex!([3.0, 3.0])).unwrap();
let simplex1_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
let _ = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v3], None).unwrap())
.unwrap();
tds.assign_neighbors().unwrap();
let err = tds
.validate_coherent_orientation_for_simplices(&[simplex1_key])
.unwrap_err();
assert!(matches!(err, TdsError::OrientationViolation { .. }));
}
#[test]
fn test_local_orientation_validation_errors_on_missing_scope_simplex() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
assert_eq!(tds.remove_simplices_by_keys(&[simplex_key]), 1);
let err = tds
.validate_coherent_orientation_for_simplices(&[simplex_key])
.unwrap_err();
assert!(matches!(
err,
TdsError::SimplexNotFound {
simplex_key: missing_key,
..
} if missing_key == simplex_key
));
}
macro_rules! test_normalize_repairs_incoherent_adjacent_pair {
($name:ident, $dim:literal) => {
#[test]
fn $name() {
let mut tds: Tds<f64, (), (), $dim> = Tds::empty();
let mut vertex_keys = Vec::with_capacity($dim + 2);
let mut seed = 1.0_f64;
for idx in 0..($dim + 2) {
let mut coords = [0.0_f64; $dim];
if idx < $dim {
coords[idx] = 1.0;
} else {
for coord in &mut coords {
*coord = seed;
seed += 1.0;
}
}
vertex_keys.push(tds.insert_vertex_with_mapping(vertex!(coords)).unwrap());
}
let simplex1_vertices: Vec<_> =
vertex_keys.iter().take($dim + 1).copied().collect();
let mut simplex2_vertices: Vec<_> =
vertex_keys.iter().take($dim).copied().collect();
simplex2_vertices.push(vertex_keys[$dim + 1]);
let simplex1: Simplex<f64, (), (), $dim> =
Simplex::new(simplex1_vertices, None).unwrap();
let simplex2: Simplex<f64, (), (), $dim> =
Simplex::new(simplex2_vertices, None).unwrap();
tds.insert_simplex_with_mapping(simplex1).unwrap();
tds.insert_simplex_with_mapping(simplex2).unwrap();
tds.assign_neighbors().unwrap();
let err = tds.validate_coherent_orientation().unwrap_err();
assert!(matches!(err, TdsError::OrientationViolation { .. }));
assert!(!tds.is_coherently_oriented());
tds.normalize_coherent_orientation().unwrap();
assert!(tds.validate_coherent_orientation().is_ok());
assert!(tds.is_coherently_oriented());
}
};
}
test_normalize_repairs_incoherent_adjacent_pair!(
test_normalize_repairs_incoherent_adjacent_pair_2d,
2
);
test_normalize_repairs_incoherent_adjacent_pair!(
test_normalize_repairs_incoherent_adjacent_pair_3d,
3
);
test_normalize_repairs_incoherent_adjacent_pair!(
test_normalize_repairs_incoherent_adjacent_pair_4d,
4
);
test_normalize_repairs_incoherent_adjacent_pair!(
test_normalize_repairs_incoherent_adjacent_pair_5d,
5
);
#[test]
fn test_assign_incident_simplices_clears_incident_simplex_when_no_simplices() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let vkey = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
tds.vertex_mut(vkey)
.unwrap()
.set_incident_simplex(Some(SimplexKey::from(KeyData::from_ffi(u64::MAX))));
assert!(tds.vertex(vkey).unwrap().incident_simplex().is_some());
tds.assign_incident_simplices().unwrap();
assert!(tds.vertex(vkey).unwrap().incident_simplex().is_none());
}
#[test]
fn test_build_facet_to_simplices_map_errors_on_u8_facet_index_overflow() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![a, b, c], None).unwrap())
.unwrap();
{
let simplex = tds.simplex_mut(simplex_key).unwrap();
while simplex.number_of_vertices() <= usize::from(u8::MAX) + 1 {
simplex.push_vertex_key(a);
}
}
let err = tds.build_facet_to_simplices_map().unwrap_err();
assert!(matches!(err, TdsError::IndexOutOfBounds { .. }));
}
#[test]
fn test_validate_vertex_and_simplex_mappings_detect_inconsistencies() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![a, b, c], None).unwrap())
.unwrap();
assert!(tds.validate_vertex_mappings().is_ok());
assert!(tds.validate_simplex_mappings().is_ok());
let uuid_a = tds.vertex(a).unwrap().uuid();
tds.uuid_to_vertex_key.remove(&uuid_a);
assert!(matches!(
tds.validate_vertex_mappings(),
Err(TdsError::MappingInconsistency {
entity: EntityKind::Vertex,
..
})
));
tds.uuid_to_vertex_key.insert(uuid_a, b);
assert!(matches!(
tds.validate_vertex_mappings(),
Err(TdsError::MappingInconsistency {
entity: EntityKind::Vertex,
..
})
));
let uuid_simplex = tds.simplex(simplex_key).unwrap().uuid();
tds.uuid_to_simplex_key.remove(&uuid_simplex);
assert!(matches!(
tds.validate_simplex_mappings(),
Err(TdsError::MappingInconsistency {
entity: EntityKind::Simplex,
..
})
));
}
#[test]
fn test_validate_simplex_vertex_keys_detects_missing_vertices() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let a = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let b = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let c = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![a, b, c], None).unwrap())
.unwrap();
let invalid_vkey = VertexKey::from(KeyData::from_ffi(u64::MAX));
tds.simplex_mut(simplex_key)
.unwrap()
.push_vertex_key(invalid_vkey);
let err = tds.validate_simplex_vertex_keys().unwrap_err();
assert!(matches!(err, TdsError::VertexNotFound { .. }));
let err = tds.is_valid().unwrap_err();
assert!(matches!(err, TdsError::VertexNotFound { .. }));
}
#[test]
fn test_geometric_error_display() {
let deg = GeometricError::DegenerateOrientation {
message: "det=0".to_string(),
};
assert!(deg.to_string().contains("det=0"));
let neg = GeometricError::NegativeOrientation {
message: "det<0".to_string(),
};
assert!(neg.to_string().contains("det<0"));
}
#[test]
fn test_tds_error_new_variant_display() {
let simplex_key = SimplexKey::from(KeyData::from_ffi(1));
let vertex_key = VertexKey::from(KeyData::from_ffi(2));
let err = TdsError::SimplexNotFound {
simplex_key,
context: "test lookup".to_string(),
};
assert!(err.to_string().contains("not found"));
assert!(err.to_string().contains("test lookup"));
let err = TdsError::VertexNotFound {
vertex_key,
context: "test vertex".to_string(),
};
assert!(err.to_string().contains("not found"));
assert!(err.to_string().contains("test vertex"));
let err = TdsError::DimensionMismatch {
expected: 4,
actual: 3,
context: "simplex check".to_string(),
};
let msg = err.to_string();
assert!(msg.contains('4') && msg.contains('3') && msg.contains("simplex check"));
let err = TdsError::IndexOutOfBounds {
index: 10,
bound: 5,
context: "facet index".to_string(),
};
let msg = err.to_string();
assert!(msg.contains("10") && msg.contains('5') && msg.contains("facet index"));
}
#[test]
fn test_tds_error_geometric_variant_wraps_geometric_error() {
let inner = GeometricError::DegenerateOrientation {
message: "test".to_string(),
};
let err = TdsError::Geometric(inner.clone());
assert!(err.to_string().contains("test"));
assert_eq!(TdsError::from(inner.clone()), TdsError::Geometric(inner));
}
#[test]
fn test_tds_mutation_error_accessors() {
let inner = TdsError::InvalidNeighbors {
reason: NeighborValidationError::Other {
message: "test".to_string(),
},
};
let mutation = TdsMutationError::from(inner.clone());
assert_eq!(mutation.as_tds_error(), &inner);
let recovered: TdsError = mutation.into_inner();
assert_eq!(recovered, inner);
}
#[test]
fn test_invariant_error_from_tds_and_triangulation() {
let tds_err = TdsError::InconsistentDataStructure {
message: "test".to_string(),
};
let inv = InvariantError::from(tds_err);
assert!(matches!(inv, InvariantError::Tds(_)));
let tri_err = TriangulationValidationError::EulerCharacteristicMismatch {
computed: 1,
expected: 2,
classification: TopologyClassification::Ball(3),
};
let inv = InvariantError::from(tri_err);
assert!(matches!(inv, InvariantError::Triangulation(_)));
}
#[test]
fn test_invariant_error_from_delaunay_validation_error() {
let dt_err = DelaunayTriangulationValidationError::VerificationFailed {
message: "test".to_string(),
};
let inv = InvariantError::from(dt_err);
assert!(matches!(inv, InvariantError::Delaunay(_)));
}
#[test]
fn test_invariant_error_summary_covers_validation_layers() {
let cases = [
(
InvariantError::from(TdsError::InconsistentDataStructure {
message: "dangling simplex".to_string(),
}),
InvariantErrorSummaryKind::Tds,
InvariantErrorSummaryDetail::Tds(TdsErrorKind::InconsistentDataStructure),
),
(
InvariantError::from(TriangulationValidationError::Disconnected {
simplex_count: 2,
}),
InvariantErrorSummaryKind::Triangulation,
InvariantErrorSummaryDetail::Triangulation(
TriangulationValidationErrorKind::Disconnected,
),
),
(
InvariantError::from(DelaunayTriangulationValidationError::VerificationFailed {
message: "non-Delaunay facet".to_string(),
}),
InvariantErrorSummaryKind::Delaunay,
InvariantErrorSummaryDetail::Delaunay(
DelaunayValidationErrorKind::VerificationFailed,
),
),
];
for (source, expected_kind, expected_detail) in cases {
let expected_message = source.to_string();
let summary = InvariantErrorSummary::from(source);
assert_eq!(summary.kind, expected_kind);
assert_eq!(summary.detail, expected_detail);
assert_eq!(summary.message, expected_message);
}
}
#[test]
fn test_invariant_kind_all_variants_are_distinct() {
let kinds = [
InvariantKind::VertexValidity,
InvariantKind::SimplexValidity,
InvariantKind::SimplexCoordinateUniqueness,
InvariantKind::VertexMappings,
InvariantKind::SimplexMappings,
InvariantKind::SimplexVertexKeys,
InvariantKind::VertexIncidence,
InvariantKind::DuplicateSimplices,
InvariantKind::FacetSharing,
InvariantKind::NeighborConsistency,
InvariantKind::CoherentOrientation,
InvariantKind::Connectedness,
InvariantKind::Topology,
InvariantKind::DelaunayProperty,
];
for (i, &a) in kinds.iter().enumerate() {
assert_eq!(a, a);
for &b in &kinds[i + 1..] {
assert_ne!(a, b);
}
}
}
#[test]
fn test_invariant_violation_stores_kind_and_error() {
let violation = InvariantViolation {
kind: InvariantKind::NeighborConsistency,
error: InvariantError::Tds(TdsError::InvalidNeighbors {
reason: NeighborValidationError::Other {
message: "test".to_string(),
},
}),
};
assert_eq!(violation.kind, InvariantKind::NeighborConsistency);
assert!(matches!(violation.error, InvariantError::Tds(_)));
}
#[test]
fn test_entity_kind_debug_output() {
assert_eq!(format!("{:?}", EntityKind::Vertex), "Vertex");
assert_eq!(format!("{:?}", EntityKind::Simplex), "Simplex");
assert_ne!(EntityKind::Vertex, EntityKind::Simplex);
}
#[test]
fn test_tds_mutation_error_from_round_trips() {
let original = TdsError::SimplexNotFound {
simplex_key: SimplexKey::from(KeyData::from_ffi(42)),
context: "round trip".to_string(),
};
let mutation = TdsMutationError::from(original.clone());
assert_eq!(mutation.to_string(), original.to_string());
let round_tripped: TdsError = mutation.into();
assert_eq!(round_tripped, original);
}
#[test]
fn test_geometric_error_from_into_tds_error() {
let geo = GeometricError::NegativeOrientation {
message: "det<0".to_string(),
};
let tds_err: TdsError = geo.into();
assert!(matches!(
tds_err,
TdsError::Geometric(GeometricError::NegativeOrientation { .. })
));
assert!(tds_err.to_string().contains("det<0"));
}
#[test]
fn test_is_connected_returns_false_for_isolated_simplices() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let a0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let a1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let a2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let b0 = tds
.insert_vertex_with_mapping(vertex!([10.0, 0.0]))
.unwrap();
let b1 = tds
.insert_vertex_with_mapping(vertex!([11.0, 0.0]))
.unwrap();
let b2 = tds
.insert_vertex_with_mapping(vertex!([10.0, 1.0]))
.unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![a0, a1, a2], None).unwrap())
.unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![b0, b1, b2], None).unwrap())
.unwrap();
assert!(
!tds.is_connected(),
"TDS with two isolated simplices (no neighbor wiring) must not be connected"
);
}
#[test]
fn test_serde_round_trip_preserves_tds_structure() {
let verts = initial_simplex_vertices_3d();
let dt = DelaunayTriangulation::new(&verts).unwrap();
let original = dt.tds().clone();
let json = serde_json::to_string(&original).expect("serialize failed");
let deserialized: Tds<f64, (), (), 3> =
serde_json::from_str(&json).expect("deserialize failed");
assert_eq!(
deserialized.number_of_vertices(),
original.number_of_vertices()
);
assert_eq!(
deserialized.number_of_simplices(),
original.number_of_simplices()
);
assert_eq!(deserialized.dim(), original.dim());
assert_eq!(deserialized, original);
assert!(deserialized.is_valid().is_ok());
}
#[test]
fn test_serde_round_trip_multi_simplex_triangulation() {
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.5, 0.5, 0.5]),
];
let dt = DelaunayTriangulation::new(&vertices).unwrap();
let original = dt.tds().clone();
assert!(original.number_of_simplices() > 1);
let json = serde_json::to_string(&original).unwrap();
let deserialized: Tds<f64, (), (), 3> = serde_json::from_str(&json).unwrap();
assert_eq!(deserialized, original);
assert!(deserialized.is_valid().is_ok());
assert!(deserialized.is_connected());
assert!(deserialized.is_coherently_oriented());
}
#[test]
fn test_serde_round_trip_2d() {
let vertices = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
vertex!([1.0, 1.0]),
];
let dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
let original = dt.tds().clone();
let json = serde_json::to_string(&original).unwrap();
let deserialized: Tds<f64, (), (), 2> = serde_json::from_str(&json).unwrap();
assert_eq!(deserialized, original);
assert!(deserialized.is_valid().is_ok());
}
#[test]
fn test_normalize_coherent_orientation_produces_coherent_result() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v3 = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let c0 = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
let c1 = tds
.insert_simplex_with_mapping(Simplex::new(vec![v1, v2, v3], None).unwrap())
.unwrap();
tds.simplex_mut(c0)
.unwrap()
.set_neighbors_from_keys([Some(c1), None, None])
.unwrap();
tds.simplex_mut(c1)
.unwrap()
.set_neighbors_from_keys([None, None, Some(c0)])
.unwrap();
tds.normalize_coherent_orientation().unwrap();
assert!(tds.is_coherently_oriented());
}
#[test]
fn test_generation_counter_bumps_on_topology_modification() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
assert_eq!(tds.generation(), 0);
let _v = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
assert!(tds.generation() > 0);
let gen_before = tds.generation();
tds.mark_topology_modified();
assert!(tds.generation() > gen_before);
}
macro_rules! test_clone_identity_dimensions {
($($dim:expr),+ $(,)?) => {
pastey::paste! {
$(
#[test]
fn [<test_clone_uses_fresh_runtime_identity_ $dim d>]() {
let tds: Tds<f64, (), (), $dim> = Tds::empty();
let cloned = tds.clone();
assert!(
!Arc::ptr_eq(tds.identity(), cloned.identity()),
"ordinary TDS clones must have distinct runtime identities"
);
assert_eq!(tds.generation(), cloned.generation());
}
#[test]
fn [<test_clone_for_rollback_preserves_identity_with_independent_generation_ $dim d>]() {
let mut tds: Tds<f64, (), (), $dim> = Tds::empty();
let _v = tds
.insert_vertex_with_mapping(vertex!([0.0_f64; $dim]))
.unwrap();
let snapshot = tds.clone_for_rollback();
let snapshot_generation = snapshot.generation();
assert!(
Arc::ptr_eq(tds.identity(), snapshot.identity()),
"rollback snapshots should preserve runtime identity"
);
tds.mark_topology_modified();
assert_eq!(
snapshot.generation(),
snapshot_generation,
"rollback snapshots need an independent generation counter"
);
}
)+
}
};
}
test_clone_identity_dimensions!(2, 3, 4, 5);
#[test]
fn test_remove_duplicate_simplices_removes_exact_duplicates() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.insert_simplex_bypassing_topology_checks_for_test(
Simplex::new(vec![v0, v1, v2], None).unwrap(),
)
.unwrap();
assert_eq!(tds.number_of_simplices(), 2);
let generation_before = tds.generation();
let removed = tds.remove_duplicate_simplices().unwrap();
assert_eq!(removed, 1);
assert_eq!(tds.number_of_simplices(), 1);
assert!(tds.generation() > generation_before);
assert!(tds.is_valid().is_ok());
}
#[test]
fn test_remove_duplicate_simplices_noop_when_no_duplicates() {
let verts = initial_simplex_vertices_3d();
let dt = DelaunayTriangulation::new(&verts).unwrap();
let mut tds = dt.tds().clone();
let generation_before = tds.generation();
let removed = tds.remove_duplicate_simplices().unwrap();
assert_eq!(removed, 0);
assert_eq!(tds.generation(), generation_before);
assert!(tds.is_valid().is_ok());
}
#[test]
fn test_remove_duplicate_simplices_rolls_back_when_rebuild_fails() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v3 = tds
.insert_vertex_with_mapping(vertex!([0.0, -1.0]))
.unwrap();
let v4 = tds
.insert_vertex_with_mapping(vertex!([0.5, -0.5]))
.unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.insert_simplex_bypassing_topology_checks_for_test(
Simplex::new(vec![v0, v1, v2], None).unwrap(),
)
.unwrap();
tds.insert_simplex_bypassing_topology_checks_for_test(
Simplex::new(vec![v0, v1, v3], None).unwrap(),
)
.unwrap();
tds.insert_simplex_bypassing_topology_checks_for_test(
Simplex::new(vec![v0, v1, v4], None).unwrap(),
)
.unwrap();
let before = tds.clone();
let generation_before = tds.generation();
let error = tds.remove_duplicate_simplices().unwrap_err();
assert!(matches!(
error.into_inner(),
TdsError::InconsistentDataStructure { .. }
));
assert_eq!(tds.number_of_simplices(), 4);
assert_eq!(tds.generation(), generation_before);
assert_eq!(tds, before);
}
#[test]
fn test_validate_vertex_incidence_detects_dangling_incident_simplex() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let ck = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.assign_incident_simplices().unwrap();
tds.simplices.remove(ck);
let err = tds.validate_vertex_incidence().unwrap_err();
assert!(matches!(err, TdsError::SimplexNotFound { .. }));
}
#[test]
fn test_validate_simplex_coordinate_uniqueness_rejects_duplicate_coords() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
let err = tds.validate_simplex_coordinate_uniqueness().unwrap_err();
assert!(
matches!(err, TdsError::DuplicateCoordinatesInSimplex { .. }),
"Expected DuplicateCoordinatesInSimplex, got {err:?}"
);
}
#[test]
fn test_validate_facet_sharing_rejects_triple_shared_facet() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v3 = tds.insert_vertex_with_mapping(vertex!([0.5, 0.5])).unwrap();
let v4 = tds.insert_vertex_with_mapping(vertex!([0.3, 0.3])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v3], None).unwrap())
.unwrap();
tds.insert_simplex_bypassing_topology_checks_for_test(
Simplex::new(vec![v0, v1, v4], None).unwrap(),
)
.unwrap();
let err = tds.validate_facet_sharing().unwrap_err();
let message = err.to_string();
assert!(
matches!(
&err,
TdsError::FacetSharingViolation {
existing_incident_count: 2,
attempted_incident_count: 3,
max_incident_count: 2,
candidate_facet_index: 2,
..
}
),
"Expected over-shared facet error, got {err:?}"
);
assert!(message.contains("exceeds incident-simplex limit"));
assert!(!message.contains("inserting candidate simplex"));
let err = tds.is_valid().unwrap_err();
assert!(
matches!(err, TdsError::FacetSharingViolation { .. }),
"Expected is_valid to surface facet-sharing violation, got {err:?}"
);
let report = tds.validation_report().unwrap_err();
let facet_violation = report
.violations
.iter()
.find(|violation| violation.kind == InvariantKind::FacetSharing)
.expect("validation_report should include the facet-sharing violation");
assert!(
matches!(
&facet_violation.error,
InvariantError::Tds(TdsError::FacetSharingViolation { .. })
),
"Expected validation_report to preserve structured facet-sharing error, got {:?}",
facet_violation.error
);
}
#[test]
fn test_validate_no_duplicate_simplices_detects_dupes() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.insert_simplex_bypassing_topology_checks_for_test(
Simplex::new(vec![v0, v1, v2], None).unwrap(),
)
.unwrap();
let err = tds.validate_no_duplicate_simplices().unwrap_err();
assert!(matches!(err, TdsError::DuplicateSimplices { .. }));
}
#[test]
fn test_tds_is_valid_passes_for_valid_simplex() {
let verts = initial_simplex_vertices_3d();
let dt = DelaunayTriangulation::new(&verts).unwrap();
assert!(dt.tds().is_valid().is_ok());
assert!(dt.tds().validate().is_ok());
}
#[test]
fn test_tds_partial_eq_different_structures_not_equal() {
let verts_a = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let verts_b = [
vertex!([0.0, 0.0]),
vertex!([2.0, 0.0]),
vertex!([0.0, 2.0]),
];
let dt_a: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&verts_a).unwrap();
let dt_b: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&verts_b).unwrap();
assert_ne!(dt_a.tds(), dt_b.tds());
}
#[test]
fn test_clear_all_neighbors_and_rebuild() {
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.5, 0.5, 0.5]),
];
let dt = DelaunayTriangulation::new(&vertices).unwrap();
let mut tds = dt.tds().clone();
assert!(tds.number_of_simplices() > 1);
let has_any_neighbor = tds.simplices().any(|(_, simplex)| {
simplex
.neighbors()
.is_some_and(|mut nb| nb.any(|neighbor| neighbor.is_some()))
});
assert!(has_any_neighbor);
tds.clear_all_neighbors();
for (_, simplex) in tds.simplices() {
assert!(simplex.neighbors().is_none());
}
}
#[test]
fn test_build_facet_to_simplices_map_basic() {
let verts = initial_simplex_vertices_3d();
let dt = DelaunayTriangulation::new(&verts).unwrap();
let tds = dt.tds();
let facet_map = tds.build_facet_to_simplices_map().unwrap();
assert_eq!(facet_map.len(), 4);
for handles in facet_map.values() {
assert_eq!(handles.len(), 1);
}
}
#[test]
fn test_find_simplices_containing_vertex_by_key() {
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.5, 0.5, 0.5]),
];
let dt = DelaunayTriangulation::new(&vertices).unwrap();
let tds = dt.tds();
for (vk, _) in tds.vertices() {
let simplices = tds.find_simplices_containing_vertex_by_key(vk);
assert!(
!simplices.is_empty(),
"Vertex {vk:?} should be in at least one simplex"
);
}
let stale_key = VertexKey::from(KeyData::from_ffi(0xDEAD));
assert!(
tds.find_simplices_containing_vertex_by_key(stale_key)
.is_empty()
);
}
#[test]
fn test_validation_report_accumulates_violations() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.uuid_to_simplex_key
.insert(Uuid::new_v4(), SimplexKey::from(KeyData::from_ffi(0xBAD)));
let report = tds.validation_report().unwrap_err();
assert!(!report.is_empty());
assert!(
report
.violations
.iter()
.any(|v| v.kind == InvariantKind::SimplexMappings),
"Expected SimplexMappings violation"
);
}
#[test]
fn test_insert_simplex_with_mapping_registers_uuid_mapping() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex = Simplex::new(vec![v0, v1, v2], None).unwrap();
let simplex_uuid = simplex.uuid();
let ck = tds.insert_simplex_with_mapping(simplex).unwrap();
assert_eq!(tds.simplex_key_from_uuid(&simplex_uuid), Some(ck));
assert_eq!(tds.number_of_simplices(), 1);
}
#[test]
fn test_insert_simplex_with_mapping_rejects_missing_vertex() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let stale = VertexKey::from(KeyData::from_ffi(0xDEAD));
let simplex = Simplex::new(vec![v0, v1, stale], None).unwrap();
let err = tds.insert_simplex_with_mapping(simplex).unwrap_err();
assert!(matches!(
err,
TdsConstructionError::ValidationError(TdsError::VertexNotFound { .. })
));
}
#[test]
fn test_insert_simplex_with_mapping_trusted_vertices_rejects_missing_vertex() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let stale = VertexKey::from(KeyData::from_ffi(0xDEAD));
let simplex = Simplex::new(vec![v0, v1, stale], None).unwrap();
let err = tds
.insert_simplex_with_mapping_trusted_vertices(simplex)
.unwrap_err();
assert!(matches!(
err,
TdsConstructionError::ValidationError(TdsError::VertexNotFound { .. })
));
}
#[test]
fn test_insert_simplex_with_mapping_rejects_duplicate_uuid() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let simplex_a = Simplex::new(vec![v0, v1, v2], None).unwrap();
let uuid_a = simplex_a.uuid();
tds.insert_simplex_with_mapping(simplex_a).unwrap();
let mut simplex_b = Simplex::new(vec![v0, v1, v2], None).unwrap();
simplex_b.set_uuid(uuid_a).unwrap();
let err = tds.insert_simplex_with_mapping(simplex_b).unwrap_err();
assert!(matches!(err, TdsConstructionError::DuplicateUuid { .. }));
}
#[test]
fn test_insert_simplex_rejects_candidate_periodic_offset_count_mismatch() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let mut candidate = Simplex::new(vec![v0, v1, v2], None).unwrap();
let candidate_uuid = candidate.uuid();
let generation_before = tds.generation();
candidate.periodic_vertex_offsets = Some(vec![[0_i8, 0_i8], [0_i8, 0_i8]].into());
let err = tds.insert_simplex_with_mapping(candidate).unwrap_err();
assert!(matches!(
err,
TdsConstructionError::ValidationError(TdsError::DimensionMismatch {
expected: 3,
actual: 2,
..
})
));
assert_eq!(tds.number_of_simplices(), 0);
assert_eq!(tds.generation(), generation_before);
assert_eq!(tds.simplex_key_from_uuid(&candidate_uuid), None);
}
#[test]
fn test_insert_simplex_propagates_existing_periodic_facet_key_error() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v3 = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let existing = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.simplex_mut(existing)
.unwrap()
.set_periodic_vertex_offsets(vec![[-128_i8, 0_i8], [127_i8, 0_i8], [0_i8, 0_i8]])
.unwrap();
let candidate = Simplex::new(vec![v0, v1, v3], None).unwrap();
let candidate_uuid = candidate.uuid();
let generation_before = tds.generation();
let err = tds.insert_simplex_with_mapping(candidate).unwrap_err();
assert!(matches!(
err,
TdsConstructionError::ValidationError(TdsError::InconsistentDataStructure {
message
}) if message.contains("Failed to derive periodic facet key")
));
assert_eq!(tds.number_of_simplices(), 1);
assert_eq!(tds.generation(), generation_before);
assert_eq!(tds.simplex_key_from_uuid(&candidate_uuid), None);
}
#[test]
fn test_insert_simplex_with_mapping_rejects_duplicate_simplex_without_mutation() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
let candidate = Simplex::new(vec![v0, v1, v2], None).unwrap();
let candidate_uuid = candidate.uuid();
let generation_before = tds.generation();
let err = tds.insert_simplex_with_mapping(candidate).unwrap_err();
assert!(matches!(
err,
TdsConstructionError::ValidationError(TdsError::DuplicateSimplices { .. })
));
assert_eq!(tds.number_of_simplices(), 1);
assert_eq!(tds.generation(), generation_before);
assert_eq!(tds.simplex_key_from_uuid(&candidate_uuid), None);
}
#[test]
fn test_insert_simplex_with_mapping_rejects_third_incident_facet_without_mutation() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v3 = tds
.insert_vertex_with_mapping(vertex!([0.0, -1.0]))
.unwrap();
let v4 = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v3], None).unwrap())
.unwrap();
let candidate = Simplex::new(vec![v0, v1, v4], None).unwrap();
let candidate_uuid = candidate.uuid();
let generation_before = tds.generation();
let err = tds.insert_simplex_with_mapping(candidate).unwrap_err();
match err {
TdsConstructionError::ValidationError(TdsError::FacetSharingViolation {
existing_incident_count,
attempted_incident_count,
max_incident_count,
candidate_simplex_uuid,
candidate_facet_index,
..
}) => {
assert_eq!(existing_incident_count, 2);
assert_eq!(attempted_incident_count, 3);
assert_eq!(max_incident_count, 2);
assert_eq!(candidate_simplex_uuid, candidate_uuid);
assert_eq!(candidate_facet_index, 2);
}
other => panic!("expected structured facet-sharing violation, got {other:?}"),
}
assert_eq!(tds.number_of_simplices(), 2);
assert_eq!(tds.generation(), generation_before);
assert_eq!(tds.simplex_key_from_uuid(&candidate_uuid), None);
}
#[test]
fn test_removed_simplices_do_not_block_future_simplex_insertions() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v3 = tds
.insert_vertex_with_mapping(vertex!([0.0, -1.0]))
.unwrap();
let v4 = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let removed = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
let second = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v3], None).unwrap())
.unwrap();
assert_eq!(tds.remove_simplices_by_keys(&[removed]), 1);
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.expect("removed duplicate simplex should not block reinsertion");
assert_eq!(tds.remove_simplices_by_keys(&[second]), 1);
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v4], None).unwrap())
.expect("removed incident simplex should not block later facet sharing");
}
#[test]
fn test_simplex_vertices_errors_on_missing_vertex_key() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let ck = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.vertices.remove(v2);
tds.uuid_to_vertex_key.retain(|_, &mut vk| vk != v2);
let err = tds.simplex_vertices(ck).unwrap_err();
assert!(matches!(err, TdsError::VertexNotFound { .. }));
}
#[test]
fn test_validate_vertex_incidence_detects_inconsistent_incident_simplex() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let _ck = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.assign_incident_simplices().unwrap();
let v3 = tds.insert_vertex_with_mapping(vertex!([2.0, 2.0])).unwrap();
let ck2 = tds
.insert_simplex_with_mapping(Simplex::new(vec![v1, v2, v3], None).unwrap())
.unwrap();
tds.vertex_mut(v0).unwrap().set_incident_simplex(Some(ck2));
let err = tds.validate_vertex_incidence().unwrap_err();
assert!(matches!(err, TdsError::InconsistentDataStructure { .. }));
}
#[test]
fn test_validate_vertex_incidence_detects_dangling_simplex_key() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.assign_incident_simplices().unwrap();
let dangling = SimplexKey::from(KeyData::from_ffi(0xDEAD));
tds.vertex_mut(v0)
.unwrap()
.set_incident_simplex(Some(dangling));
let err = tds.validate_vertex_incidence().unwrap_err();
assert!(matches!(err, TdsError::SimplexNotFound { .. }));
}
#[test]
fn test_find_simplices_containing_vertex_fallback_when_no_incident_simplex() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
let simplices = tds.find_simplices_containing_vertex_by_key(v0);
assert_eq!(simplices.len(), 1);
}
#[test]
fn test_find_simplices_containing_vertex_falls_back_on_unassigned_neighbor_slot() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v3 = tds
.insert_vertex_with_mapping(vertex!([-1.0, 1.0]))
.unwrap();
let first_simplex = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
let second_simplex = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v2, v3], None).unwrap())
.unwrap();
tds.assign_neighbors().unwrap();
tds.assign_incident_simplices().unwrap();
tds.vertex_mut(v0)
.unwrap()
.set_incident_simplex(Some(first_simplex));
{
let simplex = tds.simplex_mut(first_simplex).unwrap();
simplex.ensure_neighbors_buffer_mut()[0] = NeighborSlot::Unassigned;
}
let simplices = tds.find_simplices_containing_vertex_by_key(v0);
assert_eq!(simplices.len(), 2);
assert!(simplices.contains(&first_simplex));
assert!(simplices.contains(&second_simplex));
}
#[test]
fn test_remove_simplices_by_keys_batch_repairs_incidence_and_neighbors() {
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.5, 0.5, 0.5]),
];
let dt = DelaunayTriangulation::new(&vertices).unwrap();
let mut tds = dt.tds().clone();
assert!(tds.number_of_simplices() > 1);
let first_ck = tds.simplex_keys().next().unwrap();
let removed = tds.remove_simplices_by_keys(&[first_ck]);
assert_eq!(removed, 1);
for (vk, v) in tds.vertices() {
if let Some(ic) = v.incident_simplex() {
assert!(
tds.contains_simplex(ic),
"Vertex {vk:?} has dangling incident_simplex after batch removal"
);
}
}
for (_, simplex) in tds.simplices() {
if let Some(neighbors) = simplex.neighbors() {
for nk in neighbors.flatten() {
assert_ne!(nk, first_ck, "Dangling neighbor pointer to removed simplex");
}
}
}
}
#[test]
fn test_assign_incident_simplices_errors_on_dangling_vertex_key() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let _ck = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.vertices.remove(v2);
tds.uuid_to_vertex_key.retain(|_, &mut vk| vk != v2);
let err = tds.assign_incident_simplices().unwrap_err();
assert!(matches!(
err.as_tds_error(),
TdsError::VertexNotFound { .. }
));
}
#[test]
fn test_normalize_coherent_orientation_handles_single_simplex() {
let verts = initial_simplex_vertices_3d();
let dt = DelaunayTriangulation::new(&verts).unwrap();
let mut tds = dt.tds().clone();
assert_eq!(tds.number_of_simplices(), 1);
assert!(tds.normalize_coherent_orientation().is_ok());
}
#[test]
fn test_normalize_coherent_orientation_multi_simplex() {
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.5, 0.5, 0.5]),
];
let dt = DelaunayTriangulation::new(&vertices).unwrap();
let mut tds = dt.tds().clone();
assert!(tds.number_of_simplices() > 1);
assert!(tds.normalize_coherent_orientation().is_ok());
}
#[test]
fn test_validate_simplex_coordinate_uniqueness_passes_for_distinct_coords() {
let verts = initial_simplex_vertices_3d();
let dt = DelaunayTriangulation::new(&verts).unwrap();
let tds = dt.tds();
assert!(tds.validate_simplex_coordinate_uniqueness().is_ok());
}
#[test]
fn test_mark_topology_modified_bumps_generation() {
let tds: Tds<f64, (), (), 2> = Tds::empty();
let gen_before = tds.generation();
tds.mark_topology_modified();
assert_eq!(tds.generation(), gen_before + 1);
}
#[test]
fn test_remove_duplicate_simplices_removes_actual_duplicates() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
tds.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.insert_simplex_bypassing_topology_checks_for_test(
Simplex::new(vec![v0, v1, v2], None).unwrap(),
)
.unwrap();
assert_eq!(tds.number_of_simplices(), 2);
let generation_before = tds.generation();
let removed = tds.remove_duplicate_simplices().unwrap();
assert_eq!(removed, 1);
assert_eq!(tds.number_of_simplices(), 1);
assert!(tds.generation() > generation_before);
assert!(tds.is_valid().is_ok());
}
#[test]
fn test_remove_simplices_by_keys_returns_zero_for_missing() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let stale = SimplexKey::from(KeyData::from_ffi(0xDEAD));
assert_eq!(tds.remove_simplices_by_keys(&[stale]), 0);
}
#[test]
fn test_remove_simplices_by_keys_repairs_local_topology() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let v3 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let removed_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
let surviving_key = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v2, v3], None).unwrap())
.unwrap();
tds.construction_state = TriangulationConstructionState::Constructed;
tds.assign_neighbors().unwrap();
tds.assign_incident_simplices().unwrap();
assert!(
tds.simplices
.get(surviving_key)
.unwrap()
.neighbors()
.unwrap()
.any(|neighbor| neighbor == Some(removed_key))
);
let removed_uuid = tds.simplices.get(removed_key).unwrap().uuid();
let removed_vertices = tds.simplices.get(removed_key).unwrap().vertices().to_vec();
assert_eq!(tds.remove_simplices_by_keys(&[removed_key]), 1);
assert_eq!(removed_vertices, vec![v0, v1, v2]);
assert!(!tds.simplices.contains_key(removed_key));
assert!(tds.simplices.contains_key(surviving_key));
assert!(!tds.uuid_to_simplex_key.contains_key(&removed_uuid));
if let Some(mut neighbors) = tds.simplices.get(surviving_key).unwrap().neighbors() {
assert!(neighbors.all(|neighbor| neighbor != Some(removed_key)));
}
assert_ne!(
tds.vertices.get(v0).unwrap().incident_simplex(),
Some(removed_key)
);
assert_ne!(
tds.vertices.get(v1).unwrap().incident_simplex(),
Some(removed_key)
);
assert_ne!(
tds.vertices.get(v2).unwrap().incident_simplex(),
Some(removed_key)
);
assert_eq!(
tds.vertices.get(v0).unwrap().incident_simplex(),
Some(surviving_key)
);
assert_eq!(
tds.vertices.get(v2).unwrap().incident_simplex(),
Some(surviving_key)
);
}
#[test]
fn test_validate_neighbor_topology_rejects_wrong_length() {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let ck = tds
.insert_simplex_with_mapping(Simplex::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
let err = tds
.validate_neighbor_topology(ck, &[None, None])
.unwrap_err();
assert!(matches!(err, TdsError::InvalidNeighbors { .. }));
}
#[test]
fn test_set_vertex_data_replaces_existing() {
let vertices: [Vertex<f64, i32, 2>; 3] = [
vertex!([0.0, 0.0], 10i32),
vertex!([1.0, 0.0], 20),
vertex!([0.0, 1.0], 30),
];
let dt = DelaunayTriangulationBuilder::new(&vertices)
.build::<()>()
.unwrap();
let mut tds = dt.tds().clone();
let key = tds.vertex_keys().next().unwrap();
let prev = tds.set_vertex_data(key, Some(99));
assert!(prev.unwrap().is_some()); assert_eq!(tds.vertex(key).unwrap().data, Some(99));
}
#[test]
fn test_set_vertex_data_on_no_data_vertex() {
let vertices = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt = DelaunayTriangulation::new(&vertices).unwrap();
let mut tds = dt.tds().clone();
let key = tds.vertex_keys().next().unwrap();
let prev = tds.set_vertex_data(key, Some(()));
assert_eq!(prev, Some(None));
assert_eq!(tds.vertex(key).unwrap().data, Some(()));
}
#[test]
fn test_set_vertex_data_invalid_key_returns_none() {
let mut tds: Tds<f64, i32, (), 2> = Tds::empty();
let stale = VertexKey::from(KeyData::from_ffi(0xDEAD));
assert!(tds.set_vertex_data(stale, Some(1)).is_none());
}
#[test]
fn test_set_simplex_data_on_empty_simplex() {
let vertices = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt = DelaunayTriangulationBuilder::new(&vertices)
.build::<i32>()
.unwrap();
let mut tds = dt.tds().clone();
let key = tds.simplex_keys().next().unwrap();
let prev = tds.set_simplex_data(key, Some(42));
assert_eq!(prev, Some(None)); assert_eq!(tds.simplex(key).unwrap().data, Some(42));
}
#[test]
fn test_set_simplex_data_replaces_existing() {
let vertices = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt = DelaunayTriangulationBuilder::new(&vertices)
.build::<i32>()
.unwrap();
let mut tds = dt.tds().clone();
let key = tds.simplex_keys().next().unwrap();
tds.set_simplex_data(key, Some(1));
let prev = tds.set_simplex_data(key, Some(2));
assert_eq!(prev, Some(Some(1)));
assert_eq!(tds.simplex(key).unwrap().data, Some(2));
}
#[test]
fn test_set_simplex_data_invalid_key_returns_none() {
let mut tds: Tds<f64, (), i32, 2> = Tds::empty();
let stale = SimplexKey::from(KeyData::from_ffi(0xDEAD));
assert!(tds.set_simplex_data(stale, Some(1)).is_none());
}
#[test]
fn test_set_vertex_data_preserves_triangulation_validity() {
let vertices: [Vertex<f64, i32, 2>; 3] = [
vertex!([0.0, 0.0], 1i32),
vertex!([1.0, 0.0], 2),
vertex!([0.0, 1.0], 3),
];
let mut dt = DelaunayTriangulationBuilder::new(&vertices)
.build::<()>()
.unwrap();
let keys: Vec<_> = dt.vertices().map(|(k, _)| k).collect();
for (key, i) in keys.iter().zip(0i32..) {
dt.set_vertex_data(*key, Some(i * 100));
}
assert!(dt.validate().is_ok());
for (key, i) in keys.iter().zip(0i32..) {
let v = dt.tds().vertex(*key).unwrap();
assert_eq!(v.data, Some(i * 100));
}
}
#[test]
fn test_set_simplex_data_preserves_triangulation_validity() {
let vertices = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.5, 1.0]),
vertex!([1.5, 0.5]),
];
let mut dt = DelaunayTriangulationBuilder::new(&vertices)
.build::<i32>()
.unwrap();
assert!(dt.number_of_simplices() > 1);
let keys: Vec<_> = dt.simplices().map(|(k, _)| k).collect();
for (key, i) in keys.iter().zip(0i32..) {
dt.set_simplex_data(*key, Some(i));
}
assert!(dt.validate().is_ok());
for (key, i) in keys.iter().zip(0i32..) {
let c = dt.tds().simplex(*key).unwrap();
assert_eq!(c.data, Some(i));
}
}
#[test]
fn test_set_vertex_data_via_delaunay_wrapper() {
let vertices: [Vertex<f64, i32, 2>; 3] = [
vertex!([0.0, 0.0], 10i32),
vertex!([1.0, 0.0], 20),
vertex!([0.0, 1.0], 30),
];
let mut dt = DelaunayTriangulationBuilder::new(&vertices)
.build::<()>()
.unwrap();
let key = dt.vertices().next().unwrap().0;
let prev = dt.set_vertex_data(key, Some(99));
assert!(prev.unwrap().is_some());
assert_eq!(dt.tds().vertex(key).unwrap().data, Some(99));
let prev = dt.set_vertex_data(key, None);
assert_eq!(prev, Some(Some(99)));
assert_eq!(dt.tds().vertex(key).unwrap().data, None);
}
#[test]
fn test_set_simplex_data_via_delaunay_wrapper() {
let vertices = [
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt = DelaunayTriangulationBuilder::new(&vertices)
.build::<i32>()
.unwrap();
let key = dt.simplices().next().unwrap().0;
let prev = dt.set_simplex_data(key, Some(42));
assert_eq!(prev, Some(None));
assert_eq!(dt.tds().simplex(key).unwrap().data, Some(42));
let prev = dt.set_simplex_data(key, None);
assert_eq!(prev, Some(Some(42)));
assert_eq!(dt.tds().simplex(key).unwrap().data, None);
}
#[test]
fn test_set_data_via_dt_does_not_invalidate_locate_hint() {
let vertices: [Vertex<f64, i32, 2>; 3] = [
vertex!([0.0, 0.0], 0i32),
vertex!([1.0, 0.0], 0),
vertex!([0.0, 1.0], 0),
];
let mut dt = DelaunayTriangulationBuilder::new(&vertices)
.build::<()>()
.unwrap();
let extra = vertex!([0.25, 0.25], 0i32);
dt.insert(extra).unwrap();
let key = dt.vertices().next().unwrap().0;
let prev = dt.set_vertex_data(key, Some(999));
assert!(prev.is_some(), "set_vertex_data should find the key");
assert_eq!(
dt.tds().vertex(key).unwrap().data,
Some(999),
"stored value should reflect the mutation"
);
let another = vertex!([0.75, 0.1], 0i32);
assert!(dt.insert(another).is_ok());
assert!(dt.validate().is_ok());
}
}