// Ports Clipper2 2.0.1 (CPP/Clipper2Lib/include/clipper2/clipper.core.h, commit
// 642390d), Boost Software License 1.0, Copyright (c) Angus Johnson 2010-2026.
// See NOTICE.

///|
/// A point with integer coordinates (Clipper2's `Point64`).
#derive(Debug, Eq)
pub(all) struct Point64 {
  x : Int64
  y : Int64
}

///|
/// Which regions of a set of paths count as filled (Clipper2's `FillRule`).
#derive(Debug, Eq)
pub(all) enum FillRule {
  EvenOdd
  NonZero
  Positive
  Negative
}

///|
/// A boolean operation (Clipper2's `ClipType`; all but `Difference` commute).
#derive(Debug, Eq)
pub(all) enum ClipType {
  NoClip
  Intersection
  Union
  Difference
  Xor
}

///|
/// Largest coordinate Clipper2 accepts (`INT64_MAX >> 2`).
pub const MAX_COORD : Int64 = 2305843009213693951L

///|
/// `x` rounded to the nearest integer, ties to even (C's `nearbyint` in the
/// default rounding mode).
fn nearbyint(x : Double) -> Int64 {
  let f = x.floor()
  let d = x - f
  let r = if d < 0.5 {
    f
  } else if d > 0.5 {
    f + 1.0
  } else if f % 2.0 == 0.0 {
    f
  } else {
    f + 1.0
  }
  r.to_int64()
}

///|
fn tri_sign(x : Int64) -> Int32 {
  if x > 0L {
    1
  } else if x < 0L {
    -1
  } else {
    0
  }
}

///|
/// `a * b` of two unsigned 64-bit values as (low, high) halves (`MultiplyUInt64`).
fn multiply_u64(a : UInt64, b : UInt64) -> (UInt64, UInt64) {
  let mask = 0xFFFFFFFFUL
  let x1 = (a & mask) * (b & mask)
  let x2 = (a >> 32) * (b & mask) + (x1 >> 32)
  let x3 = (a & mask) * (b >> 32) + (x2 & mask)
  (
    ((x3 & mask) << 32) | (x1 & mask),
    (a >> 32) * (b >> 32) + (x2 >> 32) + (x3 >> 32),
  )
}

///|
fn abs_u64(v : Int64) -> UInt64 {
  (if v < 0L { -v } else { v }).reinterpret_as_uint64()
}

///|
/// Whether `a * b == c * d` exactly (`ProductsAreEqual`).
fn products_are_equal(a : Int64, b : Int64, c : Int64, d : Int64) -> Bool {
  let ab = multiply_u64(abs_u64(a), abs_u64(b))
  let cd = multiply_u64(abs_u64(c), abs_u64(d))
  ab == cd && tri_sign(a) * tri_sign(b) == tri_sign(c) * tri_sign(d)
}

///|
/// The sign of the cross product of (pt2 - pt1) and (pt3 - pt2), exactly
/// (`CrossProductSign`).
fn cross_product_sign(pt1 : Point64, pt2 : Point64, pt3 : Point64) -> Int32 {
  let a = pt2.x - pt1.x
  let b = pt3.y - pt2.y
  let c = pt2.y - pt1.y
  let d = pt3.x - pt2.x
  let ab = multiply_u64(abs_u64(a), abs_u64(b))
  let cd = multiply_u64(abs_u64(c), abs_u64(d))
  let sign_ab = tri_sign(a) * tri_sign(b)
  let sign_cd = tri_sign(c) * tri_sign(d)
  if sign_ab == sign_cd {
    let result = if ab.1 == cd.1 {
      if ab.0 == cd.0 {
        return 0
      }
      if ab.0 > cd.0 {
        1
      } else {
        -1
      }
    } else if ab.1 > cd.1 {
      1
    } else {
      -1
    }
    if sign_ab > 0 {
      result
    } else {
      -result
    }
  } else if sign_ab > sign_cd {
    1
  } else {
    -1
  }
}

///|
fn is_collinear(pt1 : Point64, shared : Point64, pt2 : Point64) -> Bool {
  products_are_equal(
    shared.x - pt1.x,
    pt2.y - shared.y,
    shared.y - pt1.y,
    pt2.x - shared.x,
  )
}

///|
fn dot_product(pt1 : Point64, pt2 : Point64, pt3 : Point64) -> Double {
  (pt2.x - pt1.x).to_double() * (pt3.x - pt2.x).to_double() +
  (pt2.y - pt1.y).to_double() * (pt3.y - pt2.y).to_double()
}

///|
fn sqr(v : Double) -> Double {
  v * v
}

