1 use fpnum::{fp, integral_sqrt, FPNum, FPPoint};

     2 use std::{

     3     cmp::{max, min},

     4     ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, RangeInclusive, Sub, SubAssign},

     5 };

     6 

     7 #[derive(PartialEq, Eq, Clone, Copy, Debug)]

     8 pub struct Point {

     9     pub x: i32,

    10     pub y: i32,

    11 }

    12 

    13 impl Point {

    14     pub const ZERO: Self = Self::new(0, 0);

    15 

    16     #[inline]

    17     pub const fn new(x: i32, y: i32) -> Self {

    18         Self { x, y }

    19     }

    20 

    21     #[inline]

    22     pub const fn diag(v: i32) -> Self {

    23         Self::new(v, v)

    24     }

    25 

    26     #[inline]

    27     pub fn signum(self) -> Self {

    28         Self::new(self.x.signum(), self.y.signum())

    29     }

    30 

    31     #[inline]

    32     pub fn abs(self) -> Self {

    33         Self::new(self.x.abs(), self.y.abs())

    34     }

    35 

    36     #[inline]

    37     pub const fn dot(self, other: Point) -> i32 {

    38         self.x * other.x + self.y * other.y

    39     }

    40 

    41     #[inline]

    42     pub fn max_norm(self) -> i32 {

    43         std::cmp::max(self.x.abs(), self.y.abs())

    44     }

    45 

    46     #[inline]

    47     pub fn integral_norm(self) -> u32 {

    48         let sqr = (self.x as u64).wrapping_pow(2) + (self.y as u64).wrapping_pow(2);

    49         integral_sqrt(sqr) as u32

    50     }

    51 

    52     #[inline]

    53     pub const fn transform(self, matrix: &[i32; 4]) -> Self {

    54         Point::new(

    55             matrix[0] * self.x + matrix[1] * self.y,

    56             matrix[2] * self.x + matrix[3] * self.y,

    57         )

    58     }

    59 

    60     #[inline]

    61     pub const fn rotate90(self) -> Self {

    62         Point::new(self.y, -self.x)

    63     }

    64 

    65     #[inline]

    66     pub const fn cross(self, other: Point) -> i32 {

    67         self.dot(other.rotate90())

    68     }

    69 

    70     #[inline]

    71     pub fn clamp(self, rect: &Rect) -> Point {

    72         Point::new(rect.x_range().clamp(self.x), rect.y_range().clamp(self.y))

    73     }

    74 

    75     #[inline]

    76     pub const fn line_to(self, end: Point) -> Line {

    77         Line::new(self, end)

    78     }

    79 

    80     #[inline]

    81     pub const fn ray_with_dir(self, direction: Point) -> Ray {

    82         Ray::new(self, direction)

    83     }

    84 

    85     #[inline]

    86     pub const fn tangent_mul(self, x: i32) -> i32 {

    87         x * self.y / self.x

    88     }

    89 

    90     #[inline]

    91     pub const fn cotangent_mul(self, y: i32) -> i32 {

    92         y * self.x / self.y

    93     }

    94 

    95     #[inline]

    96     pub fn to_fppoint(self) -> FPPoint {

    97         FPPoint::new(self.x.into(), self.y.into())

    98     }

    99 

   100     #[inline]

   101     pub fn from_fppoint(p: &FPPoint) -> Self {

   102         Self::new(p.x().round(), p.y().round())

   103     }

   104 }

   105 

   106 #[derive(PartialEq, Eq, Clone, Copy, Debug)]

   107 pub struct Size {

   108     pub width: usize,

   109     pub height: usize,

   110 }

   111 

   112 impl Size {

   113     pub const EMPTY: Self = Self::square(0);

   114 

   115     #[inline]

   116     pub const fn new(width: usize, height: usize) -> Self {

   117         Self { width, height }

   118     }

   119 

   120     #[inline]

   121     pub const fn square(size: usize) -> Self {

   122         Self {

   123             width: size,

   124             height: size,

   125         }

   126     }

   127 

   128     #[inline]

   129     pub const fn area(&self) -> usize {

   130         self.width * self.height

   131     }

   132 

   133     #[inline]

   134     pub const fn linear_index(&self, x: usize, y: usize) -> usize {

   135         y * self.width + x

   136     }

   137 

   138     #[inline]

   139     pub fn is_power_of_two(&self) -> bool {

   140         self.width.is_power_of_two() && self.height.is_power_of_two()

   141     }

   142 

   143     #[inline]

   144     pub fn next_power_of_two(&self) -> Self {

   145         Self {

   146             width: self.width.next_power_of_two(),

   147             height: self.height.next_power_of_two(),

   148         }

   149     }

   150 

   151     #[inline]

   152     pub const fn transpose(&self) -> Self {

   153         Self::new(self.height, self.width)

   154     }

   155 

   156     #[inline]

   157     pub fn to_mask(&self) -> SizeMask {

   158         SizeMask::new(*self)

   159     }

   160 

   161     #[inline]

   162     pub fn to_square(&self) -> Self {

   163         Self::square(max(self.width, self.height))

   164     }

   165 

   166     pub fn to_grid_index(&self) -> GridIndex {

   167         GridIndex::new(*self)

   168     }

   169 

   170     #[inline]

   171     pub fn contains(&self, other: Self) -> bool {

   172         self.width >= other.width && self.height >= other.height

   173     }

   174 

   175     #[inline]

   176     pub fn join(&self, other: Self) -> Self {

   177         Self {

   178             width: max(self.width, other.width),

   179             height: max(self.height, other.height)

   180         }

   181     }

   182 }

   183 

   184 #[derive(PartialEq, Eq, Clone, Copy, Debug)]

   185 pub struct SizeMask {

   186     size: Size,

   187 }

   188 

   189 impl SizeMask {

   190     #[inline]

   191     pub fn new(size: Size) -> Self {

   192         debug_assert!(size.is_power_of_two());

   193         let size = Size {

   194             width: !(size.width - 1),

   195             height: !(size.height - 1),

   196         };

   197         Self { size }

   198     }

   199 

   200     #[inline]

   201     pub fn contains_x<T: Into<usize>>(&self, x: T) -> bool {

   202         (self.size.width & x.into()) == 0

   203     }

   204 

   205     #[inline]

   206     pub fn contains_y<T: Into<usize>>(&self, y: T) -> bool {

   207         (self.size.height & y.into()) == 0

   208     }

   209 

   210     #[inline]

   211     pub fn contains(&self, point: Point) -> bool {

   212         self.contains_x(point.x as usize) && self.contains_y(point.y as usize)

   213     }

   214 }

   215 

   216 pub struct GridIndex {

   217     shift: Point,

   218 }

   219 

   220 impl GridIndex {

   221     pub fn new(size: Size) -> Self {

   222         assert!(size.is_power_of_two());

   223         let shift = Point::new(

   224             size.width.trailing_zeros() as i32,

   225             size.height.trailing_zeros() as i32,

   226         );

   227         Self { shift }

   228     }

   229 

   230     pub fn map(&self, position: Point) -> Point {

   231         Point::new(position.x >> self.shift.x, position.y >> self.shift.y)

   232     }

   233 }

   234 

   235 macro_rules! bin_op_impl {

   236     ($op: ty, $name: tt) => {

   237         impl $op for Point {

   238             type Output = Self;

   239 

   240             #[inline]

   241             fn $name(self, rhs: Self) -> Self::Output {

   242                 Self::new(self.x.$name(rhs.x), self.y.$name(rhs.y))

   243             }

   244         }

   245     };

   246 }

   247 

   248 macro_rules! scalar_bin_op_impl {

   249     ($($op: tt)::+, $name: tt) => {

   250         impl $($op)::+<i32> for Point {

   251             type Output = Self;

   252 

   253             #[inline]

   254             fn $name(self, rhs: i32) -> Self::Output {

   255                 Self::new(self.x.$name(rhs), self.y.$name(rhs))

   256             }

   257         }

   258     };

   259 }

   260 

   261 macro_rules! bin_assign_op_impl {

   262     ($op: ty, $name: tt) => {

   263         impl $op for Point {

   264             #[inline]

   265             fn $name(&mut self, rhs: Self) {

   266                 self.x.$name(rhs.x);

   267                 self.y.$name(rhs.y);

   268             }

   269         }

   270     };

   271 }

   272 

   273 macro_rules! fp_scalar_bin_op_impl {

   274     ($($op: tt)::+, $name: tt) => {

   275         impl $($op)::+<FPNum> for Point {

   276             type Output = FPPoint;

   277 

   278             #[inline]

   279             fn $name(self, rhs: FPNum) -> Self::Output {

   280                 FPPoint::new(rhs.$name(self.x), rhs.$name(self.y))

   281             }

   282         }

   283     };

   284 }

   285 

   286 macro_rules! left_fp_scalar_bin_op_impl {

   287     ($($op: tt)::+, $name: tt) => {

   288         impl $($op)::+<Point> for FPNum {

   289             type Output = FPPoint;

   290 

   291             #[inline]

   292             fn $name(self, rhs: Point) -> Self::Output {

   293                 FPPoint::new(self.$name(rhs.x), self.$name(rhs.y))

   294             }

   295         }

   296     };

   297 }

   298 

   299 bin_op_impl!(Add, add);

   300 bin_op_impl!(Sub, sub);

   301 bin_op_impl!(Mul, mul);

   302 bin_op_impl!(Div, div);

   303 scalar_bin_op_impl!(Mul, mul);

   304 scalar_bin_op_impl!(Div, div);

   305 fp_scalar_bin_op_impl!(Mul, mul);

   306 fp_scalar_bin_op_impl!(Div, div);

   307 left_fp_scalar_bin_op_impl!(Mul, mul);

   308 left_fp_scalar_bin_op_impl!(Div, div);

   309 bin_assign_op_impl!(AddAssign, add_assign);

   310 bin_assign_op_impl!(SubAssign, sub_assign);

   311 bin_assign_op_impl!(MulAssign, mul_assign);

   312 bin_assign_op_impl!(DivAssign, div_assign);

   313 

   314 #[derive(PartialEq, Eq, Clone, Copy, Debug)]

   315 pub struct Rect {

   316     top_left: Point,

   317     bottom_right: Point,

   318 }

   319 

   320 impl Rect {

   321     pub const EMPTY: Self = Self {

   322         top_left: Point::ZERO,

   323         bottom_right: Point::diag(-1),

   324     };

   325 

   326     #[inline]

   327     pub fn new(top_left: Point, bottom_right: Point) -> Self {

   328         debug_assert!(top_left.x <= bottom_right.x + 1);

   329         debug_assert!(top_left.y <= bottom_right.y + 1);

   330         Self {

   331             top_left,

   332             bottom_right,

   333         }

   334     }

   335 

   336     pub fn from_box(left: i32, right: i32, top: i32, bottom: i32) -> Self {

   337         Self::new(Point::new(left, top), Point::new(right, bottom))

   338     }

   339 

   340     pub fn from_size(top_left: Point, size: Size) -> Self {

   341         Self::new(

   342             top_left,

   343             top_left + Point::new(size.width as i32 - 1, size.height as i32 - 1),

   344         )

   345     }

   346 

   347     pub fn from_size_coords(x: i32, y: i32, width: usize, height: usize) -> Self {

   348         Self::from_size(Point::new(x, y), Size::new(width, height))

   349     }

   350 

   351     pub fn at_origin(size: Size) -> Self {

   352         Self::from_size(Point::ZERO, size)

   353     }

   354 

   355     #[inline]

   356     pub const fn width(&self) -> usize {

   357         (self.right() - self.left() + 1) as usize

   358     }

   359 

   360     #[inline]

   361     pub const fn height(&self) -> usize {

   362         (self.bottom() - self.top() + 1) as usize

   363     }

   364 

   365     #[inline]

   366     pub const fn size(&self) -> Size {

   367         Size::new(self.width(), self.height())

   368     }

   369 

   370     #[inline]

   371     pub const fn area(&self) -> usize {

   372         self.size().area()

   373     }

   374 

   375     #[inline]

   376     pub const fn left(&self) -> i32 {

   377         self.top_left().x

   378     }

   379 

   380     #[inline]

   381     pub const fn top(&self) -> i32 {

   382         self.top_left().y

   383     }

   384 

   385     #[inline]

   386     pub const fn right(&self) -> i32 {

   387         self.bottom_right().x

   388     }

   389 

   390     #[inline]

   391     pub const fn bottom(&self) -> i32 {

   392         self.bottom_right().y

   393     }

   394 

   395     #[inline]

   396     pub const fn top_left(&self) -> Point {

   397         self.top_left

   398     }

   399 

   400     #[inline]

   401     pub const fn bottom_right(&self) -> Point {

   402         self.bottom_right

   403     }

   404 

   405     #[inline]

   406     pub fn center(&self) -> Point {

   407         (self.top_left() + self.bottom_right()) / 2

   408     }

   409 

   410     #[inline]

   411     pub fn with_margin(&self, margin: i32) -> Self {

   412         let offset = Point::diag(margin);

   413         Self::new(self.top_left() + offset, self.bottom_right() - offset)

   414     }

   415 

   416     #[inline]

   417     pub fn x_range(&self) -> RangeInclusive<i32> {

   418         self.left()..=self.right()

   419     }

   420 

   421     #[inline]

   422     pub fn y_range(&self) -> RangeInclusive<i32> {

   423         self.top()..=self.bottom()

   424     }

   425 

   426     #[inline]

   427     pub fn contains(&self, point: Point) -> bool {

   428         self.x_range().contains(&point.x) && self.y_range().contains(&point.y)

   429     }

   430 

   431     #[inline]

   432     pub fn contains_inside(&self, point: Point) -> bool {

   433         point.x > self.left()

   434             && point.x < self.right()

   435             && point.y > self.top()

   436             && point.y < self.bottom()

   437     }

   438 

   439     #[inline]

   440     pub fn contains_rect(&self, other: &Self) -> bool {

   441         self.contains(other.top_left()) && self.contains(other.bottom_right())

   442     }

   443 

   444     #[inline]

   445     pub fn intersects(&self, other: &Rect) -> bool {

   446         self.left() <= other.right()

   447             && self.right() >= other.left()

   448             && self.top() <= other.bottom()

   449             && self.bottom() >= other.top()

   450     }

   451 

   452     #[inline]

   453     pub fn split_at(&self, point: Point) -> [Rect; 4] {

   454         assert!(self.contains_inside(point));

   455         [

   456             Self::from_box(self.left(), point.x, self.top(), point.y),

   457             Self::from_box(point.x, self.right(), self.top(), point.y),

   458             Self::from_box(point.x, self.right(), point.y, self.bottom()),

   459             Self::from_box(self.left(), point.x, point.y, self.bottom()),

   460         ]

   461     }

   462 

   463     #[inline]

   464     pub fn with_margins(&self, left: i32, right: i32, top: i32, bottom: i32) -> Self {

   465         Self::from_box(

   466             self.left() - left,

   467             self.right() + right,

   468             self.top() - top,

   469             self.bottom() + bottom,

   470         )

   471     }

   472 

   473     #[inline]

   474     pub fn quotient(self, x: usize, y: usize) -> Point {

   475         self.top_left() + Point::new((x % self.width()) as i32, (y % self.height()) as i32)

   476     }

   477 }

   478 

   479 trait RangeClamp<T> {

   480     fn clamp(&self, value: T) -> T;

   481 }

   482 

   483 impl<T: Ord + Copy> RangeClamp<T> for RangeInclusive<T> {

   484     fn clamp(&self, value: T) -> T {

   485         if value < *self.start() {

   486             *self.start()

   487         } else if value > *self.end() {

   488             *self.end()

   489         } else {

   490             value

   491         }

   492     }

   493 }

   494 

   495 pub struct Polygon {

   496     vertices: Vec<Point>,

   497 }

   498 

   499 impl Polygon {

   500     pub fn new(vertices: &[Point]) -> Self {

   501         let mut v = Vec::with_capacity(vertices.len() + 1);

   502         v.extend_from_slice(vertices);

   503         if !v.is_empty() {

   504             let start = v[0];

   505             v.push(start);

   506         }

   507         Self { vertices: v }

   508     }

   509 

   510     pub fn edges_count(&self) -> usize {

   511         self.vertices.len().saturating_sub(1)

   512     }

   513 

   514     pub fn get_edge(&self, index: usize) -> Line {

   515         Line::new(self.vertices[index], self.vertices[index + 1])

   516     }

   517 

   518     pub fn split_edge(&mut self, edge_index: usize, vertex: Point) {

   519         self.vertices.insert(edge_index + 1, vertex);

   520     }

   521 

   522     pub fn iter<'a>(&'a self) -> impl Iterator<Item = &Point> + 'a {

   523         (&self.vertices[..self.edges_count()]).iter()

   524     }

   525 

   526     pub fn iter_mut<'a>(&'a mut self) -> impl Iterator<Item = &mut Point> + 'a {

   527         let edges_count = self.edges_count();

   528         let start = self.vertices.as_mut_ptr();

   529         let end = unsafe { start.add(edges_count) };

   530         PolygonPointsIteratorMut {

   531             source: self,

   532             start,

   533             end,

   534         }

   535     }

   536 

   537     fn force_close(&mut self) {

   538         if !self.vertices.is_empty() {

   539             let edges_count = self.edges_count();

   540             self.vertices[edges_count] = self.vertices[0];

   541         }

   542     }

   543 

   544     pub fn iter_edges<'a>(&'a self) -> impl Iterator<Item = Line> + 'a {

   545         (&self.vertices[0..self.edges_count()])

   546             .iter()

   547             .zip(&self.vertices[1..])

   548             .map(|(s, e)| Line::new(*s, *e))

   549     }

   550 

   551     pub fn bezierize(&mut self, segments_number: u32) {

   552         fn calc_point(p1: Point, p2: Point, p3: Point) -> FPPoint {

   553             let diff13 = (p1 - p3).to_fppoint();

   554             let diff13_norm = diff13.distance();

   555 

   556             if diff13_norm.is_zero() {

   557                 diff13

   558             } else {

   559                 let diff12_norm = (p1 - p2).to_fppoint().distance();

   560                 let diff23_norm = (p2 - p3).to_fppoint().distance();

   561                 let min_distance = min(diff13_norm, min(diff12_norm, diff23_norm));

   562 

   563                 diff13 * min_distance / diff13_norm / 3

   564             }

   565         }

   566 

   567         if self.vertices.len() < 4 {

   568             return;

   569         }

   570 

   571         let delta = fp!(1 / segments_number);

   572         let mut bezierized_vertices = Vec::new();

   573         let mut pi = 0;

   574         let mut i = 1;

   575         let mut ni = 2;

   576         let mut right_point = calc_point(self.vertices[pi], self.vertices[i], self.vertices[ni]);

   577         let mut left_point;

   578 

   579         pi += 1;

   580         while pi != 0 {

   581             pi = i;

   582             i = ni;

   583             ni += 1;

   584             if ni >= self.vertices.len() {

   585                 ni = 0;

   586             }

   587 

   588             left_point = right_point;

   589             right_point = calc_point(self.vertices[pi], self.vertices[i], self.vertices[ni]);

   590 

   591             bezierized_vertices.extend(BezierCurveSegments::new(

   592                 Line::new(self.vertices[pi], self.vertices[i]),

   593                 left_point,

   594                 -right_point,

   595                 delta,

   596             ));

   597         }

   598 

   599         self.vertices = bezierized_vertices;

   600     }

   601 }

   602 

   603 struct PolygonPointsIteratorMut<'a> {

   604     source: &'a mut Polygon,

   605     start: *mut Point,

   606     end: *mut Point,

   607 }

   608 

   609 impl<'a> Iterator for PolygonPointsIteratorMut<'a> {

   610     type Item = &'a mut Point;

   611 

   612     fn next(&mut self) -> Option<<Self as Iterator>::Item> {

   613         if self.start == self.end {

   614             None

   615         } else {

   616             unsafe {

   617                 let result = &mut *self.start;

   618                 self.start = self.start.add(1);

   619                 Some(result)

   620             }

   621         }

   622     }

   623 }

   624 

   625 impl<'a> Drop for PolygonPointsIteratorMut<'a> {

   626     fn drop(&mut self) {

   627         self.source.force_close();

   628     }

   629 }

   630 

   631 impl From<Vec<Point>> for Polygon {

   632     fn from(mut v: Vec<Point>) -> Self {

   633         if !v.is_empty() && v[0] != v[v.len() - 1] {

   634             let start = v[0];

   635             v.push(start)

   636         }

   637         Self { vertices: v }

   638     }

   639 }

   640 

   641 #[derive(PartialEq, Eq, Clone, Copy, Debug)]

   642 pub struct Ray {

   643     pub start: Point,

   644     pub direction: Point,

   645 }

   646 

   647 impl Ray {

   648     #[inline]

   649     pub const fn new(start: Point, direction: Point) -> Ray {

   650         Self { start, direction }

   651     }

   652 

   653     #[inline]

   654     pub const fn tangent_mul(&self, x: i32) -> i32 {

   655         self.direction.tangent_mul(x)

   656     }

   657 

   658     #[inline]

   659     pub const fn cotangent_mul(&self, y: i32) -> i32 {

   660         self.direction.cotangent_mul(y)

   661     }

   662 

   663     #[inline]

   664     pub fn orientation(&self, point: Point) -> i32 {

   665         (point - self.start).cross(self.direction).signum()

   666     }

   667 }

   668 

   669 #[derive(PartialEq, Eq, Clone, Copy, Debug)]

   670 pub struct Line {

   671     pub start: Point,

   672     pub end: Point,

   673 }

   674 

   675 impl Line {

   676     pub const ZERO: Self = Self::new(Point::ZERO, Point::ZERO);

   677 

   678     #[inline]

   679     pub const fn new(start: Point, end: Point) -> Self {

   680         Self { start, end }

   681     }

   682 

   683     #[inline]

   684     pub fn center(&self) -> Point {

   685         (self.start + self.end) / 2

   686     }

   687 

   688     #[inline]

   689     pub fn scaled_direction(&self) -> Point {

   690         self.end - self.start

   691     }

   692 

   693     #[inline]

   694     pub fn scaled_normal(&self) -> Point {

   695         self.scaled_direction().rotate90()

   696     }

   697 

   698     #[inline]

   699     pub fn to_ray(&self) -> Ray {

   700         Ray::new(self.start, self.scaled_direction())

   701     }

   702 }

   703 

   704 impl IntoIterator for Line {

   705     type Item = Point;

   706     type IntoIter = LinePoints;

   707 

   708     fn into_iter(self) -> Self::IntoIter {

   709         LinePoints::new(self)

   710     }

   711 }

   712 

   713 pub struct LinePoints {

   714     accumulator: Point,

   715     direction: Point,

   716     sign: Point,

   717     current: Point,

   718     total_steps: i32,

   719     step: i32,

   720 }

   721 

   722 impl LinePoints {

   723     pub fn new(line: Line) -> Self {

   724         let dir = line.end - line.start;

   725 

   726         Self {

   727             accumulator: Point::ZERO,

   728             direction: dir.abs(),

   729             sign: dir.signum(),

   730             current: line.start,

   731             total_steps: dir.max_norm(),

   732             step: 0,

   733         }

   734     }

   735 }

   736 

   737 impl Iterator for LinePoints {

   738     type Item = Point;

   739 

   740     fn next(&mut self) -> Option<Self::Item> {

   741         if self.step <= self.total_steps {

   742             self.accumulator += self.direction;

   743 

   744             if self.accumulator.x > self.total_steps {

   745                 self.accumulator.x -= self.total_steps;

   746                 self.current.x += self.sign.x;

   747             }

   748             if self.accumulator.y > self.total_steps {

   749                 self.accumulator.y -= self.total_steps;

   750                 self.current.y += self.sign.y;

   751             }

   752 

   753             self.step += 1;

   754 

   755             Some(self.current)

   756         } else {

   757             None

   758         }

   759     }

   760 }

   761 

   762 pub struct ArcPoints {

   763     point: Point,

   764     step: i32,

   765 }

   766 

   767 impl ArcPoints {

   768     pub const fn new(radius: i32) -> Self {

   769         Self {

   770             point: Point::new(0, radius),

   771             step: 3 - 2 * radius,

   772         }

   773     }

   774 }

   775 

   776 impl Iterator for ArcPoints {

   777     type Item = Point;

   778 

   779     fn next(&mut self) -> Option<Self::Item> {

   780         if self.point.x < self.point.y {

   781             let result = self.point;

   782 

   783             if self.step < 0 {

   784                 self.step += self.point.x * 4 + 6;

   785             } else {

   786                 self.step += (self.point.x - self.point.y) * 4 + 10;

   787                 self.point.y -= 1;

   788             }

   789 

   790             self.point.x += 1;

   791 

   792             Some(result)

   793         } else if self.point.x == self.point.y {

   794             self.point.x += 1;

   795 

   796             Some(self.point)

   797         } else {

   798             None

   799         }

   800     }

   801 }

   802 

   803 pub struct EquidistantPoints {

   804     vector: Vec<Point>,

   805 }

   806 

   807 impl EquidistantPoints {

   808     pub fn new(vector: Point) -> Self {

   809         Self {

   810             vector: if vector.x == vector.y {

   811                 vec![

   812                     Point::new(vector.x, vector.x),

   813                     Point::new(vector.x, -vector.x),

   814                     Point::new(-vector.x, -vector.x),

   815                     Point::new(-vector.x, vector.x),

   816                 ]

   817             } else {

   818                 vec![

   819                     Point::new(vector.x, vector.y),

   820                     Point::new(vector.x, -vector.y),

   821                     Point::new(-vector.x, -vector.y),

   822                     Point::new(-vector.x, vector.y),

   823                     Point::new(vector.y, vector.x),

   824                     Point::new(vector.y, -vector.x),

   825                     Point::new(-vector.y, -vector.x),

   826                     Point::new(-vector.y, vector.x),

   827                 ]

   828             },

   829         }

   830     }

   831 }

   832 

   833 impl IntoIterator for EquidistantPoints {

   834     type Item = Point;

   835     type IntoIter = std::vec::IntoIter<Point>;

   836 

   837     fn into_iter(self) -> Self::IntoIter {

   838         self.vector.into_iter()

   839     }

   840 }

   841 

   842 pub struct BezierCurveSegments {

   843     segment: Line,

   844     control_point1: FPPoint,

   845     control_point2: FPPoint,

   846     offset: FPNum,

   847     max_offset: FPNum,

   848     delta: FPNum,

   849     have_finished: bool,

   850 }

   851 

   852 impl BezierCurveSegments {

   853     pub fn new(segment: Line, p1: FPPoint, p2: FPPoint, delta: FPNum) -> Self {

   854         Self {

   855             segment,

   856             control_point1: segment.start.to_fppoint() - p1,

   857             control_point2: segment.end.to_fppoint() - p2,

   858             offset: fp!(0),

   859             max_offset: fp!(4095 / 4096),

   860             delta,

   861             have_finished: false,

   862         }

   863     }

   864 }

   865 

   866 impl Iterator for BezierCurveSegments {

   867     type Item = Point;

   868 

   869     fn next(&mut self) -> Option<Self::Item> {

   870         if self.offset < self.max_offset {

   871             let offset_sq = self.offset * self.offset;

   872             let offset_cub = offset_sq * self.offset;

   873 

   874             let r1 = fp!(1) - self.offset * 3 + offset_sq * 3 - offset_cub;

   875             let r2 = self.offset * 3 - offset_sq * 6 + offset_cub * 3;

   876             let r3 = offset_sq * 3 - offset_cub * 3;

   877 

   878             let p = r1 * self.segment.start

   879                 + r2 * self.control_point1

   880                 + r3 * self.control_point2

   881                 + offset_cub * self.segment.end;

   882 

   883             self.offset += self.delta;

   884 

   885             Some(Point::from_fppoint(&p))

   886         } else if !self.have_finished {

   887             self.have_finished = true;

   888 

   889             Some(self.segment.end)

   890         } else {

   891             None

   892         }

   893     }

   894 }

   895 

   896 #[cfg(test)]

   897 mod tests {

   898     use super::*;

   899 

   900     fn get_points(coords: &[(i32, i32)]) -> Vec<Point> {

   901         coords.iter().map(|(x, y)| Point::new(*x, *y)).collect()

   902     }

   903 

   904     #[test]

   905     fn line_basic() {

   906         let line: Vec<Point> = Line::new(Point::new(0, 0), Point::new(3, 3))

   907             .into_iter()

   908             .collect();

   909         let v = get_points(&[(0, 0), (1, 1), (2, 2), (3, 3)]);

   910 

   911         assert_eq!(line, v);

   912     }

   913 

   914     #[test]

   915     fn line_skewed() {

   916         let line: Vec<Point> = Line::new(Point::new(0, 0), Point::new(5, -7))

   917             .into_iter()

   918             .collect();

   919         let v = get_points(&[

   920             (0, 0),

   921             (1, -1),

   922             (2, -2),

   923             (2, -3),

   924             (3, -4),

   925             (4, -5),

   926             (4, -6),

   927             (5, -7),

   928         ]);

   929 

   930         assert_eq!(line, v);

   931     }

   932 

   933     #[test]

   934     fn equidistant_full() {

   935         let n: Vec<Point> = EquidistantPoints::new(Point::new(1, 3))

   936             .into_iter()

   937             .collect();

   938         let v = get_points(&[

   939             (1, 3),

   940             (1, -3),

   941             (-1, -3),

   942             (-1, 3),

   943             (3, 1),

   944             (3, -1),

   945             (-3, -1),

   946             (-3, 1),

   947         ]);

   948 

   949         assert_eq!(n, v);

   950     }

   951 

   952     #[test]

   953     fn equidistant_half() {

   954         let n: Vec<Point> = EquidistantPoints::new(Point::new(2, 2))

   955             .into_iter()

   956             .collect();

   957         let v = get_points(&[(2, 2), (2, -2), (-2, -2), (-2, 2)]);

   958 

   959         assert_eq!(n, v);

   960     }

   961 

   962     #[test]

   963     fn line() {

   964         let l = Line::new(Point::new(1, 1), Point::new(5, 6));

   965 

   966         assert_eq!(l.center(), Point::new(3, 3));

   967     }

   968 

   969     #[test]

   970     fn rect() {

   971         let r = Rect::from_box(10, 100, 0, 70);

   972 

   973         assert!(r.contains_inside(Point::new(99, 69)));

   974         assert!(!r.contains_inside(Point::new(100, 70)));

   975 

   976         assert_eq!(r.top_left(), Point::new(10, 0));

   977         assert_eq!(r.with_margin(12), Rect::from_box(22, 88, 12, 58));

   978     }

   979 

   980     #[test]

   981     fn fit() {

   982         let r = Rect::from_box(10, 100, 0, 70);

   983 

   984         assert_eq!(Point::new(0, -10).clamp(&r), Point::new(10, 0));

   985         assert_eq!(Point::new(1000, 1000).clamp(&r), Point::new(100, 70));

   986     }

   987 }