///|
pub struct LineSegment {
  start : Point
  end : Point
} derive(Debug, Eq)

///|
pub fn LineSegment::new(start~ : Point, end~ : Point) -> LineSegment {
  { start, end }
}

///|
pub fn LineSegment::length_l1(self : LineSegment) -> Int {
  self.start.distance_l1(self.end)
}

///|
pub fn LineSegment::bounds(self : LineSegment) -> Rect {
  let left = min_i(self.start.x, self.end.x)
  let top = min_i(self.start.y, self.end.y)
  Rect::new(
    x=left,
    y=top,
    width=max_i(self.start.x, self.end.x) - left + 1,
    height=max_i(self.start.y, self.end.y) - top + 1,
  )
}

///|
pub fn LineSegment::sample(self : LineSegment, count : Int) -> Array[Point] {
  let out : Array[Point] = []
  let n = max_i(1, count)
  for i in 0.. Polygon {
  { points, }
}

///|
pub fn Polygon::empty() -> Polygon {
  Polygon::new([])
}

///|
pub fn Polygon::point_count(self : Polygon) -> Int {
  self.points.length()
}

///|
pub fn Polygon::signed_area_x2(self : Polygon) -> Int {
  let mut total = 0
  if self.points.length() >= 2 {
    for i in 0.. Int {
  abs_i(self.signed_area_x2()) / 2
}

///|
pub fn Polygon::bounds(self : Polygon) -> Rect {
  if self.points.length() == 0 {
    Rect::new(x=0, y=0, width=0, height=0)
  } else {
    let mut left = self.points[0].x
    let mut top = self.points[0].y
    let mut right = left
    let mut bottom = top
    for point in self.points {
      left = min_i(left, point.x)
      top = min_i(top, point.y)
      right = max_i(right, point.x)
      bottom = max_i(bottom, point.y)
    }
    Rect::new(x=left, y=top, width=right - left + 1, height=bottom - top + 1)
  }
}

///|
pub fn Polygon::centroid(self : Polygon) -> Point {
  if self.points.length() == 0 {
    Point::new(x=0, y=0)
  } else {
    let mut x = 0
    let mut y = 0
    for point in self.points {
      x += point.x
      y += point.y
    }
    Point::new(x=x / self.points.length(), y=y / self.points.length())
  }
}

///|
pub fn Polygon::contains(self : Polygon, point : Point) -> Bool {
  if self.points.length() < 3 {
    false
  } else {
    let mut inside = false
    let mut j = self.points.length() - 1
    for i in 0.. point.y) != (b.y > point.y)
      if crosses {
        let denominator = b.y - a.y
        if denominator != 0 {
          let x = (b.x - a.x) * (point.y - a.y) / denominator + a.x
          if point.x < x {
            inside = !inside
          }
        }
      }
      j = i
    }
    inside
  }
}

///|
pub fn Polygon::translate(self : Polygon, dx : Int, dy : Int) -> Polygon {
  let out : Array[Point] = []
  for point in self.points {
    out.push(point.translate(dx, dy))
  }
  Polygon::new(out)
}

///|
pub fn Polygon::scale(
  self : Polygon,
  numerator : Int,
  denominator : Int,
) -> Polygon {
  let den = if denominator == 0 { 1 } else { denominator }
  let out : Array[Point] = []
  for point in self.points {
    out.push(
      Point::new(x=point.x * numerator / den, y=point.y * numerator / den),
    )
  }
  Polygon::new(out)
}

///|
pub fn polygon_to_mask(polygon : Polygon, size : Size, id : Int) -> Mask {
  let mask = Mask::new(width=size.width, height=size.height)
  let bounds = polygon.bounds().intersection(mask_bounds(size))
  for y in bounds.y.. Rect {
  Rect::new(x=0, y=0, width=max_i(0, size.width), height=max_i(0, size.height))
}

///|
pub fn convex_hull(points : Array[Point]) -> Polygon {
  if points.length() <= 1 {
    Polygon::new(points)
  } else {
    let sorted = points.copy()
    for i in 1.. 0 && compare_points(sorted[j - 1], value) > 0 {
        sorted[j] = sorted[j - 1]
        j -= 1
      }
      sorted[j] = value
    }
    let lower : Array[Point] = []
    for point in sorted {
      while lower.length() >= 2 &&
            cross_turn(
              lower[lower.length() - 2],
              lower[lower.length() - 1],
              point,
            ) <=
            0 {
        ignore(lower.pop())
      }
      lower.push(point)
    }
    let upper : Array[Point] = []
    let mut i = sorted.length()
    while i > 0 {
      i -= 1
      let point = sorted[i]
      while upper.length() >= 2 &&
            cross_turn(
              upper[upper.length() - 2],
              upper[upper.length() - 1],
              point,
            ) <=
            0 {
        ignore(upper.pop())
      }
      upper.push(point)
    }
    if lower.length() > 0 {
      ignore(lower.pop())
    }
    if upper.length() > 0 {
      ignore(upper.pop())
    }
    for point in upper {
      lower.push(point)
    }
    Polygon::new(lower)
  }
}

///|
fn compare_points(a : Point, b : Point) -> Int {
  if a.x < b.x || (a.x == b.x && a.y < b.y) {
    -1
  } else if a == b {
    0
  } else {
    1
  }
}

///|
fn cross_turn(a : Point, b : Point, c : Point) -> Int {
  (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
}

///|
pub struct Affine2D {
  a : Int
  b : Int
  c : Int
  d : Int
  tx : Int
  ty : Int
  scale : Int
} derive(Debug, Eq)

///|
pub fn Affine2D::identity() -> Affine2D {
  { a: 1000, b: 0, c: 0, d: 1000, tx: 0, ty: 0, scale: 1000 }
}

///|
pub fn Affine2D::new(
  a~ : Int,
  b~ : Int,
  c~ : Int,
  d~ : Int,
  tx~ : Int,
  ty~ : Int,
  scale? : Int = 1000,
) -> Affine2D {
  { a, b, c, d, tx, ty, scale: max_i(1, scale) }
}

///|
pub fn Affine2D::apply(self : Affine2D, point : Point) -> Point {
  Point::new(
    x=(self.a * point.x + self.b * point.y) / self.scale + self.tx,
    y=(self.c * point.x + self.d * point.y) / self.scale + self.ty,
  )
}

///|
pub fn Affine2D::inverse_apply(self : Affine2D, point : Point) -> Point {
  let px = (point.x - self.tx) * self.scale
  let py = (point.y - self.ty) * self.scale
  let determinant = self.a * self.d - self.b * self.c
  if determinant == 0 {
    point
  } else {
    Point::new(
      x=(self.d * px - self.b * py) / determinant,
      y=(-self.c * px + self.a * py) / determinant,
    )
  }
}

///|
pub fn Affine2D::compose(self : Affine2D, next : Affine2D) -> Affine2D {
  let scale = self.scale * next.scale
  Affine2D::new(
    a=next.a * self.a + next.b * self.c,
    b=next.a * self.b + next.b * self.d,
    c=next.c * self.a + next.d * self.c,
    d=next.c * self.b + next.d * self.d,
    tx=next.a * self.tx / self.scale + next.b * self.ty / self.scale + next.tx,
    ty=next.c * self.tx / self.scale + next.d * self.ty / self.scale + next.ty,
    scale~,
  )
}

///|
pub fn transform_points(
  transform : Affine2D,
  points : Array[Point],
) -> Array[Point] {
  let out : Array[Point] = []
  for point in points {
    out.push(transform.apply(point))
  }
  out
}

///|
pub fn transform_polygon(transform : Affine2D, polygon : Polygon) -> Polygon {
  Polygon::new(transform_points(transform, polygon.points))
}

///|
pub fn line_raster(start : Point, end : Point) -> Array[Point] {
  LineSegment::new(start~, end~).sample(
    max_i(abs_i(end.x - start.x), abs_i(end.y - start.y)) + 1,
  )
}