|
|
| (25 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == planegeometry.rs ==
| |
| <syntaxhighlight lang="rs">
| |
| // plane_geometry.rs
| |
| // Geometry of points and lines in the plane, implemented with rational numbers. The implementation is janky, though.
| |
| // Can be used to enumerate ternary billiard scales.
| |
| use std::ops::Add;
| |
| use std::ops::Sub;
| |
| use std::ops::Neg;
| |
| use std::iter::zip;
| |
| use num_traits::sign::Signed;
| |
| use std::fmt;
| |
|
| |
|
| use num_rational::Rational64 as r64;
| |
|
| |
| #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
| |
| /// The possible configurations of a point and an oriented line on the plane.
| |
| pub enum PointLineConfiguration {
| |
| Left, // The point is on the left half-plane.
| |
| Right, // The point is on the right half-plane.
| |
| OnTheLine, // The point is on the line.
| |
| }
| |
|
| |
| fn is_between(a:r64, b:r64, c:r64) -> bool {
| |
| if b == c {
| |
| a == b
| |
| } else if b < c {
| |
| b < a && a < c
| |
| } else {
| |
| c < a && a < b
| |
| }
| |
| }
| |
|
| |
| /// Gives the greatest common denominator of the two inputs, unless that's 2^63.
| |
| /// 2^63 doesn't fit in an `i64`, so it returns -2^63, which does.
| |
| pub fn gcd(u: i64, v: i64) -> i64 {
| |
| // `wrapping_abs` gives a number's absolute value, unless that's 2^63. 2^63
| |
| // won't fit in `i64`, so it gives -2^63 instead.
| |
| let mut v = v.wrapping_abs() as u64;
| |
| if u == 0 {
| |
| return v as i64;
| |
| }
| |
| let mut u = u.wrapping_abs() as u64;
| |
| if v == 0 {
| |
| return u as i64;
| |
| }
| |
|
| |
| // `|` is bitwise OR. `trailing_zeros` quickly counts a binary number's
| |
| // trailing zeros, giving its prime factorization's exponent on two.
| |
| let gcd_exponent_on_two = (u | v).trailing_zeros();
| |
|
| |
| // `>>=` divides the left by two to the power of the right, storing that in
| |
| // the left variable. `u` divided by its prime factorization's power of two
| |
| // turns it odd.
| |
| u >>= u.trailing_zeros();
| |
| v >>= v.trailing_zeros();
| |
|
| |
| while u != v {
| |
| if u < v {
| |
| // Swap the variables' values with each other.
| |
| core::mem::swap(&mut u, &mut v);
| |
| }
| |
| u -= v;
| |
| u >>= u.trailing_zeros();
| |
| }
| |
|
| |
| // `<<` multiplies the left by two to the power of the right.
| |
| (u << gcd_exponent_on_two) as i64
| |
| }
| |
|
| |
| /// A rational number or unsigned infinity; represents a valid slope for a line in Q^2.
| |
| #[derive(Copy, Clone, Debug, Hash)]
| |
| pub struct Slope {
| |
| numer: i64,
| |
| denom: i64,
| |
| }
| |
|
| |
| impl PartialEq for Slope {
| |
| fn eq(&self, other: &Self) -> bool {
| |
| self.numer * other.denom == other.numer * self.denom
| |
| }
| |
| }
| |
|
| |
| impl fmt::Display for Slope {
| |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
| |
| write!(f, "{}/{}", self.numer, self.denom)
| |
| }
| |
| }
| |
|
| |
| impl Slope {
| |
| /// Converts a `Slope` to a rational; returns Err if `denom` is 0.
| |
| pub fn as_rational(&self) -> Result<r64, String> {
| |
| if self.denom != 0 {
| |
| Ok(r64::new(self.numer, self.denom))
| |
| } else {
| |
| Err("Attempted to convert a Slope with `denom` == 0 into a Rational64".to_string())
| |
| }
| |
| }
| |
|
| |
| /// Converts the projective rational to a rational; panics if the denominator is zero.
| |
| pub fn as_rational_raw(&self) -> r64 {
| |
| r64::new(self.numer, self.denom)
| |
| }
| |
|
| |
| /// Create a new reduced Slope; panics if both numer and denom are 0.
| |
| pub fn new(n: i64, d: i64) -> Result<Self, String> {
| |
| let (mut numer, mut denom) = (n, d);
| |
| if numer == 0 && denom == 0 {
| |
| Err("Attempted to create a Slope with both `numer` and `denom` equal to 0".to_string())
| |
| } else {
| |
| if denom < 0 {
| |
| numer = -numer;
| |
| denom = -denom;
| |
| }
| |
| let d = gcd(numer, denom);
| |
| if d > 1 {
| |
| numer = numer/d;
| |
| denom = denom/d;
| |
| }
| |
| Ok(Self {
| |
| numer,
| |
| denom,
| |
| })
| |
| }
| |
| }
| |
|
| |
| /// Create a new Slope without checking that `numer` == `denom` == 0, or reducing the rational afterwards.
| |
| pub fn raw(numer: i64, denom: i64) -> Self {
| |
| Self {
| |
| numer,
| |
| denom,
| |
| }
| |
| }
| |
|
| |
| /// Create a new `Slope` from a rational.
| |
| pub fn rational(rat: r64) -> Self {
| |
| Self {
| |
| numer: *rat.numer(),
| |
| denom: *rat.denom(),
| |
| }
| |
| }
| |
|
| |
| /// Create a new `Slope` from an integer.
| |
| pub fn integer(n: i64) -> Self {
| |
| // use 'raw' since an integer is always reduced
| |
| Self::raw(n, 1)
| |
| }
| |
|
| |
| /// Shorthand for slope 0.
| |
| pub fn zero() -> Self {
| |
| Self::raw(0, 1)
| |
| }
| |
|
| |
| /// Shorthand for slope 1.
| |
| pub fn one() -> Self {
| |
| Self::raw(1, 1)
| |
| }
| |
|
| |
| /// Shorthand for infinite slope.
| |
| pub fn infinity() -> Self {
| |
| Self::raw(1, 0)
| |
| }
| |
| }
| |
|
| |
|
| |
| /// A finite point; a member of Q^2.
| |
| #[derive(Copy, Clone, Debug, Hash, PartialEq)]
| |
| pub struct Point {
| |
| // The x-coordinate.
| |
| x: r64,
| |
| // The y-coordinate.
| |
| y: r64,
| |
| }
| |
|
| |
| impl Add for Point {
| |
| type Output = Self;
| |
|
| |
| fn add(self, other: Self) -> Self {
| |
| Self {
| |
| x: self.x + other.x,
| |
| y: self.y + other.y,
| |
| }
| |
| }
| |
| }
| |
|
| |
| impl Sub for Point{
| |
| type Output = Self;
| |
|
| |
| fn sub(self, other: Self) -> Self {
| |
| Self {
| |
| x: self.x - other.x,
| |
| y: self.y - other.y,
| |
| }
| |
| }
| |
| }
| |
|
| |
| impl Neg for Point{
| |
| type Output = Self;
| |
|
| |
| fn neg(self) -> Self {
| |
| Self {
| |
| x: -self.x,
| |
| y: -self.y,
| |
| }
| |
| }
| |
| }
| |
|
| |
| impl Point {
| |
| pub fn new(x: r64, y: r64) -> Self {
| |
| Self {
| |
| x,
| |
| y,
| |
| }
| |
| }
| |
|
| |
| pub fn zero() -> Self {
| |
| Self {
| |
| x: r64::new(0,1),
| |
| y: r64::new(0,1),
| |
| }
| |
| }
| |
|
| |
| pub fn scalar_mult(lambda: r64, v: Point) -> Self {
| |
| Self {
| |
| x: lambda*v.x,
| |
| y: lambda*v.y,
| |
| }
| |
| }
| |
|
| |
|
| |
| pub fn average(points: &Vec<Self>) -> Self {
| |
| let mut sum = Self::zero();
| |
| for p in points {
| |
| sum = sum + *p;
| |
| }
| |
| Self::scalar_mult(r64::new(1,1)/r64::new(points.len() as i64,1), sum)
| |
| }
| |
|
| |
| pub fn theta(v: Point) -> f64 {
| |
| ( *v.y.numer() as f64 / *v.y.denom() as f64 ).atan2( *v.x.numer() as f64 / *v.x.denom() as f64 )
| |
| }
| |
|
| |
| /// Return a copy of `points` sorted using the direction they make from the centroid, according to theta(v-centroid) in (-pi, pi].
| |
| fn ordered_ccw(mut points: Vec<Self>) -> Vec<Self> {
| |
| let centroid = Self::average(&points);
| |
| points.sort_by(|a,b| Self::theta(*a-centroid).partial_cmp(&Self::theta(*b-centroid)).unwrap() );
| |
| points
| |
| }
| |
|
| |
| pub fn midpoint(p1: &Self, p2: &Self) -> Self {
| |
| Self {
| |
| x: (p1.x+p2.x)/r64::new(2,1),
| |
| y: (p1.y+p2.y)/r64::new(2,1),
| |
| }
| |
| }
| |
| // Use the slope-intercept formula including the case where the slope is infinite.
| |
| pub fn are_collinear(p1: Self, p2: Self, p3: Self) -> bool {
| |
| (p1.y - p3.y)*(p1.x - p2.x) == (p1.y-p2.y)*(p1.x - p3.x)
| |
| }
| |
| }
| |
|
| |
| impl fmt::Display for Point {
| |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
| |
| write!(f, "({}, {})", self.x, self.y)
| |
| }
| |
| }
| |
|
| |
| /// An oriented line in Q^2 of rational or infinite slope.
| |
| #[derive(Copy, Clone, Debug, Hash)]
| |
| pub struct Line {
| |
| point1: Point,
| |
| point2: Point,
| |
| }
| |
|
| |
| impl PartialEq for Line {
| |
| fn eq(&self, other: &Self) -> bool {
| |
| self.slope() == other.slope() && self.has_point(other.point())
| |
| }
| |
| }
| |
|
| |
| impl Line {
| |
| pub fn slope(self: Line) -> Slope {
| |
| Slope::new(
| |
| (*(self.point2.y-self.point1.y).numer()) * (*(self.point2.x-self.point1.x).denom()),
| |
| (*(self.point2.x-self.point1.x).numer()) * (*(self.point2.y-self.point1.y).denom())).unwrap()
| |
| }
| |
|
| |
| pub fn point(self: Line) -> Point {
| |
| self.point1
| |
| }
| |
|
| |
| pub fn from_slope_and_point(sl: Slope, point: Point) -> Self {
| |
| Self {
| |
| point1: point,
| |
| point2: point + Point::new(r64::new_raw(sl.denom, 1), r64::new_raw(sl.numer, 1)),
| |
| }
| |
| }
| |
| pub fn from_points(point1: Point, point2: Point) -> Result<Self, String> {
| |
| if point1 == point2 {
| |
| Err("The points {point1} and {point2} are equal".to_string())
| |
| } else {
| |
| Ok(Line{point1, point2})
| |
| }
| |
| }
| |
|
| |
| /// Test whether a line is vertical.
| |
| fn is_vertical(&self) -> bool {
| |
| self.point1.x == self.point2.x
| |
| }
| |
|
| |
| /// Test whether a line is horizontal.
| |
| fn is_horizontal(&self) -> bool {
| |
| self.point1.y == self.point2.y
| |
| }
| |
|
| |
| /// Test whether two lines are parallel.
| |
| fn is_parallel(&self, other: Self) -> bool {
| |
| self.slope() == other.slope()
| |
| }
| |
|
| |
| /// Test whether `p` satisfies the equation of the line.
| |
| fn has_point(&self, p: Point) -> bool {
| |
| (p.y - self.point().y)*r64::new_raw(self.slope().denom,1) == r64::new_raw(self.slope().numer,1)*(p.x - self.point().x)
| |
| }
| |
|
| |
| /// Determine whether `p1` and `p2` are on the same side of the line.
| |
| fn on_same_side(&self, p1: Point, p2: Point) -> bool {
| |
| if self.is_vertical() {
| |
| (p1.x < self.point1.x && p2.x < self.point1.x ) || (p1.x > self.point1.x && p2.x > self.point1.x)
| |
| } else { // both `p1` and `p2` are above `self`
| |
| ((p1.y - self.point1.y)*r64::new_raw(self.slope().denom,1) > r64::new_raw(self.slope().numer,1)*(p1.x - self.point1.x) &&
| |
| (p2.y - self.point1.y)*r64::new_raw(self.slope().denom,1) > r64::new_raw(self.slope().numer,1)*(p2.x - self.point1.x))
| |
| || // ... or both are below `self`
| |
| ((p1.y - self.point1.y)*r64::new_raw(self.slope().denom,1) < r64::new_raw(self.slope().numer,1)*(p1.x - self.point1.x) &&
| |
| (p2.y - self.point1.y)*r64::new_raw(self.slope().denom,1) < r64::new_raw(self.slope().numer,1)*(p2.x - self.point1.x))
| |
| }
| |
| }
| |
|
| |
| /// Depending on the orientation of the line, determine whether the point `p` is to the left, to the right, or on the line.
| |
| pub fn point_line_config(&self, p: Point) -> PointLineConfiguration {
| |
| if self.point2.x != self.point1.x { // For non-vertical lines
| |
| if ((p.y - self.point().y)*r64::new_raw(self.slope().denom, 1) - r64::new_raw(self.slope().numer, 1)*(p.x - self.point().x)) * (self.point2.x - self.point1.x).signum() > r64::new_raw(0,1) {
| |
| PointLineConfiguration::Left
| |
| } else if ((p.y - self.point().y)*r64::new_raw(self.slope().denom, 1) - r64::new_raw(self.slope().numer, 1)*(p.x - self.point().x)) * (self.point2.x - self.point1.x).signum() == r64::new_raw(0,1) {
| |
| PointLineConfiguration::OnTheLine
| |
| } else {
| |
| PointLineConfiguration::Right
| |
| }
| |
| } else { // For vertical lines
| |
| // If point2.y < point1.y, then the line is oriented downwards, so multiply by -1 to compensate.
| |
| if (p.x-self.point().x) * (self.point2.y-self.point1.y) < r64::new_raw(0,1) { // upwards vertical line and point to the left of it, or downwards vertical line and point to the right of it.
| |
| PointLineConfiguration::Left
| |
| } else if (p.x-self.point().x) * (self.point2.y-self.point1.y) == r64::new_raw(0,1) {
| |
| PointLineConfiguration::OnTheLine
| |
| } else {
| |
| PointLineConfiguration::Right
| |
| }
| |
| }
| |
| }
| |
| }
| |
|
| |
|
| |
| impl fmt::Display for Line {
| |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
| |
| write!(f, "(slope: {}, point: {})", self.slope(), self.point1)
| |
| }
| |
| }
| |
|
| |
| /// For two non-parallel ones, find the intersection; for two parallel lines, return `None`.
| |
| pub fn intersection(l1: Line, l2: Line) -> Option<Point> {
| |
| let (x1, y1, x2, y2) = (l1.point().x, l1.point().y, l2.point().x, l2.point().y);
| |
| match (l1.slope(), l2.slope()) {
| |
| (s1, s2) if s1 == s2 => None, // Same slope
| |
| (s1, s2) if s1 == Slope::infinity() && s2 != Slope::infinity() => Some(Point {
| |
| x: x1,
| |
| y: s2.as_rational_raw() * (x1 - x2) + y2,
| |
| }),
| |
| (s1, s2) if s1 != Slope::infinity() && s2 == Slope::infinity() => Some(Point {
| |
| x: x2,
| |
| y: s1.as_rational_raw() * (x2 - x1) + y1,
| |
| }),
| |
| (s1, s2) => Some(Point {
| |
| x: (y1 - s1.as_rational_raw() * x1 + s2.as_rational_raw() * x2 - y2)
| |
| / (s2.as_rational_raw() - s1.as_rational_raw()),
| |
| y: (s1.as_rational_raw() * s2.as_rational_raw() * (x2 - x1) + s2.as_rational_raw() * y1 - s1.as_rational_raw() * y2)
| |
| / (s2.as_rational_raw() - s1.as_rational_raw()),
| |
| }),
| |
| }
| |
| }
| |
|
| |
| #[derive(Clone, Debug, Hash)]
| |
| pub struct ConvexPolygon {
| |
| vertices: Vec<Point>, // Assumes that the vertices are ordered in clockwise or counterclockwise order.
| |
| }
| |
|
| |
| impl PartialEq for ConvexPolygon {
| |
| fn eq(&self, other: &Self) -> bool {
| |
| // If all the points in both polygons are equal then they are equal; we ensure this by enforcing a standard order when a `ConvexPolygon` is created.
| |
| if other.vertices.len() != self.vertices.len() {
| |
| return false;
| |
| }
| |
| for (a, b) in zip(self.vertices.iter(), other.vertices.iter()) {
| |
| if a != b {
| |
| return false;
| |
| }
| |
| }
| |
| true
| |
| }
| |
| }
| |
|
| |
| impl ConvexPolygon { // Assumes that the vertices form a convex polygon. Does not check if the `Vec` of vertices consists of distinct elements.
| |
| pub fn new(vertices: Vec<Point>) -> Option<Self> {
| |
| if vertices.len() >= 3 {
| |
| Some(Self {
| |
| vertices: Point::ordered_ccw(vertices), // This will work for vertices of a convex polygon.
| |
| })
| |
| } else {
| |
| None
| |
| }
| |
| }
| |
|
| |
| fn raw(vertices: Vec<Point>) -> Self { // Does not check for ordering.
| |
| Self {
| |
| vertices: Point::ordered_ccw(vertices), // This will work for vertices of a convex polygon.
| |
| }
| |
|
| |
| }
| |
|
| |
| pub fn centroid(&self) -> Point {
| |
| Point::average(&self.vertices)
| |
| }
| |
|
| |
| pub fn has_point_inside(&self, point: Point) -> bool {
| |
| // Do `point` and edge_i+1 x edge_i+2 lie on the same side of edge_i?
| |
| for i in 0..self.vertices.len()-2 {
| |
| if !Line::from_points(self.vertices[i], self.vertices[i+1]).unwrap().on_same_side(point, self.vertices[i+2]) {
| |
| return false;
| |
| }
| |
| }
| |
| // Check last two triples.
| |
| if !Line::from_points(self.vertices[self.vertices.len()-2], self.vertices[self.vertices.len()-1]).unwrap().on_same_side(point, self.vertices[0]) {
| |
| return false;
| |
| } else if !Line::from_points(self.vertices[self.vertices.len()-1], self.vertices[0]).unwrap().on_same_side(point, self.vertices[1]) {
| |
| return false;
| |
| } else {
| |
| return true;
| |
| }
| |
| }
| |
|
| |
| /// A vector storing the edges of the polygon in order.
| |
| fn lines_for_edges(&self) -> Vec<Line> {
| |
| let mut result: Vec<Line> = (0..self.vertices.len()-1).into_iter().map(|i| Line::from_points(self.vertices[i], self.vertices[i+1]).unwrap()).collect();
| |
| result.push(Line::from_points(self.vertices[self.vertices.len()-1], self.vertices[0]).unwrap());
| |
| result
| |
| }
| |
|
| |
| /// Subdivide a polygon with the given line and return the two pieces.
| |
| pub fn subdivide(&self, line: Line) -> (Option<ConvexPolygon>, Option<ConvexPolygon>) {
| |
| // Collect vertices that fall to the left, on thhe line, and to the right, respectively. The left and right collections are missing two vertices.
| |
| let mut vertices_left: Vec<Point> = self.vertices
| |
| .iter()
| |
| .filter(|&x| line.point_line_config(*x) == PointLineConfiguration::Left).cloned().collect();
| |
| let mut vertices_right: Vec<Point> = self.vertices
| |
| .iter()
| |
| .filter(|&x| line.point_line_config(*x) == PointLineConfiguration::Right).cloned().collect();
| |
| let vertices_on_line: Vec<Point> = self.vertices
| |
| .iter()
| |
| .filter(|&x| line.point_line_config(*x) == PointLineConfiguration::OnTheLine).cloned().collect();
| |
| if !vertices_left.is_empty() || !vertices_right.is_empty() {
| |
| // Add any vertices on the line both to the new left polygon and the new right polygon.
| |
| for point in &vertices_on_line {
| |
| vertices_left.push(*point);
| |
| vertices_right.push(*point);
| |
| }
| |
| // Look for intersection points on edges with the line.
| |
| for edge in &self.lines_for_edges() {
| |
| if let Some(intsn) = intersection(*edge, line) {
| |
| if is_between(intsn.x, edge.point1.x, edge.point2.x) && is_between(intsn.y, edge.point1.y, edge.point2.y) {
| |
| vertices_left.push(intsn);
| |
| vertices_right.push(intsn);
| |
| }
| |
| }
| |
| }
| |
| // At most two vertices are added, so if there was no vertex to one side originally, that side doesn't have a polygon.
| |
| }
| |
| (ConvexPolygon::new(vertices_left), ConvexPolygon::new(vertices_right))
| |
| }
| |
|
| |
|
| |
| fn triangle_from_lines(l1: Line, l2: Line, l3: Line) -> Option<Self> {
| |
| if !l1.is_parallel(l2) && !l2.is_parallel(l3) && !l3.is_parallel(l1) {
| |
| let p1 = intersection(l1, l2).unwrap();
| |
| let p2 = intersection(l2, l3).unwrap();
| |
| let p3 = intersection(l3, l1).unwrap();
| |
| Self::new(vec![p1, p2, p3])
| |
| } else {
| |
| None
| |
| }
| |
| }
| |
|
| |
| fn parallelogram_from_lines(l1: Line, l2: Line, m1: Line, m2: Line) -> Option<Self> {
| |
| if l1.is_parallel(l2) && l1 != l2 && m1.is_parallel(m2) && m1 != m2 {
| |
| let p1 = intersection(l1, m1).unwrap();
| |
| let p2 = intersection(l1, m2).unwrap();
| |
| let p3 = intersection(l2, m1).unwrap();
| |
| let p4 = intersection(l2, m2).unwrap();
| |
| Self::new(vec![p1, p2, p3, p4])
| |
| } else {
| |
| None
| |
| }
| |
| }
| |
| }
| |
|
| |
| fn projected_constraint_planes(a: u32, b: u32, c: u32) -> (Vec<Line>, Vec<Line>, Vec<Line>) {
| |
| let first = (0..b+c+1).map(|i| Line::from_slope_and_point(Slope::raw(0, 1), Point::new(r64::new(0, 1), r64::new(-(b as i64) + (i as i64), c as i64 ) ) )).collect(); // horizontal lines going up (Left)
| |
| let second = (0..a+c+1).map(|j| Line::from_slope_and_point(Slope::raw(1, 0), Point::new(r64::new((c as i64)-(j as i64), c as i64), r64::new(0, 1) ) )).collect(); // vertical lines going left (Left)
| |
| let third = (0..a+b+1).map(|k| Line::from_slope_and_point(Slope::raw(b as i64, a as i64), Point::new( r64::new(0, 1), r64::new(-(b as i64)+(k as i64), a as i64))) ).collect(); // lines of pos. slope going up (Left)
| |
| (first, second, third)
| |
| }
| |
|
| |
| /// Project the unit cube in R^3 via a linear map that has (a,b,c) in its kernel.
| |
| pub fn projected_cube(a: u32, b: u32, c: u32) -> Option<ConvexPolygon> {
| |
| if a > 0 && b > 0 && c > 0 {
| |
| let projected_cube_vertices = vec![Point::new(r64::new(0,1), r64::new(1,1)),
| |
| Point::new(r64::new(1,1), r64::new(1,1)),
| |
| Point::new(r64::new(1,1), r64::new(0,1)),
| |
| Point::new(r64::new(-(a as i64), c as i64), r64::new(-(b as i64), c as i64) + r64::new(1,1)),
| |
| Point::new(r64::new(-(a as i64), c as i64), r64::new(-(b as i64), c as i64)),
| |
| Point::new(r64::new(-(a as i64), c as i64) + r64::new(1,1), r64::new(-(b as i64), c as i64))];
| |
| ConvexPolygon::new(projected_cube_vertices)
| |
| } else {
| |
| None
| |
| }
| |
| }
| |
|
| |
| /// Partition the projected unit cube with the projected constraint planes.
| |
| pub fn project_and_partition(a: u32, b: u32, c: u32) -> Vec<ConvexPolygon> {
| |
| let projected_cube = projected_cube(a, b, c).unwrap();
| |
| let lineses = projected_constraint_planes(a, b, c); // it's a vector of vector of `Line`s
| |
| let mut first_shapes = Vec::<ConvexPolygon>::new();
| |
| let mut second_shapes = Vec::<ConvexPolygon>::new();
| |
| let mut third_shapes = Vec::<ConvexPolygon>::new();
| |
| let mut i: usize = 0;
| |
| let mut remaining: ConvexPolygon = projected_cube;
| |
| while let (maybe_remaining, maybe_next) = remaining.subdivide((lineses.0)[i]) { // The remaining portion is to the Left.
| |
| match (maybe_remaining, maybe_next) {
| |
| (Some(r), None) => {
| |
| remaining = r;
| |
| },
| |
| (Some(r), Some(next)) => {
| |
| remaining = r;
| |
| first_shapes.push(next);
| |
| },
| |
| (None, Some(next)) => { // This is the last `next` you need to look at.
| |
| first_shapes.push(next);
| |
| break;
| |
| },
| |
| (_, _) => {
| |
| break;
| |
| },
| |
| }
| |
| i = i+1;
| |
| }
| |
| for polygon in first_shapes {
| |
| let mut j: usize = 0;
| |
| let mut remaining2: ConvexPolygon = polygon;
| |
| loop {
| |
| let (maybe_remaining, maybe_next) = remaining2.subdivide((lineses.1)[j]); // The remaining portion is to the Left.
| |
| match (maybe_remaining, maybe_next) {
| |
| (Some(r), None) => {
| |
| remaining2 = r;
| |
| },
| |
| (Some(r), Some(next)) => {
| |
| remaining2 = r;
| |
| second_shapes.push(next);
| |
| },
| |
| (None, Some(next)) => {
| |
| second_shapes.push(next);
| |
| break;
| |
| },
| |
| (_, _) => {
| |
| break;
| |
| },
| |
| }
| |
| j = j+1;
| |
| }
| |
| }
| |
| for polygon in second_shapes {
| |
| let mut j: usize = 0;
| |
| let mut remaining3: ConvexPolygon = polygon;
| |
| while let (maybe_remaining, maybe_next) = remaining3.subdivide((lineses.2)[j]) { // The remaining portion is to the Left.
| |
| match (maybe_remaining, maybe_next) {
| |
| (Some(r), None) => {
| |
| remaining3 = r;
| |
| },
| |
| (Some(r), Some(next)) => {
| |
| remaining3 = r;
| |
| third_shapes.push(next);
| |
| },
| |
| (None, Some(next)) => {
| |
| third_shapes.push(next);
| |
| break;
| |
| },
| |
| (_, _) => {
| |
| break;
| |
| },
| |
| }
| |
| j = j+1;
| |
| }
| |
| }
| |
| for polygon in third_shapes.clone() {
| |
| }
| |
| third_shapes
| |
| }
| |
|
| |
| /// Advance a projected point, `pt`, by one letter according to what integer coordinate it next hits as it traverses in the given velocity,
| |
| /// and return the next point and the corresponding letter, one of "x", "y", and "z".
| |
| pub fn advance(a: u32, b: u32, c: u32, pt: Point) -> Result<(Point, String), String> {
| |
| let projected_cube = projected_cube(a, b, c).unwrap();
| |
| // Consider: _ /
| |
| // |
| |
| if !projected_cube.has_point_inside(pt) {
| |
| Err(format!("Point passed to `advance`, {}, is not inside the projected cube", pt))
| |
| } else {
| |
| let projected_x_y_equals_1_1 = Line::from_slope_and_point(Slope::raw(b as i64, a as i64), Point::new( r64::new(0, 1), r64::new(-(b as i64)+(a as i64), a as i64))); // the /
| |
| let projected_x_z_equals_1_1 = Line::from_slope_and_point(Slope::raw(0, 1), Point::new(r64::new(0, 1), r64::new(-(b as i64)+(c as i64), c as i64))); // the _, oriented right
| |
| let projected_y_z_equals_1_1 = Line::from_slope_and_point(Slope::raw(1, 0), Point::new(r64::new((c as i64)-(a as i64), c as i64), r64::new(0, 1))); // the |, oriented up
| |
| if projected_x_y_equals_1_1.point_line_config(pt) == PointLineConfiguration::Right
| |
| && projected_y_z_equals_1_1.point_line_config(pt) == PointLineConfiguration::Right { // Below the / and to the right of the | => x has changed, change x coordinate to 0 and project; move x coordinate to the left
| |
| Ok((pt - Point::new(r64::new(1,1), r64::new(0,1)), "x".to_string())) // new point is one unit to the left
| |
| } else if projected_x_z_equals_1_1.point_line_config(pt) == PointLineConfiguration::Left
| |
| && projected_x_y_equals_1_1.point_line_config(pt) == PointLineConfiguration::Left { // Above the _ and to the left of the / => y has changed, change y coordinate to 0 and project; move y coordinate down
| |
| Ok((pt - Point::new(r64::new(0,1), r64::new(1,1)), "y".to_string())) // new point is one unit below
| |
| } else if projected_x_z_equals_1_1.point_line_config(pt) == PointLineConfiguration::Right
| |
| && projected_y_z_equals_1_1.point_line_config(pt) == PointLineConfiguration::Left { // Below the _ and to the left of the | => z has changed, change y coordinate to 0 and project
| |
| Ok((pt + Point::new(r64::new((a as i64), (c as i64)), r64::new((b as i64), (c as i64) ) ), "z".to_string())) // new point is one unit below in the z-direction, and e3 is projected to (-a/c, -b/c)
| |
| } else {
| |
| Err(format!("Point passed to `advance`, {}, is inside the projected cube but falls on a projected constraint plane", pt))
| |
| }
| |
| }
| |
| }
| |
|
| |
| #[cfg(test)]
| |
| mod tests {
| |
| use num_rational::Rational64 as r64;
| |
| use crate::plane_geometry::Slope;
| |
| use crate::plane_geometry::Point;
| |
| use crate::plane_geometry::Line;
| |
| use crate::plane_geometry::intersection;
| |
| use crate::plane_geometry::ConvexPolygon;
| |
| use crate::plane_geometry::PointLineConfiguration;
| |
| use crate::plane_geometry::projected_cube;
| |
|
| |
| // Tests for the struct `Slope`.
| |
| #[test]
| |
| fn slope_bad_slope() {
| |
| let bad_slope : Result<Slope, String> = Slope::new(0,0);
| |
| assert_eq!(bad_slope,
| |
| Err("Attempted to create a Slope with both `numer` and `denom` equal to 0".to_string()));
| |
| }
| |
|
| |
| #[test]
| |
| fn slope_infinite_slope() {
| |
| let infinite_slope : Result<Slope, String> = Slope::new(1,0);
| |
| assert_eq!(infinite_slope, Ok(Slope::infinity()));
| |
| }
| |
|
| |
| #[test]
| |
| fn slope_zero_slope() {
| |
| let zero_slope : Result<Slope, String> = Slope::new(0,1);
| |
| assert_eq!(zero_slope, Ok(Slope::zero()));
| |
| }
| |
|
| |
| #[test]
| |
| fn slope_integer_slope() {
| |
| let slope_four : Slope = Slope::integer(4i64);
| |
| assert_eq!(slope_four, Slope::raw(4,1));
| |
| }
| |
|
| |
| #[test]
| |
| fn slope_reduction() {
| |
| let slope_two : Result<Slope, String> = Slope::new(8,4);
| |
| assert_eq!(slope_two, Ok(Slope::raw(2,1)));
| |
| let slope_half : Result<Slope, String> = Slope::new(4,8);
| |
| assert_eq!(slope_half, Ok(Slope::raw(1,2)));
| |
| }
| |
|
| |
| #[test]
| |
| fn slope_as_rational() {
| |
| let good_rational : Result<r64, String> = Slope::new(3,2).expect("Bad slope").as_rational();
| |
| assert_eq!(good_rational, Ok(r64::new(3,2)));
| |
|
| |
| let bad_rational : Result<r64, String> = Slope::new(3,0).expect("Bad slope").as_rational();
| |
| assert_eq!(bad_rational,
| |
| Err("Attempted to convert a Slope with `denom` == 0 into a Rational64".to_string()));
| |
| }
| |
|
| |
| // Tests for the module `Point`.
| |
|
| |
| #[test]
| |
| fn point_create_point() {
| |
| let point : Point = Point::new(r64::new(2,1),r64::new(2,1));
| |
| assert_eq!(point, Point{ x: r64::new(2,1), y: r64::new(2,1)})
| |
| }
| |
|
| |
| #[test]
| |
| fn point_midpoint_vertical() {
| |
| let point1 : Point = Point::new(r64::new(2,1),r64::new(2,1));
| |
| let point2 : Point = Point::new(r64::new(2,1),r64::new(1,1));
| |
| assert_eq!(Point::midpoint(&point1, &point2), Point{ x: r64::new(2,1), y: r64::new(3,2)})
| |
| }
| |
|
| |
| #[test]
| |
| fn point_midpoint_nonvertical() {
| |
| let point1 : Point = Point::new(r64::new(1,1),r64::new(2,1));
| |
| let point2 : Point = Point::new(r64::new(2,1),r64::new(1,1));
| |
| assert_eq!(Point::midpoint(&point1, &point2), Point{ x: r64::new(3,2), y: r64::new(3,2)})
| |
| }
| |
|
| |
| #[test]
| |
| fn point_midpoint_identical() {
| |
| let point1 : Point = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let point2 : Point = Point::new(r64::new(1,1),r64::new(1,1));
| |
| assert_eq!(Point::midpoint(&point1, &point2), Point{ x: r64::new(1,1), y: r64::new(1,1)})
| |
| }
| |
|
| |
| #[test]
| |
| fn point_collinear() {
| |
| let point1 : Point = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let point2 : Point = Point::new(r64::new(3,1),r64::new(4,1));
| |
| let point3 : Point = Point::new(r64::new(1,1),r64::new(4,1));
| |
| let point4 : Point = Point::new(r64::new(2,1),r64::new(5,2));
| |
|
| |
| assert!(Point::are_collinear(point1, point1, point1));
| |
| assert!(Point::are_collinear(point1, point1, point2));
| |
| assert!(Point::are_collinear(point1, point2, point1));
| |
| assert!(Point::are_collinear(point2, point1, point1));
| |
| assert!(Point::are_collinear(point1, point2, point4));
| |
| assert!(!Point::are_collinear(point1, point2, point3));
| |
| }
| |
|
| |
| #[test]
| |
| fn line_parallel_implies_equal_slope() {
| |
| let line1 = Line::from_points(Point::new(r64::new(0,1),r64::new(0,1)), Point::new(r64::new(1,1),r64::new(1,1))).unwrap();
| |
| let line2 = Line::from_points(Point::new(r64::new(0,1),r64::new(1,1)), Point::new(r64::new(1,1),r64::new(2,1))).unwrap();
| |
| assert_eq!(line1.slope(), line2.slope());
| |
| }
| |
|
| |
| // Tests for the module `Line`.
| |
| #[test]
| |
| fn line_equality() {
| |
| let line1 = Line::from_points(Point::new(r64::new(0,1),r64::new(0,1)), Point::new(r64::new(1,1),r64::new(1,1))).unwrap();
| |
| let line2 = Line::from_slope_and_point(Slope::integer(1), Point::new(r64::new(2,1),r64::new(2,1))); // equal to `line1`
| |
| assert_eq!(line1, line2);
| |
| let line3 = Line::from_slope_and_point(Slope::integer(1), Point::new(r64::new(1,2),r64::new(1,2)));
| |
| assert_eq!(line3, line2);
| |
|
| |
| let line4 = Line::from_points(Point::new(r64::new(0,1),r64::new(0,1)), Point::new(r64::new(2,1),r64::new(1,1))).unwrap();
| |
| assert_ne!(line1, line4);
| |
| let line5 = Line::from_points(Point::new(r64::new(1,1),r64::new(2,1)), Point::new(r64::new(0,1),r64::new(1,1))).unwrap();
| |
| assert_ne!(line1, line5);
| |
| }
| |
|
| |
| #[test]
| |
| fn line_intersection_parallel_equal() {
| |
| let line1 = Line::from_points(Point::new(r64::new(0,1),r64::new(0,1)), Point::new(r64::new(1,1),r64::new(1,1))).unwrap();
| |
| let line2 = Line::from_slope_and_point(Slope::integer(1), Point::new(r64::new(2,1),r64::new(2,1))); // equal to `line1`
| |
| assert_eq!(intersection(line1, line2), None);
| |
| }
| |
|
| |
|
| |
| #[test]
| |
| fn line_intersection_parallel_unequal() {
| |
| let line1 = Line::from_points(Point::new(r64::new(0,1),r64::new(0,1)), Point::new(r64::new(1,1),r64::new(1,1))).unwrap();
| |
| let line2 = Line::from_points(Point::new(r64::new(0,1),r64::new(1,2)), Point::new(r64::new(1,1),r64::new(3,2))).unwrap(); // not equal but parallel to `line1`
| |
| assert_eq!(intersection(line1, line2), None);
| |
|
| |
| let line3 = Line::from_points(Point::new(r64::new(0,1),r64::new(1,1)), Point::new(r64::new(1,1),r64::new(2,1))).unwrap(); // not equal but parallel to `line1`
| |
| assert_eq!(intersection(line1, line3), None);
| |
| }
| |
|
| |
| #[test]
| |
| fn line_intersection_nonparallel() {
| |
| let line1 = Line::from_points(Point::new(r64::new(0,1),r64::new(0,1)), Point::new(r64::new(1,1),r64::new(1,1))).unwrap();
| |
| let line2 = Line::from_points(Point::new(r64::new(0,1),r64::new(0,1)), Point::new(r64::new(1,1),r64::new(2,1))).unwrap();
| |
| assert_eq!(intersection(line1, line2), Some(Point::new(r64::new(0,1), r64::new(0,1))));
| |
| }
| |
|
| |
| #[test]
| |
| fn point_order_coordinate_vecs() {
| |
| let e1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let e2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
|
| |
| let mut points = vec![e1, -e1, e2, -e2, e1+e2, e1-e2, -e1-e2, -e1+e2];
| |
| points = Point::ordered_ccw(points);
| |
| assert!(points[0] == -e1-e2 && points[1] == -e2 && points[2] == e1-e2 && points[3] == e1 && points[4] == e1+e2 && points[5] == e2 && points[6] == -e1+e2 && points[7] == -e1 );
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_disallow_polygon_with_fewer_than_3_vertices() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let result0 = ConvexPolygon::new(vec![]);
| |
| assert_eq!(result0, None);
| |
| let result1 = ConvexPolygon::new(vec![p1]);
| |
| assert_eq!(result1, None);
| |
| let result2 = ConvexPolygon::new(vec![p1, p2]);
| |
| assert_eq!(result2, None);
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_vertices_of_triangle_are_sorted() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
|
| |
| let triangle = ConvexPolygon::new(vec![p1, p2, p3]);
| |
| assert!(triangle.is_some());
| |
|
| |
| let vertices = triangle.unwrap().vertices;
| |
| assert_eq!(vertices, vec![p3, p1, p2]);
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_vertices_of_square_are_sorted() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
| let p4 = Point::new(r64::new(1,1),r64::new(1,1));
| |
|
| |
| let square = ConvexPolygon::new(vec![p1, p2, p3, p4]);
| |
| assert!(square.is_some());
| |
|
| |
| let vertices = square.unwrap().vertices;
| |
| assert_eq!(vertices, vec![p3, p1, p4, p2]);
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_vertices_of_5gon_are_sorted() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
| let p4 = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let p5 = Point::new(r64::new(1,2),r64::new(2,1));
| |
|
| |
| let pentagon = ConvexPolygon::new(vec![p1, p2, p3, p4, p5]);
| |
| assert!(pentagon.is_some());
| |
|
| |
| let vertices = pentagon.unwrap().vertices;
| |
| assert_eq!(vertices, vec![p3, p1, p4, p5, p2]);
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_triangle_has_centroid_inside() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
|
| |
| let triangle = ConvexPolygon::new(vec![p1, p2, p3]);
| |
| let centroid = ConvexPolygon::centroid(&triangle.clone().unwrap());
| |
| assert!(triangle.clone().unwrap().has_point_inside(centroid));
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_vertex_is_not_inside() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
|
| |
| let triangle = ConvexPolygon::new(vec![p1, p2, p3]);
| |
| assert!(!triangle.unwrap().has_point_inside(p1));
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_point_on_edge_is_not_inside() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
|
| |
| let triangle = ConvexPolygon::new(vec![p1, p2, p3]);
| |
| let p_edge = Point::midpoint(&p1, &p2);
| |
| assert!(!triangle.unwrap().has_point_inside(p_edge));
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_point_outside_is_not_inside() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
|
| |
| let triangle = ConvexPolygon::new(vec![p1, p2, p3]);
| |
| let p_outside = Point::new(r64::new(1,1),r64::new(1,1));
| |
| assert!(!triangle.unwrap().has_point_inside(p_outside));
| |
| }
| |
|
| |
| #[test]
| |
| fn line_point_line_config_test_vertical_line() {
| |
| let p_left = Point::new(r64::new(-1,1),r64::new(0,1));
| |
| let p_on_line = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p_right = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let vertical_line_up = Line::from_slope_and_point(Slope::infinity(), Point::zero());
| |
| assert_eq!(vertical_line_up.point_line_config(p_left), PointLineConfiguration::Left);
| |
| assert_eq!(vertical_line_up.point_line_config(p_on_line), PointLineConfiguration::OnTheLine);
| |
| assert_eq!(vertical_line_up.point_line_config(p_right), PointLineConfiguration::Right);
| |
| let vertical_line_down = Line::from_points(Point::zero(), Point::new(r64::new(0,1), r64::new(-1,1)));
| |
| assert_eq!(vertical_line_down.clone().unwrap().point_line_config(p_left), PointLineConfiguration::Right);
| |
| assert_eq!(vertical_line_down.clone().unwrap().point_line_config(p_on_line), PointLineConfiguration::OnTheLine);
| |
| assert_eq!(vertical_line_down.clone().unwrap().point_line_config(p_right), PointLineConfiguration::Left);
| |
| }
| |
|
| |
| #[test]
| |
| fn line_point_line_config_test_pos_slope() {
| |
| let p_above = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p_on_line = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let p_below = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let line_up_right = Line::from_slope_and_point(Slope::integer(1), Point::zero());
| |
| assert_eq!(line_up_right.point_line_config(p_above), PointLineConfiguration::Left);
| |
| assert_eq!(line_up_right.point_line_config(p_on_line), PointLineConfiguration::OnTheLine);
| |
| assert_eq!(line_up_right.point_line_config(p_below), PointLineConfiguration::Right);
| |
| let line_down_left = Line::from_points(Point::zero(), Point::new(r64::new(-1,1), r64::new(-1,1)));
| |
| assert_eq!(line_down_left.clone().unwrap().point_line_config(p_above), PointLineConfiguration::Right);
| |
| assert_eq!(line_down_left.clone().unwrap().point_line_config(p_on_line), PointLineConfiguration::OnTheLine);
| |
| assert_eq!(line_down_left.clone().unwrap().point_line_config(p_below), PointLineConfiguration::Left);
| |
| }
| |
|
| |
| #[test]
| |
| fn line_point_line_config_test_neg_slope() {
| |
| let p_below = Point::new(r64::new(-1,1),r64::new(0,1));
| |
| let p_on_line = Point::new(r64::new(-1,1),r64::new(1,1));
| |
| let p_above = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let line_down_right = Line::from_slope_and_point(Slope::integer(-1), Point::zero());
| |
| assert_eq!(line_down_right.point_line_config(p_below), PointLineConfiguration::Right);
| |
| assert_eq!(line_down_right.point_line_config(p_on_line), PointLineConfiguration::OnTheLine);
| |
| assert_eq!(line_down_right.point_line_config(p_above), PointLineConfiguration::Left);
| |
| let line_up_left = Line::from_points(Point::zero(), Point::new(r64::new(-1,1), r64::new(1,1)));
| |
| assert_eq!(line_up_left.clone().unwrap().point_line_config(p_below), PointLineConfiguration::Left);
| |
| assert_eq!(line_up_left.clone().unwrap().point_line_config(p_on_line), PointLineConfiguration::OnTheLine);
| |
| assert_eq!(line_up_left.clone().unwrap().point_line_config(p_above), PointLineConfiguration::Right);
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_if_all_vertices_are_to_one_side() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
| let p4 = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let square = ConvexPolygon::raw(vec![p3, p1, p4, p2]);
| |
|
| |
| let line_to_the_right = Line::from_slope_and_point(Slope::infinity(), Point::new(r64::new(2,1), r64::new(0,1)));
| |
| let line_to_the_left = Line::from_slope_and_point(Slope::infinity(), Point::new(r64::new(-1,1), r64::new(0,1)));
| |
| let line_above = Line::from_slope_and_point(Slope::zero(), Point::new(r64::new(0,1), r64::new(2,1)));
| |
| let line_below = Line::from_slope_and_point(Slope::zero(), Point::new(r64::new(0,1), r64::new(-1,1)));
| |
|
| |
| assert_eq!(square.subdivide(line_to_the_right), (Some(ConvexPolygon::raw(vec![p3, p1, p4, p2])), Option::<ConvexPolygon>::None) );
| |
| assert_eq!(square.subdivide(line_to_the_left), (Option::<ConvexPolygon>::None, Some(ConvexPolygon::raw(vec![p3, p1, p4, p2]))) );
| |
| assert_eq!(square.subdivide(line_above), (Option::<ConvexPolygon>::None, Some(ConvexPolygon::raw(vec![p3, p1, p4, p2]))) );
| |
| assert_eq!(square.subdivide(line_below), (Some(ConvexPolygon::raw(vec![p3, p1, p4, p2])), Option::<ConvexPolygon>::None) );
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_new_line_cuts_two_edges() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
| let p4 = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let square = ConvexPolygon::raw(vec![p3, p1, p4, p2]);
| |
|
| |
| let line = Line::from_slope_and_point(Slope::infinity(), Point::new(r64::new(1,2), r64::new(0,1)));
| |
| let (left_polygon, right_polygon) = square.subdivide(line);
| |
| assert_eq!(left_polygon, Some(ConvexPolygon::raw(vec![Point::new(r64::new(0,1),r64::new(0,1)),
| |
| Point::new(r64::new(1,2),r64::new(0,1)),
| |
| Point::new(r64::new(1,2),r64::new(1,1)),
| |
| Point::new(r64::new(0,1),r64::new(1,1))
| |
| ])), "`left_polygon` is not right polygon");
| |
| assert_eq!(right_polygon, Some(ConvexPolygon::raw(vec![Point::new(r64::new(1,2),r64::new(0,1)),
| |
| Point::new(r64::new(1,1),r64::new(0,1)),
| |
| Point::new(r64::new(1,1),r64::new(1,1)),
| |
| Point::new(r64::new(1,2),r64::new(1,1))
| |
| ])), "`right_polygon` is not right polygon");
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_new_line_grazes_one_vertex() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
| let p4 = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let square = ConvexPolygon::raw(vec![p3, p1, p4, p2]);
| |
|
| |
| let line = Line::from_slope_and_point(Slope::integer(1), Point::new(r64::new(0,1), r64::new(1,1)));
| |
| let (left_polygon, right_polygon) = square.subdivide(line);
| |
|
| |
| assert_eq!(left_polygon, None, "`left_polygon` is not right polygon");
| |
| assert_eq!(right_polygon, Some(ConvexPolygon::raw(vec![p3, p1, p4, p2])), "`right_polygon` is not right polygon");
| |
|
| |
| let line2 = Line::from_slope_and_point(Slope::integer(1), Point::new(r64::new(1,1), r64::new(0,1)));
| |
| let (left_polygon, right_polygon) = square.subdivide(line2);
| |
|
| |
| assert_eq!(left_polygon, Some(ConvexPolygon::raw(vec![p3, p1, p4, p2])), "`left_polygon` is not right polygon");
| |
| assert_eq!(right_polygon, None, "`right_polygon` is not right polygon");
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_new_line_coincides_with_one_edge() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
| let p4 = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let square = ConvexPolygon::raw(vec![p3, p1, p4, p2]);
| |
|
| |
| let line = Line::from_slope_and_point(Slope::infinity(), Point::new(r64::new(0,1), r64::new(0,1)));
| |
| let (left_polygon, right_polygon) = square.subdivide(line);
| |
|
| |
| assert_eq!(left_polygon, None, "`left_polygon` is not right polygon");
| |
| assert_eq!(right_polygon, Some(ConvexPolygon::raw(vec![p3, p1, p4, p2])), "`right_polygon` is not right polygon");
| |
|
| |
| let line = Line::from_slope_and_point(Slope::integer(0), Point::new(r64::new(1,1), r64::new(0,1)));
| |
| let (left_polygon, right_polygon) = square.subdivide(line);
| |
|
| |
| assert_eq!(left_polygon, Some(ConvexPolygon::raw(vec![p3, p1, p4, p2])), "`left_polygon` is not right polygon");
| |
| assert_eq!(right_polygon, None, "`right_polygon` is not right polygon");
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_new_line_cuts_one_edge() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
| let p4 = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let square = ConvexPolygon::raw(vec![p3, p1, p4, p2]);
| |
|
| |
| let line = Line::from_slope_and_point(Slope::integer(2), Point::new(r64::new(0,1), r64::new(0,1)));
| |
| let (left_polygon, right_polygon) = square.subdivide(line);
| |
|
| |
| assert_eq!(left_polygon, Some(ConvexPolygon::raw(vec![Point::new(r64::new(0,1),r64::new(0,1)),
| |
| Point::new(r64::new(1,2),r64::new(1,1)),
| |
| Point::new(r64::new(0,1),r64::new(1,1)),
| |
| ])), "`left_polygon is not right polygon");
| |
| assert_eq!(right_polygon, Some(ConvexPolygon::raw(vec![Point::new(r64::new(0,1),r64::new(0,1)),
| |
| Point::new(r64::new(1,1),r64::new(0,1)),
| |
| Point::new(r64::new(1,1),r64::new(1,1)),
| |
| Point::new(r64::new(1,2),r64::new(1,1))
| |
| ])), "`right_polygon` is not right polygon");
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_new_line_cuts_no_edges() {
| |
| let p1 = Point::new(r64::new(1,1),r64::new(0,1));
| |
| let p2 = Point::new(r64::new(0,1),r64::new(1,1));
| |
| let p3 = Point::new(r64::new(0,1),r64::new(0,1));
| |
| let p4 = Point::new(r64::new(1,1),r64::new(1,1));
| |
| let square = ConvexPolygon::raw(vec![p3, p1, p4, p2]);
| |
|
| |
| let line = Line::from_slope_and_point(Slope::integer(1), Point::new(r64::new(0,1), r64::new(0,1)));
| |
| let (left_polygon, right_polygon) = square.subdivide(line);
| |
|
| |
| assert_eq!(left_polygon, Some(ConvexPolygon::raw(vec![Point::new(r64::new(0,1),r64::new(0,1)),
| |
| Point::new(r64::new(1,1),r64::new(1,1)),
| |
| Point::new(r64::new(0,1),r64::new(1,1))
| |
| ])), "`left_polygon` is not right polygon");
| |
| assert_eq!(right_polygon, Some(ConvexPolygon::raw(vec![Point::new(r64::new(0,1),r64::new(0,1)),
| |
| Point::new(r64::new(1,1),r64::new(0,1)),
| |
| Point::new(r64::new(1,1),r64::new(1,1))
| |
| ])), "`right_polygon` is not right polygon");
| |
| }
| |
|
| |
| #[test]
| |
| fn convexpolygon_subdivide_test() {
| |
| let hexagon = projected_cube(5, 2, 3);
| |
| assert_eq!(hexagon, ConvexPolygon::new(vec![Point::new(r64::new(1,1),r64::new(0,1)), Point::new(r64::new(0,1),r64::new(1,1)), Point::new(r64::new(1,1),r64::new(1,1)),
| |
| Point::new(r64::new(-5,3),r64::new(-2,3)), Point::new(r64::new(-2,3),r64::new(-2,3)), Point::new(r64::new(-5,3),r64::new(1,3))]) );
| |
| let line = Line::from_slope_and_point(Slope::integer(0), Point::new(r64::new(0,1), r64::new(-1,3)));
| |
| let divided = hexagon.unwrap().subdivide(line);
| |
| assert_eq!(divided.0, ConvexPolygon::new(vec![Point::new(r64::new(1,1),r64::new(0,1)), Point::new(r64::new(0,1),r64::new(1,1)), Point::new(r64::new(1,1),r64::new(1,1)),
| |
| Point::new(r64::new(-5,3),r64::new(-1,3)), Point::new(r64::new(1,6),r64::new(-1,3)), Point::new(r64::new(-5,3),r64::new(1,3))]) );
| |
| assert_eq!(divided.1, ConvexPolygon::new(vec![ Point::new(r64::new(-5,3),r64::new(-1,3)), Point::new(r64::new(1,6),r64::new(-1,3)),
| |
| Point::new(r64::new(-5,3),r64::new(-2,3)), Point::new(r64::new(-2,3),r64::new(-2,3)) ]) );
| |
| let line2 = Line::from_slope_and_point(Slope::integer(0), Point::new(r64::new(0,1), r64::new(0,1)));
| |
| let divided_again = (divided.0).unwrap().subdivide(line2);
| |
|
| |
| assert_eq!(divided_again.0, ConvexPolygon::new(vec![Point::new(r64::new(1,1),r64::new(0,1)), Point::new(r64::new(0,1),r64::new(1,1)), Point::new(r64::new(1,1),r64::new(1,1)),
| |
| Point::new(r64::new(-5,3),r64::new(0,1)), Point::new(r64::new(-5,3),r64::new(1,3))]) );
| |
| assert_eq!(divided_again.1, ConvexPolygon::new(vec![Point::new(r64::new(1,1),r64::new(0,1)), Point::new(r64::new(1,6),r64::new(-1,3)),
| |
| Point::new(r64::new(-5,3),r64::new(0,1)), Point::new(r64::new(-5,3),r64::new(-1,3))]) );
| |
| }
| |
|
| |
| }
| |
| </syntaxhighlight>
| |