///|
fn perpendic_dist_from_line_sqrd(
  pt : Point64,
  line1 : Point64,
  line2 : Point64,
) -> Double {
  let a = (pt.x - line1.x).to_double()
  let b = (pt.y - line1.y).to_double()
  let c = (line2.x - line1.x).to_double()
  let d = (line2.y - line1.y).to_double()
  if c == 0.0 && d == 0.0 {
    return 0.0
  }
  sqr(a * d - c * b) / (c * c + d * d)
}

///|
/// A path's signed area, positive for counter-clockwise paths in a y-up frame
/// (`Area`).
pub fn area(path : ArrayView[Point64]) -> Double {
  let cnt = path.length()
  if cnt < 3 {
    return 0.0
  }
  let mut a = 0.0
  let mut i2 = cnt - 1
  let stop = if cnt % 2 == 0 { cnt } else { cnt - 1 }
  let mut i1 = 0
  while i1 != stop {
    a += (path[i2].y + path[i1].y).to_double() *
      (path[i2].x - path[i1].x).to_double()
    i2 = i1 + 1
    a += (path[i1].y + path[i2].y).to_double() *
      (path[i1].x - path[i2].x).to_double()
    i1 += 2
  }
  if cnt % 2 == 1 {
    a += (path[i2].y + path[i1].y).to_double() *
      (path[i2].x - path[i1].x).to_double()
  }
  a * 0.5
}

///|
/// Where the lines through `ln1a`-`ln1b` and `ln2a`-`ln2b` cross, kept within
/// the first segment; None when they are parallel (`GetLineIntersectPt`).
fn get_line_intersect_pt(
  ln1a : Point64,
  ln1b : Point64,
  ln2a : Point64,
  ln2b : Point64,
) -> Point64? {
  let dx1 = (ln1b.x - ln1a.x).to_double()
  let dy1 = (ln1b.y - ln1a.y).to_double()
  let dx2 = (ln2b.x - ln2a.x).to_double()
  let dy2 = (ln2b.y - ln2a.y).to_double()
  let det = dy1 * dx2 - dy2 * dx1
  if det == 0.0 {
    return None
  }
  let t = (
      (ln1a.x - ln2a.x).to_double() * dy2 - (ln1a.y - ln2a.y).to_double() * dx2
    ) /
    det
  if t <= 0.0 {
    Some(ln1a)
  } else if t >= 1.0 {
    Some(ln1b)
  } else {
    Some({
      x: (ln1a.x.to_double() + t * dx1).to_int64(),
      y: (ln1a.y.to_double() + t * dy1).to_int64(),
    })
  }
}

///|
/// Whether two segments cross, touching ends excluded unless `inclusive`
/// (`SegmentsIntersect`).
fn segments_intersect(
  seg1a : Point64,
  seg1b : Point64,
  seg2a : Point64,
  seg2b : Point64,
  inclusive~ : Bool = false,
) -> Bool {
  let dy1 = (seg1b.y - seg1a.y).to_double()
  let dx1 = (seg1b.x - seg1a.x).to_double()
  let dy2 = (seg2b.y - seg2a.y).to_double()
  let dx2 = (seg2b.x - seg2a.x).to_double()
  let cp = dy1 * dx2 - dy2 * dx1
  if cp == 0.0 {
    return false
  }
  let ax = (seg1a.x - seg2a.x).to_double()
  let ay = (seg1a.y - seg2a.y).to_double()
  if inclusive {
    let t = ax * dy2 - ay * dx2
    if t == 0.0 {
      return true
    }
    if t > 0.0 {
      if cp < 0.0 || t > cp {
        return false
      }
    } else if cp > 0.0 || t < cp {
      return false
    }
    let t = ax * dy1 - ay * dx1
    if t == 0.0 {
      return true
    }
    if t > 0.0 {
      cp > 0.0 && t <= cp
    } else {
      cp < 0.0 && t >= cp
    }
  } else {
    let t = ax * dy2 - ay * dx2
    if t == 0.0 {
      return false
    }
    if t > 0.0 {
      if cp < 0.0 || t >= cp {
        return false
      }
    } else if cp > 0.0 || t <= cp {
      return false
    }
    let t = ax * dy1 - ay * dx1
    if t == 0.0 {
      return false
    }
    if t > 0.0 {
      cp > 0.0 && t < cp
    } else {
      cp < 0.0 && t > cp
    }
  }
}

