///|
/// A mutable-free polyline view used by editors, masks, and path analysis.
pub struct Polyline2D {
  points : Array[Point2]
  closed : Bool
} derive(Debug)

///|
pub fn polyline2d(points : Array[Point2], closed? : Bool = false) -> Polyline2D {
  { points: points.copy(), closed }
}

///|
pub fn Polyline2D::points(self : Polyline2D) -> Array[Point2] {
  self.points.copy()
}

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

///|
pub fn Polyline2D::closed(self : Polyline2D) -> Bool {
  self.closed
}

///|
pub fn Polyline2D::total_length(self : Polyline2D) -> Double {
  if self.points.length() < 2 {
    return 0.0
  }
  let mut total = 0.0
  for index in 1.. (Point2, Double) {
  let dx = end.x() - start.x()
  let dy = end.y() - start.y()
  let length_squared = dx * dx + dy * dy
  if length_squared <= 0.0 {
    return (start, 0.0)
  }
  let ratio = clamp01(
    ((point.x() - start.x()) * dx + (point.y() - start.y()) * dy) /
    length_squared,
  )
  (start.lerp(end, ratio), ratio)
}

///|
pub struct PolylineProjection2D {
  point : Point2
  segment : Int
  ratio : Double
  distance : Double
  arc_length : Double
} derive(Debug)

///|
pub fn PolylineProjection2D::point(self : PolylineProjection2D) -> Point2 {
  self.point
}

///|
pub fn PolylineProjection2D::segment(self : PolylineProjection2D) -> Int {
  self.segment
}

///|
pub fn PolylineProjection2D::ratio(self : PolylineProjection2D) -> Double {
  self.ratio
}

///|
pub fn PolylineProjection2D::distance(self : PolylineProjection2D) -> Double {
  self.distance
}

///|
pub fn PolylineProjection2D::arc_length(self : PolylineProjection2D) -> Double {
  self.arc_length
}

///|
pub fn Polyline2D::project(
  self : Polyline2D,
  target : Point2,
) -> PolylineProjection2D {
  if self.points.length() == 0 {
    return {
      point: target,
      segment: 0,
      ratio: 0.0,
      distance: 0.0,
      arc_length: 0.0,
    }
  }
  if self.points.length() == 1 {
    return {
      point: self.points[0],
      segment: 0,
      ratio: 0.0,
      distance: target.distance(self.points[0]),
      arc_length: 0.0,
    }
  }
  let segment_count = if self.closed {
    self.points.length()
  } else {
    self.points.length() - 1
  }
  let mut best_point = self.points[0]
  let mut best_segment = 0
  let mut best_ratio = 0.0
  let mut best_distance = target.distance(best_point)
  let mut arc = 0.0
  let mut best_arc = 0.0
  for index in 0.. Point2 {
  if self.points.length() == 0 {
    return point2(x=0.0, y=0.0)
  }
  let total = self.total_length()
  if total <= 0.0 {
    return self.points[0]
  }
  let target = clamp(distance, 0.0, total)
  let segment_count = if self.closed {
    self.points.length()
  } else {
    self.points.length() - 1
  }
  let mut arc = 0.0
  for index in 0.. Polyline2D {
  let result : Array[Point2] = []
  let actual = count.max(1)
  for index in 0.. Bounds2D {
  if self.points.length() == 0 {
    return { minimum: point2(x=0.0, y=0.0), maximum: point2(x=0.0, y=0.0) }
  }
  let mut minimum = self.points[0]
  let mut maximum = self.points[0]
  for point in self.points {
    minimum = point2(x=minimum.x().min(point.x()), y=minimum.y().min(point.y()))
    maximum = point2(x=maximum.x().max(point.x()), y=maximum.y().max(point.y()))
  }
  { minimum, maximum }
}

///|
pub fn Polyline2D::simplify(
  self : Polyline2D,
  tolerance : Double,
) -> Polyline2D {
  if self.points.length() < 3 || tolerance <= 0.0 {
    return self
  }
  let squared = tolerance * tolerance
  let keep : Array[Point2] = []
  keep.push(self.points[0])
  for index in 1..<(self.points.length() - 1) {
    let previous = keep[keep.length() - 1]
    let current = self.points[index]
    let next = self.points[index + 1]
    let (projected, _) = point_segment_projection(current, previous, next)
    if current.distance(projected) * current.distance(projected) > squared {
      keep.push(current)
    }
  }
  keep.push(self.points[self.points.length() - 1])
  polyline2d(keep, closed=self.closed)
}

///|
pub struct Polygon2D {
  vertices : Array[Point2]
} derive(Debug)

///|
pub fn polygon2d(vertices : Array[Point2]) -> Polygon2D {
  { vertices: vertices.copy() }
}

///|
pub fn Polygon2D::vertices(self : Polygon2D) -> Array[Point2] {
  self.vertices.copy()
}

///|
pub fn Polygon2D::length(self : Polygon2D) -> Int {
  self.vertices.length()
}

///|
pub fn Polygon2D::signed_area(self : Polygon2D) -> Double {
  if self.vertices.length() < 3 {
    return 0.0
  }
  let mut area = 0.0
  for index in 0.. Double {
  self.signed_area().abs()
}

///|
pub fn Polygon2D::clockwise(self : Polygon2D) -> Bool {
  self.signed_area() < 0.0
}

///|
pub fn Polygon2D::perimeter(self : Polygon2D) -> Double {
  if self.vertices.length() < 2 {
    return 0.0
  }
  let mut total = 0.0
  for index in 0.. Point2 {
  if self.vertices.length() == 0 {
    return point2(x=0.0, y=0.0)
  }
  let area_twice = self.signed_area() * 2.0
  if area_twice.abs() < 0.000000000001 {
    let mut x = 0.0
    let mut y = 0.0
    for point in self.vertices {
      x = x + point.x()
      y = y + point.y()
    }
    return point2(
      x=x / self.vertices.length().to_double(),
      y=y / self.vertices.length().to_double(),
    )
  }
  let mut x = 0.0
  let mut y = 0.0
  for index in 0.. Bool {
  if self.vertices.length() < 3 {
    return false
  }
  let mut inside = false
  let mut previous = self.vertices.length() - 1
  for index in 0.. point.y()) != (prior.y() > point.y())
    if crosses {
      let x = (prior.x() - current.x()) *
        (point.y() - current.y()) /
        (prior.y() - current.y()) +
        current.x()
      if point.x() < x {
        inside = !inside
      }
    }
    previous = index
  }
  inside
}

///|
pub fn Polygon2D::bounds(self : Polygon2D) -> Bounds2D {
  polyline2d(self.vertices, closed=true).bounds()
}

///|
pub fn Polygon2D::reversed(self : Polygon2D) -> Polygon2D {
  let values : Array[Point2] = []
  let mut index = self.vertices.length()
  while index > 0 {
    index = index - 1
    values.push(self.vertices[index])
  }
  polygon2d(values)
}

///|
fn point_cross(origin : Point2, first : Point2, second : Point2) -> Double {
  (first.x() - origin.x()) * (second.y() - origin.y()) -
  (first.y() - origin.y()) * (second.x() - origin.x())
}

///|
pub fn convex_hull(points : Array[Point2]) -> Polygon2D {
  if points.length() < 3 {
    return polygon2d(points)
  }
  let sorted = points.copy()
  sorted.sort_by(fn(left, right) {
    let x_order = left.x().compare(right.x())
    if x_order == 0 {
      left.y().compare(right.y())
    } else {
      x_order
    }
  })
  let lower : Array[Point2] = []
  for point in sorted {
    while lower.length() >= 2 &&
          point_cross(
            lower[lower.length() - 2],
            lower[lower.length() - 1],
            point,
          ) <=
          0.0 {
      ignore(lower.remove(lower.length() - 1))
    }
    lower.push(point)
  }
  let upper : Array[Point2] = []
  let mut index = sorted.length()
  while index > 0 {
    index = index - 1
    let point = sorted[index]
    while upper.length() >= 2 &&
          point_cross(
            upper[upper.length() - 2],
            upper[upper.length() - 1],
            point,
          ) <=
          0.0 {
      ignore(upper.remove(upper.length() - 1))
    }
    upper.push(point)
  }
  ignore(lower.remove(lower.length() - 1))
  ignore(upper.remove(upper.length() - 1))
  for point in upper {
    lower.push(point)
  }
  polygon2d(lower)
}

///|
pub enum JoinStyle2D {
  MiterJoin
  RoundJoin
  BevelJoin
} derive(Debug)

///|
pub fn join_styles2d() -> Array[JoinStyle2D] {
  [MiterJoin, RoundJoin, BevelJoin]
}

///|
pub fn offset_polyline2d(line : Polyline2D, distance : Double) -> Polyline2D {
  if line.points.length() < 2 {
    return line
  }
  let result : Array[Point2] = []
  let last = if line.closed {
    line.points.length()
  } else {
    line.points.length() - 1
  }
  for index in 0.. last {
    ignore(result.remove(result.length() - 1))
  }
  polyline2d(result, closed=line.closed)
}

///|
pub fn polygon2d_from_bounds(bounds : Bounds2D) -> Polygon2D {
  polygon2d([
    bounds.minimum(),
    point2(x=bounds.maximum().x(), y=bounds.minimum().y()),
    bounds.maximum(),
    point2(x=bounds.minimum().x(), y=bounds.maximum().y()),
  ])
}

///|
pub fn polygon2d_translate(polygon : Polygon2D, offset : Point2) -> Polygon2D {
  let result : Array[Point2] = []
  for point in polygon.vertices {
    result.push(point2(x=point.x() + offset.x(), y=point.y() + offset.y()))
  }
  polygon2d(result)
}

///|
pub fn polygon2d_scale(
  polygon : Polygon2D,
  scale : Point2,
  origin? : Point2 = point2(x=0.0, y=0.0),
) -> Polygon2D {
  let result : Array[Point2] = []
  for point in polygon.vertices {
    result.push(
      point2(
        x=origin.x() + (point.x() - origin.x()) * scale.x(),
        y=origin.y() + (point.y() - origin.y()) * scale.y(),
      ),
    )
  }
  polygon2d(result)
}

///|
pub fn polygon2d_rotate(
  polygon : Polygon2D,
  angle : Double,
  origin? : Point2 = point2(x=0.0, y=0.0),
) -> Polygon2D {
  let cosine = @math.cos(angle)
  let sine = @math.sin(angle)
  let result : Array[Point2] = []
  for point in polygon.vertices {
    let x = point.x() - origin.x()
    let y = point.y() - origin.y()
    result.push(
      point2(
        x=origin.x() + x * cosine - y * sine,
        y=origin.y() + x * sine + y * cosine,
      ),
    )
  }
  polygon2d(result)
}