aboutsummaryrefslogtreecommitdiff
path: root/src/math
diff options
context:
space:
mode:
Diffstat (limited to 'src/math')
-rw-r--r--src/math/polygon/mod.rs133
-rw-r--r--src/math/polygon/polygon_graph.rs20
-rw-r--r--src/math/polygon/triangulate.rs3
3 files changed, 122 insertions, 34 deletions
diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs
index 90d46bb..e1f15c5 100644
--- a/src/math/polygon/mod.rs
+++ b/src/math/polygon/mod.rs
@@ -12,6 +12,21 @@ use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar};
use num_traits::Zero;
use serde::{Deserialize, Serialize};
use std::ops::Neg;
+use thiserror::Error;
+
+/// Describes errors that can happen when handling polygons, especially on creation.
+#[derive(Debug, Error)]
+pub enum PolygonError<T: Scalar + Copy> {
+ /// Since the polygon is not allowed to be complex, self intersection is an error.
+ #[error("the polygon intersects with itself with edges `{0:?}` and `{1:?}`")]
+ SelfIntersect(LineSegment<T>, LineSegment<T>),
+ #[error("polygons need at least 3 vertices to be valid, `{0}` where provided")]
+ TooFewVertices(usize),
+ #[error("vertex `{0:?}` with corner id `{1}` is or would be in the polygon twice")]
+ VertexDoubling(Vec2<T>, usize),
+ #[error("line `{0:?}` is not a polygon edge")]
+ EdgeNotFound(LineSegment<T>),
+}
#[derive(Clone, Debug, Deserialize, Serialize)]
// TODO: Support polygons with holes
@@ -22,17 +37,29 @@ pub struct Polygon<T: Scalar + Copy> {
impl<T: Scalar + Copy> Polygon<T> {
/// Create a new polygon from the provided corners. If the corners are right-turning, they will
/// be reversed to be left-turning.
- ///
- /// # Panics
- /// If one tries to create a polygon with less than three corners, it will fail. Zero area
- /// polygons however are allowed at the moment.
- pub fn new(corners: Vec<Vec2<T>>) -> Self
+ /// Checks if the corners make a valid polygon before creating it. If the check fails, an error
+ /// will be returned.
+ pub fn new(corners: Vec<Vec2<T>>) -> Result<Self, PolygonError<T>>
where
T: RealField,
{
- if corners.len() < 3 {
- panic!("Cannot create polygon with less than three corners.");
- }
+ Self::check_validity(&corners)?;
+
+ let corners = if combined_angle(&corners) > T::zero() {
+ corners
+ } else {
+ corners.into_iter().rev().collect()
+ };
+
+ Ok(Self { corners })
+ }
+
+ /// Like new, but does not perform any validity checks, so be careful when using this function.
+ pub fn new_unchecked(corners: Vec<Vec2<T>>) -> Self
+ where
+ T: RealField,
+ {
+ assert!(Polygon::check_validity(&corners).is_ok());
let corners = if combined_angle(&corners) > T::zero() {
corners
@@ -43,22 +70,67 @@ impl<T: Scalar + Copy> Polygon<T> {
Self { corners }
}
+ /// Checks if a set of corners can be made into a polygon or not. Returns Ok if they can, or
+ /// the reason they cannot in form of a PolygonError.
+ pub fn check_validity(corners: &[Vec2<T>]) -> Result<(), PolygonError<T>>
+ where
+ T: RealField,
+ {
+ if corners.len() < 3 {
+ return Err(PolygonError::TooFewVertices(corners.len()));
+ }
+
+ // Check that all vertices are in the slice only once.
+ for i in 0..corners.len() {
+ for j in (i + 1)..corners.len() {
+ if corners[i] == corners[j] {
+ return Err(PolygonError::VertexDoubling(corners[i], i));
+ }
+ }
+ }
+
+ // Check that no edges cross paths, except the edges that are right next to each other,
+ // which must intersect with each other on the common vertex.
+ if corners.len() > 3 {
+ for i in 0..corners.len() - 2 {
+ let line_i = LineSegment::new(corners[i], corners[i + 1]);
+ let end_j = if i == 0 {
+ corners.len() - 1
+ } else {
+ corners.len()
+ };
+ for j in (i + 2)..end_j {
+ let next_j = (j + 1) % corners.len();
+ let line_j = LineSegment::new(corners[j], corners[next_j]);
+
+ if LineSegment::intersect(&line_i, &line_j) {
+ return Err(PolygonError::SelfIntersect(line_i, line_j));
+ }
+ }
+ }
+ }
+
+ Ok(())
+ }
+
/// Add a vertex as a corner between the two provided neighbours. The direction of the
/// neighbours is not relevant. The edge between the two will be replaced with two edges to the
- /// new corner from each of the neighbours respectively.
- /// If there already is a point `corner` in the polygon, this function will fail and return
- /// `false`. It will do nothing and return `false` if the provided neighbours are not actually
- /// neighbours in the polygon already.
- /// Otherwise it will perform the addition and return `true`.
+ /// new corner from each of the neighbours respectively. On success, the method returns the
+ /// position of the corner in the corners list.
+ ///
+ /// # Failures
+ /// If the corner is already present in the polygon's vertex list, the method will throw a
+ /// VertexDoubling-Error. If no matching neighbour-pair can be found, an EdgeNotFound-Error
+ /// will be thrown.
pub fn add_corner(
&mut self,
corner: Vec2<T>,
neighbour1: &Vec2<T>,
neighbour2: &Vec2<T>,
- ) -> bool {
+ ) -> Result<usize, PolygonError<T>> {
// Check that the corners do not contain the corner vector already.
- if self.corners.iter().find(|&c| *c == corner).is_some() {
- return false;
+ if let Some(pos) = self.corners.iter().position(|&c| c == corner) {
+ return Err(PolygonError::VertexDoubling(corner, pos));
}
for i in 0..self.corners.len() {
@@ -66,16 +138,19 @@ impl<T: Scalar + Copy> Polygon<T> {
if self.corners[i] == *neighbour1 && self.corners[next] == *neighbour2 {
self.corners.insert(next, corner);
- return true;
+ return Ok(next);
}
if self.corners[i] == *neighbour2 && self.corners[next] == *neighbour1 {
self.corners.insert(next, corner);
- return true;
+ return Ok(next);
}
}
// No matching neighbour pair can be found.
- false
+ Err(PolygonError::EdgeNotFound(LineSegment::new(
+ *neighbour1,
+ *neighbour2,
+ )))
}
/// Get the corners of this polygon in left-turning direction.
@@ -307,8 +382,6 @@ fn combined_angle<T: Scalar + Copy + RealField>(points: &Vec<Vec2<T>>) -> T {
combined_angle += angle - T::pi();
}
- println!("Calculated combined angle: {} Pi", combined_angle / T::pi());
-
combined_angle
}
@@ -317,6 +390,12 @@ mod test {
use super::*;
#[test]
+ fn check_validity() {
+ Polygon::check_validity(&[Vec2::new(0., 0.), Vec2::new(1., 0.), Vec2::new(0., 1.)])
+ .expect("Simple triangle does not pass validity check");
+ }
+
+ #[test]
fn polygon_contains() {
let polygon = Polygon::new(vec![
Vec2::new(0., 0.),
@@ -326,7 +405,8 @@ mod test {
Vec2::new(3., 1.5),
Vec2::new(2., 0.),
Vec2::new(1., 1.),
- ]);
+ ])
+ .unwrap();
assert!(!polygon.contains_point(&Vec2::new(1., -2.)));
assert!(!polygon.contains_point(&Vec2::new(-1., 0.5)));
@@ -351,7 +431,8 @@ mod test {
Vec2::new(2., 0.5),
Vec2::new(4., 2.),
Vec2::new(4., 0.),
- ]);
+ ])
+ .unwrap();
/* NOTE: From now on, inside means inside the polygon, but might be on an edge or on a
* corner point, really inside means inside and not on an edge.
@@ -403,14 +484,16 @@ mod test {
Vec2::new(0.5, 1.5),
Vec2::new(1., 0.),
Vec2::new(-0.5, 1.),
- ]);
+ ])
+ .unwrap();
let second = Polygon::new(vec![
Vec2::new(0., 0.),
Vec2::new(-2., 2.),
Vec2::new(3., 2.),
Vec2::new(1.5, 0.),
- ]);
+ ])
+ .unwrap();
let union = first.unite(second);
assert_eq!(union.len(), 1);
diff --git a/src/math/polygon/polygon_graph.rs b/src/math/polygon/polygon_graph.rs
index 6fdb6cd..5a730b0 100644
--- a/src/math/polygon/polygon_graph.rs
+++ b/src/math/polygon/polygon_graph.rs
@@ -291,7 +291,7 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
.expect("Failure to find node that should be inside list.")];
}
- Polygon::new(bounding_corners)
+ Polygon::new(bounding_corners).expect("PolygonGraph produced invalid polygon")
}
}
@@ -311,7 +311,7 @@ mod test {
let b = Vec2::new(0., 1.);
let c = Vec2::new(0.5, 1.);
- let triangle = Polygon::new(vec![a, b, c]);
+ let triangle = Polygon::new(vec![a, b, c]).unwrap();
let graph = PolygonGraph::from_polygon(&triangle);
assert_eq!(graph.num_edges(), 3);
@@ -333,9 +333,9 @@ mod test {
let bot_left = Vec2::new(0., 1.);
let bot_right = Vec2::new(1., 1.);
- let triangle = Polygon::new(vec![top_left, bot_right, top_right]);
+ let triangle = Polygon::new(vec![top_left, bot_right, top_right]).unwrap();
- let square = Polygon::new(vec![bot_left, bot_right, top_right, top_left]);
+ let square = Polygon::new(vec![bot_left, bot_right, top_right, top_left]).unwrap();
let mut graph = PolygonGraph::new();
graph.add_all(&triangle);
@@ -368,7 +368,8 @@ mod test {
Vec2::new(2., 2.),
Vec2::new(3., 1.),
Vec2::new(2., 0.),
- ]);
+ ])
+ .unwrap();
let second = Polygon::new(vec![
Vec2::new(2.5, -0.5),
@@ -376,7 +377,8 @@ mod test {
Vec2::new(2., 2.),
Vec2::new(2., 0.5),
Vec2::new(2.5, 0.),
- ]);
+ ])
+ .unwrap();
let mut graph = PolygonGraph::from_polygon(&first);
graph.add_all(&second);
@@ -406,7 +408,8 @@ mod test {
Vec2::new(2., 2.),
Vec2::new(3., 1.),
Vec2::new(2., 0.),
- ]);
+ ])
+ .unwrap();
let second = Polygon::new(vec![
Vec2::new(2.5, -0.5),
@@ -414,7 +417,8 @@ mod test {
Vec2::new(2., 2.),
Vec2::new(2., 0.5),
Vec2::new(2.5, 0.),
- ]);
+ ])
+ .unwrap();
let mut graph = PolygonGraph::from_polygon(&first);
graph.add_all(&second);
diff --git a/src/math/polygon/triangulate.rs b/src/math/polygon/triangulate.rs
index 78dfa03..4c7d952 100644
--- a/src/math/polygon/triangulate.rs
+++ b/src/math/polygon/triangulate.rs
@@ -136,7 +136,8 @@ mod test {
Vec2::new(2., 0.5),
Vec2::new(4., 2.),
Vec2::new(4., 0.),
- ]);
+ ])
+ .unwrap();
let triangles = super::triangulate(polygon);
generated by cgit v1.2.3-70-g09d2 (git 2.51.1) at 2025-12-06 11:19:42 +0000