///|
fn get_closest_point_on_segment(
  off : Point64,
  seg1 : Point64,
  seg2 : Point64,
) -> Point64 {
  if seg1.x == seg2.x && seg1.y == seg2.y {
    return seg1
  }
  let dx = (seg2.x - seg1.x).to_double()
  let dy = (seg2.y - seg1.y).to_double()
  let q = (
      (off.x - seg1.x).to_double() * dx + (off.y - seg1.y).to_double() * dy
    ) /
    (sqr(dx) + sqr(dy))
  let q = if q < 0.0 { 0.0 } else if q > 1.0 { 1.0 } else { q }
  { x: seg1.x + nearbyint(q * dx), y: seg1.y + nearbyint(q * dy), }
}

///|
/// Where a point lies relative to a polygon (`PointInPolygonResult`).
#derive(Debug, Eq)
pub(all) enum PointInPolygonResult {
  IsOn
  IsInside
  IsOutside
}

///|
/// Whether `pt` is on, inside or outside `polygon` (`PointInPolygon`).
pub fn point_in_polygon(
  pt : Point64,
  polygon : ArrayView[Point64],
) -> PointInPolygonResult {
  let len = polygon.length()
  if len < 3 {
    return IsOutside
  }
  let mut val = 0
  let mut first = 0
  while first != len && polygon[first].y == pt.y {
    first += 1
  }
  if first == len {
    return IsOutside
  }
  let mut cend = len
  let mut is_above = polygon[first].y < pt.y
  let starting_above = is_above
  let mut curr = first + 1
  let mut prev = 0
  while true {
    if curr == cend {
      if cend == first || first == 0 {
        break
      }
      cend = first
      curr = 0
    }
    if is_above {
      while curr != cend && polygon[curr].y < pt.y {
        curr += 1
      }
      if curr == cend {
        continue
      }
    } else {
      while curr != cend && polygon[curr].y > pt.y {
        curr += 1
      }
      if curr == cend {
        continue
      }
    }
    prev = if curr == 0 { len - 1 } else { curr - 1 }
    let c = polygon[curr]
    let p = polygon[prev]
    if c.y == pt.y {
      if c.x == pt.x || (c.y == p.y && (pt.x < p.x) != (pt.x < c.x)) {
        return IsOn
      }
      curr += 1
      if curr == first {
        break
      }
      continue
    }
    if pt.x < c.x && pt.x < p.x {
      ()
    } else if pt.x > p.x && pt.x > c.x {
      val = 1 - val
    } else {
      let d = cross_product_sign(p, c, pt)
      if d == 0 {
        return IsOn
      }
      if (d < 0) == is_above {
        val = 1 - val
      }
    }
    is_above = !is_above
    curr += 1
  }
  if is_above != starting_above {
    cend = len
    if curr == cend {
      curr = 0
    }
    prev = if curr == 0 { cend - 1 } else { curr - 1 }
    let d = cross_product_sign(polygon[prev], polygon[curr], pt)
    if d == 0 {
      return IsOn
    }
    if (d < 0) == is_above {
      val = 1 - val
    }
  }
  if val == 0 {
    IsOutside
  } else {
    IsInside
  }
}

///|
/// Sorts `a` by `less`, keeping equal elements in order (`std::stable_sort`).
fn[T] stable_sort(a : Array[T], less : (T, T) -> Bool) -> Unit {
  let n = a.length()
  if n < 2 {
    return
  }
  let tmp = a.copy()
  let mut width = 1
  while width < n {
    let mut lo = 0
    while lo < n {
      let mid = @cmp.minimum(lo + width, n)
      let hi = @cmp.minimum(lo + 2 * width, n)
      let mut i = lo
      let mut j = mid
      let mut k = lo
      while i < mid && j < hi {
        if less(a[j], a[i]) {
          tmp[k] = a[j]
          j += 1
        } else {
          tmp[k] = a[i]
          i += 1
        }
        k += 1
      }
      while i < mid {
        tmp[k] = a[i]
        i += 1
        k += 1
      }
      while j < hi {
        tmp[k] = a[j]
        j += 1
        k += 1
      }
      lo = hi
    }
    for i in 0.. Bool {
  let mut pip = IsOn
  for pt in path1 {
    match point_in_polygon(pt, path2[:]) {
      IsOutside => {
        if pip == IsOutside {
          return false
        }
        pip = IsOutside
      }
      IsInside => {
        if pip == IsInside {
          return true
        }
        pip = IsInside
      }
      IsOn => ()
    }
  }
  if pip != IsInside {
    return false
  }
  let b = bounds_of(path1)
  let mid : Point64 = {
    x: (b.left + b.right) / 2L,
    y: (b.top + b.bottom) / 2L,
  }
  point_in_polygon(mid, path2[:]) == IsInside
}