rgeometry 0.12.0

High-Level Computational Geometry
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

use crate::algorithms::convex_hull::graham_scan::convex_hull;
use crate::data::{Point, PointLocation, Polygon};
use crate::{Error, PolygonScalar, TotalOrd};

/// Creates a star-shaped polygon by sorting vertices around a center point.
///
/// A star-shaped polygon is one where all points on the boundary are visible
/// from the center point. This function creates such a polygon by sorting
/// the vertices counter-clockwise around the given center point.
///
/// # Arguments
///
/// * `vertices` - The vertices of the polygon (at least 3 required)
/// * `point` - The center point around which vertices are sorted
///
/// # Returns
///
/// Returns `Ok(polygon)` if a valid star polygon can be created, or an error if:
/// - There are fewer than 3 vertices
/// - The center point is outside the convex hull of the vertices
/// - All vertices are collinear
///
/// # Example
///
/// ```rust
/// use rgeometry::algorithms::polygonization::new_star_polygon;
/// use rgeometry::data::Point;
///
/// let vertices = vec![
///   Point::new([0, 0]),
///   Point::new([4, 0]),
///   Point::new([4, 4]),
///   Point::new([0, 4]),
/// ];
/// let center = Point::new([2, 2]);
/// let polygon = new_star_polygon(vertices, &center).unwrap();
/// ```
pub fn new_star_polygon<T>(
  mut vertices: Vec<Point<T>>,
  point: &Point<T>,
) -> Result<Polygon<T>, Error>
where
  T: PolygonScalar + TotalOrd,
{
  // Validate that the center point is inside the convex hull of the vertices
  let hull = convex_hull(vertices.clone())?;
  if hull.locate(point) == PointLocation::Outside {
    return Err(Error::ConvexViolation);
  }

  vertices.sort_by(|a, b| point.ccw_cmp_around(a, b));
  Polygon::new(vertices)
}

#[cfg(test)]
mod tests {
  use super::*;
  use proptest::prelude::*;
  use test_strategy::proptest;

  #[proptest]
  fn star_polygon_is_valid(
    #[strategy(proptest::collection::vec(any::<Point<i8, 2>>(), 3..20))] pts: Vec<Point<i8, 2>>,
  ) {
    // Use the centroid as the center point (always inside convex hull if non-degenerate)
    let sum_x: i32 = pts.iter().map(|p| *p.x_coord() as i32).sum();
    let sum_y: i32 = pts.iter().map(|p| *p.y_coord() as i32).sum();
    let n = pts.len() as i32;
    let center = Point::new([(sum_x / n) as i8, (sum_y / n) as i8]);

    if let Ok(p) = new_star_polygon(pts, &center) {
      prop_assert!(p.validate().is_ok());
    }
  }

  #[test]
  fn center_outside_convex_hull_fails() {
    let vertices = vec![
      Point::new([0, 0]),
      Point::new([4, 0]),
      Point::new([4, 4]),
      Point::new([0, 4]),
    ];
    let center = Point::new([10, 10]); // Outside the square
    let result = new_star_polygon(vertices, &center);
    assert!(matches!(result, Err(Error::ConvexViolation)));
  }

  #[test]
  fn center_inside_convex_hull_succeeds() {
    let vertices = vec![
      Point::new([0, 0]),
      Point::new([4, 0]),
      Point::new([4, 4]),
      Point::new([0, 4]),
    ];
    let center = Point::new([2, 2]); // Inside the square
    let result = new_star_polygon(vertices, &center);
    assert!(result.is_ok());
  }
}