haar_lib/geom/
convex_cut.rs

1//! 凸多角形の直線での切断
2
3use crate::geom::{ccw::*, intersect_line_segment::*, *};
4
5/// 凸多角形`ps`を直線`l`で切断して、その切断後の2つの多角形を返す
6pub fn convex_cut(ps: &[Vector], l: Line, eps: Eps) -> (Vec<Vector>, Vec<Vector>) {
7    use self::IntersectLineSegment::*;
8
9    let n = ps.len();
10    let mut left = vec![];
11    let mut right = vec![];
12
13    for i in 0..n {
14        let (s, c) = intersect_line_segment(l, Line::new(ps[i], ps[(i + 1) % n]), eps);
15
16        match s {
17            LEFTSIDE => left.push(ps[i]),
18            RIGHTSIDE => right.push(ps[i]),
19            OVERLAPPED => {
20                left.push(ps[i]);
21                right.push(ps[i]);
22            }
23            CROSSED => {
24                match ccw(l.from, l.to, ps[i], eps) {
25                    CCW::CLOCKWISE => right.push(ps[i]),
26                    _ => left.push(ps[i]),
27                };
28
29                left.push(c.unwrap());
30                right.push(c.unwrap());
31            }
32        }
33    }
34
35    (left, right)
36}