rgeometry/data/
triangle.rs

1use super::{Point, PointLocation};
2use crate::{Error, Orientation, PolygonScalar, TotalOrd};
3use claims::debug_assert_ok;
4use num_traits::*;
5use rand::distributions::uniform::SampleUniform;
6use rand::Rng;
7
8// FIXME: Support n-dimensional triangles?
9#[derive(Debug, Clone)]
10pub struct Triangle<T>([Point<T, 2>; 3]);
11
12impl<T> Triangle<T>
13where
14  T: PolygonScalar,
15{
16  pub fn new(pts: [Point<T, 2>; 3]) -> Result<Triangle<T>, Error> {
17    let triangle = Triangle(pts);
18    triangle.validate()?;
19    Ok(triangle)
20  }
21
22  pub fn new_ccw(mut pts: [Point<T, 2>; 3]) -> Triangle<T> {
23    match Point::orient(&pts[0], &pts[1], &pts[2]) {
24      Orientation::CounterClockWise => Triangle(pts),
25      Orientation::ClockWise => {
26        pts.swap(0, 2);
27        Triangle(pts)
28      }
29      Orientation::CoLinear => panic!("Cannot orient colinear points."),
30    }
31  }
32
33  pub fn validate(&self) -> Result<(), Error> {
34    self.view().validate()
35  }
36
37  // O(1)
38  pub fn locate(&self, pt: &Point<T, 2>) -> PointLocation {
39    self.view().locate(pt)
40  }
41
42  pub fn view(&self) -> TriangleView<'_, T> {
43    TriangleView([&self.0[0], &self.0[1], &self.0[2]])
44  }
45}
46
47pub struct TriangleView<'a, T>([&'a Point<T, 2>; 3]);
48
49impl<'a, T> TriangleView<'a, T>
50where
51  T: PolygonScalar,
52{
53  // O(1)
54  pub fn new(pts: [&'a Point<T, 2>; 3]) -> Result<TriangleView<'a, T>, Error> {
55    let triangle = TriangleView(pts);
56    triangle.validate()?;
57    Ok(triangle)
58  }
59
60  pub fn new_ccw(pts: [&'a Point<T, 2>; 3]) -> TriangleView<'a, T> {
61    match Point::orient(pts[0], pts[1], pts[2]) {
62      Orientation::CounterClockWise => TriangleView(pts),
63      Orientation::ClockWise => TriangleView([pts[2], pts[1], pts[0]]),
64      Orientation::CoLinear => panic!("Cannot orient colinear points."),
65    }
66  }
67
68  pub fn new_unchecked(pts: [&'a Point<T, 2>; 3]) -> TriangleView<'a, T> {
69    TriangleView(pts)
70  }
71
72  // O(1)
73  pub fn validate(&self) -> Result<(), Error> {
74    if self.orientation() != Orientation::CounterClockWise {
75      Err(Error::ClockWiseViolation)
76    } else {
77      Ok(())
78    }
79  }
80
81  pub fn orientation(&self) -> Orientation {
82    let arr = &self.0;
83    Point::orient(arr[0], arr[1], arr[2])
84  }
85
86  // O(1)
87  pub fn locate(&self, pt: &Point<T, 2>) -> PointLocation {
88    use Orientation::*;
89    debug_assert_ok!(self.validate());
90    let [a, b, c] = self.0;
91    let ab = Point::orient(a, b, pt);
92    let bc = Point::orient(b, c, pt);
93    let ca = Point::orient(c, a, pt);
94    if ab == ClockWise || bc == ClockWise || ca == ClockWise {
95      PointLocation::Outside
96    } else if ab == CoLinear || bc == CoLinear || ca == CoLinear {
97      PointLocation::OnBoundary
98    } else {
99      PointLocation::Inside
100    }
101  }
102
103  pub fn signed_area<F>(&self) -> F
104  where
105    T: PolygonScalar + Into<F>,
106    F: NumOps<F, F> + FromPrimitive + Clone,
107  {
108    self.signed_area_2x::<F>() / F::from_usize(2).unwrap()
109  }
110
111  pub fn signed_area_2x<F>(&self) -> F
112  where
113    T: PolygonScalar + Into<F>,
114    F: NumOps<F, F> + Clone,
115  {
116    let [a, b, c] = self.0;
117    let ax = a.x_coord().clone().into();
118    let ay = a.y_coord().clone().into();
119    let bx = b.x_coord().clone().into();
120    let by = b.y_coord().clone().into();
121    let cx = c.x_coord().clone().into();
122    let cy = c.y_coord().clone().into();
123    ax.clone() * by.clone() - bx.clone() * ay.clone() + bx * cy.clone() - cx.clone() * by + cx * ay
124      - ax * cy
125    // x1*y2 - x2*y1 +
126    // x2*y3 - x3*y2 +
127    // x3*y1 - x1*y3
128  }
129
130  pub fn bounding_box(&self) -> (Point<T, 2>, Point<T, 2>) {
131    let min_x = self.0[0]
132      .x_coord()
133      .total_min(self.0[1].x_coord())
134      .total_min(self.0[2].x_coord())
135      .clone();
136    let max_x = self.0[0]
137      .x_coord()
138      .total_max(self.0[1].x_coord())
139      .total_max(self.0[2].x_coord())
140      .clone();
141    let min_y = self.0[0]
142      .y_coord()
143      .total_min(self.0[1].y_coord())
144      .total_min(self.0[2].y_coord())
145      .clone();
146    let max_y = self.0[0]
147      .y_coord()
148      .total_max(self.0[1].y_coord())
149      .total_max(self.0[2].y_coord())
150      .clone();
151    (Point::new([min_x, min_y]), Point::new([max_x, max_y]))
152  }
153
154  pub fn rejection_sampling<R>(&self, rng: &mut R) -> Point<T, 2>
155  where
156    R: Rng + ?Sized,
157    T: SampleUniform,
158  {
159    let (min, max) = self.bounding_box();
160    loop {
161      let [min_x, min_y] = min.array.clone();
162      let [max_x, max_y] = max.array.clone();
163      let x = rng.gen_range(min_x..=max_x);
164      let y = rng.gen_range(min_y..=max_y);
165      let pt = Point::new([x, y]);
166      if self.locate(&pt) != PointLocation::Outside {
167        return pt;
168      }
169    }
170  }
171
172  // sampleTriangle :: (RandomGen g, Random r, Fractional r, Ord r) => Triangle 2 p r -> Rand g (Point 2 r)
173  // sampleTriangle (Triangle v1 v2 v3) = do
174  //   a' <- getRandomR (0, 1)
175  //   b' <- getRandomR (0, 1)
176  //   let (a, b) = if a' + b' > 1 then (1 - a', 1 - b') else (a', b')
177  //   return $ v1^.core .+^ a*^u .+^ b*^v
178  //   where
179  //     u = v2^.core .-. v1^.core
180  //     v = v3^.core .-. v1^.core
181}
rgeometry/data/triangle.rs

rgeometry/data/
triangle.rs
