// A port of libtess.js 1.2.2 (https://github.com/brendankenny/libtess.js),
// itself a port of SGI's GLU tessellator, as used by p5.js's ShapeBuilder:
// nonzero winding, triangles only (edge-flag callback set), with p5's
// combine callback. Objects live in index arenas; -1 is null.
//
// SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
// Copyright (C) [dates of first publication] Silicon Graphics, Inc.
// All Rights Reserved.
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to permit
// persons to whom the Software is furnished to do so, subject to the
// following conditions:
// The above copyright notice including the dates of first publication and
// either this permission notice or a reference to
// http://oss.sgi.com/projects/FreeB/ shall be included in all copies or
// substantial portions of the Software.
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
// NO EVENT SHALL SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
// Except as contained in this notice, the name of Silicon Graphics, Inc.
// shall not be used in advertising or otherwise to promote the sale, use
// or other dealings in this Software without prior written authorization
// from Silicon Graphics, Inc.

///|
let glu_max_coord : Double = 1.0e150

///|
let sentinel_coord : Double = 4.0e150

///|
priv struct Tess {
  // half-edges (0 = eHead, 1 = eHeadSym)
  e_next : Array[Int32]
  e_sym : Array[Int32]
  e_onext : Array[Int32]
  e_lnext : Array[Int32]
  e_org : Array[Int32]
  e_lface : Array[Int32]
  e_region : Array[Int32]
  e_winding : Array[Int32]
  // vertices (0 = vHead)
  v_next : Array[Int32]
  v_prev : Array[Int32]
  v_edge : Array[Int32]
  v_x : Array[Double]
  v_y : Array[Double]
  v_z : Array[Double]
  v_s : Array[Double]
  v_t : Array[Double]
  v_pq : Array[Int32]
  v_data : Array[Int32]
  // faces (0 = fHead)
  f_next : Array[Int32]
  f_prev : Array[Int32]
  f_edge : Array[Int32]
  f_inside : Array[Bool]
  // active regions
  r_eup : Array[Int32]
  r_node : Array[Int32]
  r_winding : Array[Int32]
  r_inside : Array[Bool]
  r_sentinel : Array[Bool]
  r_dirty : Array[Bool]
  r_fix : Array[Bool]
  // dictionary nodes (0 = head)
  d_key : Array[Int32]
  d_next : Array[Int32]
  d_prev : Array[Int32]
  // vertex data (p5's 12-number vertex arrays)
  data : Array[FixedArray[Double]]
  mut event : Int32
  // priority queue
  pq_verts : Array[Int32]
  mut pq_order : Array[Int32]
  mut pq_size : Int32
  mut pq_init : Bool
  h_heap : Array[Int32]
  h_verts : Array[Int32]
  h_handles : Array[Int32]
  mut h_size : Int32
  mut h_max : Int32
  mut h_free : Int32
  mut h_init : Bool
  stride : Int32
}

///|
fn Tess::new(stride : Int32) -> Tess {
  let t : Tess = {
    e_next: [],
    e_sym: [],
    e_onext: [],
    e_lnext: [],
    e_org: [],
    e_lface: [],
    e_region: [],
    e_winding: [],
    v_next: [],
    v_prev: [],
    v_edge: [],
    v_x: [],
    v_y: [],
    v_z: [],
    v_s: [],
    v_t: [],
    v_pq: [],
    v_data: [],
    f_next: [],
    f_prev: [],
    f_edge: [],
    f_inside: [],
    r_eup: [],
    r_node: [],
    r_winding: [],
    r_inside: [],
    r_sentinel: [],
    r_dirty: [],
    r_fix: [],
    d_key: [-1],
    d_next: [0],
    d_prev: [0],
    data: [],
    event: -1,
    pq_verts: [],
    pq_order: [],
    pq_size: 0,
    pq_init: false,
    h_heap: [],
    h_verts: [-1, -1],
    h_handles: [0, 0],
    h_size: 0,
    h_max: 32,
    h_free: 0,
    h_init: false,
    stride,
  }
  // mesh heads
  ignore(t.new_vertex(0, 0))
  t.v_next[0] = 0
  t.v_prev[0] = 0
  ignore(t.new_face(0, 0))
  t.f_next[0] = 0
  t.f_prev[0] = 0
  let e = t.new_half_edge(-1)
  let es = t.new_half_edge(-1)
  t.e_next[e] = e
  t.e_next[es] = es
  t.e_sym[e] = es
  t.e_sym[es] = e
  for _ in 0..<33 {
    t.h_heap.push(0)
  }
  t.h_heap[1] = 1
  t
}

///|
fn set_at(a : Array[Int32], i : Int32, v : Int32) -> Unit {
  while a.length() <= i {
    a.push(0)
  }
  a[i] = v
}

///|
fn get_at(a : Array[Int32], i : Int32, default : Int32) -> Int32 {
  if i >= 0 && i < a.length() {
    a[i]
  } else {
    default
  }
}

///|
fn Tess::new_half_edge(self : Tess, next : Int32) -> Int32 {
  let i = self.e_next.length()
  self.e_next.push(if next < 0 { i } else { next })
  self.e_sym.push(-1)
  self.e_onext.push(-1)
  self.e_lnext.push(-1)
  self.e_org.push(-1)
  self.e_lface.push(-1)
  self.e_region.push(-1)
  self.e_winding.push(0)
  i
}

///|
fn Tess::new_vertex(self : Tess, next : Int32, prev : Int32) -> Int32 {
  let i = self.v_next.length()
  self.v_next.push(next)
  self.v_prev.push(prev)
  self.v_edge.push(-1)
  self.v_x.push(0)
  self.v_y.push(0)
  self.v_z.push(0)
  self.v_s.push(0)
  self.v_t.push(0)
  self.v_pq.push(0)
  self.v_data.push(-1)
  i
}

///|
fn Tess::new_face(self : Tess, next : Int32, prev : Int32) -> Int32 {
  let i = self.f_next.length()
  self.f_next.push(next)
  self.f_prev.push(prev)
  self.f_edge.push(-1)
  self.f_inside.push(false)
  i
}

///|
fn Tess::new_region(self : Tess) -> Int32 {
  let i = self.r_eup.length()
  self.r_eup.push(-1)
  self.r_node.push(-1)
  self.r_winding.push(0)
  self.r_inside.push(false)
  self.r_sentinel.push(false)
  self.r_dirty.push(false)
  self.r_fix.push(false)
  i
}

// ---- half-edge helpers ----

///|
fn Tess::dst(self : Tess, e : Int32) -> Int32 {
  self.e_org[self.e_sym[e]]
}

///|
fn Tess::rface(self : Tess, e : Int32) -> Int32 {
  self.e_lface[self.e_sym[e]]
}

///|
fn Tess::oprev(self : Tess, e : Int32) -> Int32 {
  self.e_lnext[self.e_sym[e]]
}

///|
fn Tess::lprev(self : Tess, e : Int32) -> Int32 {
  self.e_sym[self.e_onext[e]]
}

///|
fn Tess::rprev(self : Tess, e : Int32) -> Int32 {
  self.e_onext[self.e_sym[e]]
}

///|
fn Tess::dnext(self : Tess, e : Int32) -> Int32 {
  self.e_sym[self.rprev(e)]
}

// ---- geometry (geom.js) ----

///|
fn Tess::vert_eq(self : Tess, u : Int32, v : Int32) -> Bool {
  self.v_s[u] == self.v_s[v] && self.v_t[u] == self.v_t[v]
}

///|
fn Tess::vert_leq(self : Tess, u : Int32, v : Int32) -> Bool {
  self.v_s[u] < self.v_s[v] ||
  (self.v_s[u] == self.v_s[v] && self.v_t[u] <= self.v_t[v])
}

///|
fn Tess::edge_eval(self : Tess, u : Int32, v : Int32, w : Int32) -> Double {
  let s = self.v_s
  let t = self.v_t
  let gap_l = s[v] - s[u]
  let gap_r = s[w] - s[v]
  if gap_l + gap_r > 0 {
    if gap_l < gap_r {
      return t[v] - t[u] + (t[u] - t[w]) * (gap_l / (gap_l + gap_r))
    } else {
      return t[v] - t[w] + (t[w] - t[u]) * (gap_r / (gap_l + gap_r))
    }
  }
  0
}

///|
fn Tess::edge_sign(self : Tess, u : Int32, v : Int32, w : Int32) -> Double {
  let s = self.v_s
  let t = self.v_t
  let gap_l = s[v] - s[u]
  let gap_r = s[w] - s[v]
  if gap_l + gap_r > 0 {
    return (t[v] - t[w]) * gap_l + (t[v] - t[u]) * gap_r
  }
  0
}

///|
fn Tess::trans_leq(self : Tess, u : Int32, v : Int32) -> Bool {
  self.v_t[u] < self.v_t[v] ||
  (self.v_t[u] == self.v_t[v] && self.v_s[u] <= self.v_s[v])
}

///|
fn Tess::trans_eval(self : Tess, u : Int32, v : Int32, w : Int32) -> Double {
  let s = self.v_s
  let t = self.v_t
  let gap_l = t[v] - t[u]
  let gap_r = t[w] - t[v]
  if gap_l + gap_r > 0 {
    if gap_l < gap_r {
      return s[v] - s[u] + (s[u] - s[w]) * (gap_l / (gap_l + gap_r))
    } else {
      return s[v] - s[w] + (s[w] - s[u]) * (gap_r / (gap_l + gap_r))
    }
  }
  0
}

///|
fn Tess::trans_sign(self : Tess, u : Int32, v : Int32, w : Int32) -> Double {
  let s = self.v_s
  let t = self.v_t
  let gap_l = t[v] - t[u]
  let gap_r = t[w] - t[v]
  if gap_l + gap_r > 0 {
    return (s[v] - s[w]) * gap_l + (s[v] - s[u]) * gap_r
  }
  0
}

///|
fn Tess::edge_goes_left(self : Tess, e : Int32) -> Bool {
  self.vert_leq(self.dst(e), self.e_org[e])
}

///|
fn Tess::edge_goes_right(self : Tess, e : Int32) -> Bool {
  self.vert_leq(self.e_org[e], self.dst(e))
}

///|
fn Tess::vert_l1dist(self : Tess, u : Int32, v : Int32) -> Double {
  (self.v_s[u] - self.v_s[v]).abs() + (self.v_t[u] - self.v_t[v]).abs()
}

///|
fn interpolate(a : Double, x : Double, b : Double, y : Double) -> Double {
  let a = if a < 0 { 0.0 } else { a }
  let b = if b < 0 { 0.0 } else { b }
  if a <= b {
    if b == 0 {
      (x + y) / 2
    } else {
      x + (y - x) * (a / (a + b))
    }
  } else {
    y + (x - y) * (b / (a + b))
  }
}

///|
fn Tess::edge_intersect(
  self : Tess,
  o1 : Int32,
  d1 : Int32,
  o2 : Int32,
  d2 : Int32,
  v : Int32,
) -> Unit {
  let mut o1 = o1
  let mut d1 = d1
  let mut o2 = o2
  let mut d2 = d2
  if !self.vert_leq(o1, d1) {
    let tmp = o1
    o1 = d1
    d1 = tmp
  }
  if !self.vert_leq(o2, d2) {
    let tmp = o2
    o2 = d2
    d2 = tmp
  }
  if !self.vert_leq(o1, o2) {
    let tmp = o1
    o1 = o2
    o2 = tmp
    let tmp = d1
    d1 = d2
    d2 = tmp
  }
  if !self.vert_leq(o2, d1) {
    self.v_s[v] = (self.v_s[o2] + self.v_s[d1]) / 2
  } else if self.vert_leq(d1, d2) {
    let mut z1 = self.edge_eval(o1, o2, d1)
    let mut z2 = self.edge_eval(o2, d1, d2)
    if z1 + z2 < 0 {
      z1 = -z1
      z2 = -z2
    }
    self.v_s[v] = interpolate(z1, self.v_s[o2], z2, self.v_s[d1])
  } else {
    let mut z1 = self.edge_sign(o1, o2, d1)
    let mut z2 = -self.edge_sign(o1, d2, d1)
    if z1 + z2 < 0 {
      z1 = -z1
      z2 = -z2
    }
    self.v_s[v] = interpolate(z1, self.v_s[o2], z2, self.v_s[d2])
  }
  if !self.trans_leq(o1, d1) {
    let tmp = o1
    o1 = d1
    d1 = tmp
  }
  if !self.trans_leq(o2, d2) {
    let tmp = o2
    o2 = d2
    d2 = tmp
  }
  if !self.trans_leq(o1, o2) {
    let tmp = o1
    o1 = o2
    o2 = tmp
    let tmp = d1
    d1 = d2
    d2 = tmp
  }
  if !self.trans_leq(o2, d1) {
    self.v_t[v] = (self.v_t[o2] + self.v_t[d1]) / 2
  } else if self.trans_leq(d1, d2) {
    let mut z1 = self.trans_eval(o1, o2, d1)
    let mut z2 = self.trans_eval(o2, d1, d2)
    if z1 + z2 < 0 {
      z1 = -z1
      z2 = -z2
    }
    self.v_t[v] = interpolate(z1, self.v_t[o2], z2, self.v_t[d1])
  } else {
    let mut z1 = self.trans_sign(o1, o2, d1)
    let mut z2 = -self.trans_sign(o1, d2, d1)
    if z1 + z2 < 0 {
      z1 = -z1
      z2 = -z2
    }
    self.v_t[v] = interpolate(z1, self.v_t[o2], z2, self.v_t[d2])
  }
}

// ---- mesh (mesh.js) ----

///|
fn Tess::make_edge_pair(self : Tess, e_next : Int32) -> Int32 {
  let e = self.new_half_edge(-1)
  let es = self.new_half_edge(-1)
  let e_prev = self.e_next[self.e_sym[e_next]]
  self.e_next[es] = e_prev
  self.e_next[self.e_sym[e_prev]] = e
  self.e_next[e] = e_next
  self.e_next[self.e_sym[e_next]] = es
  self.e_sym[e] = es
  self.e_onext[e] = e
  self.e_lnext[e] = es
  self.e_sym[es] = e
  self.e_onext[es] = es
  self.e_lnext[es] = e
  e
}

///|
fn Tess::splice(self : Tess, a : Int32, b : Int32) -> Unit {
  let a_onext = self.e_onext[a]
  let b_onext = self.e_onext[b]
  self.e_lnext[self.e_sym[a_onext]] = b
  self.e_lnext[self.e_sym[b_onext]] = a
  self.e_onext[a] = b_onext
  self.e_onext[b] = a_onext
}

///|
fn Tess::make_vertex(self : Tess, e_orig : Int32, v_next : Int32) -> Unit {
  let v_prev = self.v_prev[v_next]
  let v_new = self.new_vertex(v_next, v_prev)
  self.v_next[v_prev] = v_new
  self.v_prev[v_next] = v_new
  self.v_edge[v_new] = e_orig
  let mut e = e_orig
  for ;; {
    self.e_org[e] = v_new
    e = self.e_onext[e]
    if e == e_orig {
      break
    }
  }
}

///|
fn Tess::make_face(self : Tess, e_orig : Int32, f_next : Int32) -> Unit {
  let f_prev = self.f_prev[f_next]
  let f_new = self.new_face(f_next, f_prev)
  self.f_next[f_prev] = f_new
  self.f_prev[f_next] = f_new
  self.f_edge[f_new] = e_orig
  self.f_inside[f_new] = self.f_inside[f_next]
  let mut e = e_orig
  for ;; {
    self.e_lface[e] = f_new
    e = self.e_lnext[e]
    if e == e_orig {
      break
    }
  }
}

///|
fn Tess::kill_edge(self : Tess, e_del : Int32) -> Unit {
  let e_next = self.e_next[e_del]
  let e_prev = self.e_next[self.e_sym[e_del]]
  self.e_next[self.e_sym[e_next]] = e_prev
  self.e_next[self.e_sym[e_prev]] = e_next
}

///|
fn Tess::kill_vertex(self : Tess, v_del : Int32, new_org : Int32) -> Unit {
  let e_start = self.v_edge[v_del]
  let mut e = e_start
  for ;; {
    self.e_org[e] = new_org
    e = self.e_onext[e]
    if e == e_start {
      break
    }
  }
  let v_prev = self.v_prev[v_del]
  let v_next = self.v_next[v_del]
  self.v_prev[v_next] = v_prev
  self.v_next[v_prev] = v_next
}

///|
fn Tess::kill_face(self : Tess, f_del : Int32, new_lface : Int32) -> Unit {
  let e_start = self.f_edge[f_del]
  let mut e = e_start
  for ;; {
    self.e_lface[e] = new_lface
    e = self.e_lnext[e]
    if e == e_start {
      break
    }
  }
  let f_prev = self.f_prev[f_del]
  let f_next = self.f_next[f_del]
  self.f_prev[f_next] = f_prev
  self.f_next[f_prev] = f_next
}

///|
fn Tess::make_edge_in_mesh(self : Tess) -> Int32 {
  let e = self.make_edge_pair(0)
  self.make_vertex(e, 0)
  self.make_vertex(self.e_sym[e], 0)
  self.make_face(e, 0)
  e
}

///|
fn Tess::mesh_splice(self : Tess, e_org : Int32, e_dst : Int32) -> Unit {
  if e_org == e_dst {
    return
  }
  let mut joining_loops = false
  let mut joining_vertices = false
  if self.e_org[e_dst] != self.e_org[e_org] {
    joining_vertices = true
    self.kill_vertex(self.e_org[e_dst], self.e_org[e_org])
  }
  if self.e_lface[e_dst] != self.e_lface[e_org] {
    joining_loops = true
    self.kill_face(self.e_lface[e_dst], self.e_lface[e_org])
  }
  self.splice(e_dst, e_org)
  if !joining_vertices {
    self.make_vertex(e_dst, self.e_org[e_org])
    self.v_edge[self.e_org[e_org]] = e_org
  }
  if !joining_loops {
    self.make_face(e_dst, self.e_lface[e_org])
    self.f_edge[self.e_lface[e_org]] = e_org
  }
}

///|
fn Tess::delete_edge(self : Tess, e_del : Int32) -> Unit {
  let e_del_sym = self.e_sym[e_del]
  let mut joining_loops = false
  if self.e_lface[e_del] != self.rface(e_del) {
    joining_loops = true
    self.kill_face(self.e_lface[e_del], self.rface(e_del))
  }
  if self.e_onext[e_del] == e_del {
    self.kill_vertex(self.e_org[e_del], -1)
  } else {
    self.f_edge[self.rface(e_del)] = self.oprev(e_del)
    self.v_edge[self.e_org[e_del]] = self.e_onext[e_del]
    self.splice(e_del, self.oprev(e_del))
    if !joining_loops {
      self.make_face(e_del, self.e_lface[e_del])
    }
  }
  if self.e_onext[e_del_sym] == e_del_sym {
    self.kill_vertex(self.e_org[e_del_sym], -1)
    self.kill_face(self.e_lface[e_del_sym], -1)
  } else {
    self.f_edge[self.e_lface[e_del]] = self.oprev(e_del_sym)
    self.v_edge[self.e_org[e_del_sym]] = self.e_onext[e_del_sym]
    self.splice(e_del_sym, self.oprev(e_del_sym))
  }
  self.kill_edge(e_del)
}

///|
fn Tess::add_edge_vertex(self : Tess, e_org : Int32) -> Int32 {
  let e_new = self.make_edge_pair(e_org)
  let e_new_sym = self.e_sym[e_new]
  self.splice(e_new, self.e_lnext[e_org])
  self.e_org[e_new] = self.dst(e_org)
  self.make_vertex(e_new_sym, self.e_org[e_new])
  self.e_lface[e_new] = self.e_lface[e_org]
  self.e_lface[e_new_sym] = self.e_lface[e_org]
  e_new
}

///|
fn Tess::split_edge(self : Tess, e_org : Int32) -> Int32 {
  let temp = self.add_edge_vertex(e_org)
  let e_new = self.e_sym[temp]
  let e_org_sym = self.e_sym[e_org]
  self.splice(e_org_sym, self.oprev(e_org_sym))
  self.splice(e_org_sym, e_new)
  self.e_org[e_org_sym] = self.e_org[e_new]
  self.v_edge[self.dst(e_new)] = self.e_sym[e_new]
  self.e_lface[self.e_sym[e_new]] = self.rface(e_org)
  self.e_winding[e_new] = self.e_winding[e_org]
  self.e_winding[self.e_sym[e_new]] = self.e_winding[e_org_sym]
  e_new
}

///|
fn Tess::connect(self : Tess, e_org : Int32, e_dst : Int32) -> Int32 {
  let mut joining_loops = false
  let e_new = self.make_edge_pair(e_org)
  let e_new_sym = self.e_sym[e_new]
  if self.e_lface[e_dst] != self.e_lface[e_org] {
    joining_loops = true
    self.kill_face(self.e_lface[e_dst], self.e_lface[e_org])
  }
  self.splice(e_new, self.e_lnext[e_org])
  self.splice(e_new_sym, e_dst)
  self.e_org[e_new] = self.dst(e_org)
  self.e_org[e_new_sym] = self.e_org[e_dst]
  self.e_lface[e_new] = self.e_lface[e_org]
  self.e_lface[e_new_sym] = self.e_lface[e_org]
  self.f_edge[self.e_lface[e_org]] = e_new_sym
  if !joining_loops {
    self.make_face(e_new, self.e_lface[e_org])
  }
  e_new
}

// ---- priority queue (PriorityQ + PriorityQHeap) ----

///|
fn Tess::h_float_down(self : Tess, index : Int32) -> Unit {
  let heap = self.h_heap
  let verts = self.h_verts
  let mut curr = index
  let curr_handle = get_at(heap, curr, 0)
  for ;; {
    let mut child = curr << 1
    if child < self.h_size {
      if self.vert_leq(
          get_at(verts, get_at(heap, child + 1, 0), -1),
          get_at(verts, get_at(heap, child, 0), -1),
        ) {
        child = child + 1
      }
    }
    let child_handle = get_at(heap, child, 0)
    if child > self.h_size ||
      self.vert_leq(
        get_at(verts, curr_handle, -1),
        get_at(verts, child_handle, -1),
      ) {
      set_at(heap, curr, curr_handle)
      set_at(self.h_handles, curr_handle, curr)
      return
    }
    set_at(heap, curr, child_handle)
    set_at(self.h_handles, child_handle, curr)
    curr = child
  }
}

///|
fn Tess::h_float_up(self : Tess, index : Int32) -> Unit {
  let heap = self.h_heap
  let verts = self.h_verts
  let mut curr = index
  let curr_handle = get_at(heap, curr, 0)
  for ;; {
    let parent = curr >> 1
    let parent_handle = get_at(heap, parent, 0)
    if parent == 0 ||
      self.vert_leq(
        get_at(verts, parent_handle, -1),
        get_at(verts, curr_handle, -1),
      ) {
      set_at(heap, curr, curr_handle)
      set_at(self.h_handles, curr_handle, curr)
      return
    }
    set_at(heap, curr, parent_handle)
    set_at(self.h_handles, parent_handle, curr)
    curr = parent
  }
}

///|
fn Tess::h_insert(self : Tess, vert : Int32) -> Int32 {
  self.h_size += 1
  let end = self.h_size
  if end * 2 > self.h_max {
    self.h_max *= 2
    while self.h_handles.length() < self.h_max + 1 {
      self.h_handles.push(0)
    }
  }
  let slot = if self.h_free == 0 {
    end
  } else {
    let s = self.h_free
    self.h_free = get_at(self.h_handles, s, 0)
    s
  }
  while self.h_verts.length() <= slot {
    self.h_verts.push(-1)
  }
  self.h_verts[slot] = vert
  set_at(self.h_handles, slot, end)
  set_at(self.h_heap, end, slot)
  if self.h_init {
    self.h_float_up(end)
  }
  slot
}

///|
fn Tess::h_minimum(self : Tess) -> Int32 {
  get_at(self.h_verts, get_at(self.h_heap, 1, 0), -1)
}

///|
fn Tess::h_extract_min(self : Tess) -> Int32 {
  let heap = self.h_heap
  let min_handle = get_at(heap, 1, 0)
  let min_vertex = get_at(self.h_verts, min_handle, -1)
  if self.h_size > 0 {
    set_at(heap, 1, get_at(heap, self.h_size, 0))
    set_at(self.h_handles, get_at(heap, 1, 0), 1)
    if min_handle < self.h_verts.length() {
      self.h_verts[min_handle] = -1
    }
    set_at(self.h_handles, min_handle, self.h_free)
    self.h_free = min_handle
    self.h_size -= 1
    if self.h_size > 0 {
      self.h_float_down(1)
    }
  }
  min_vertex
}

///|
fn Tess::h_remove(self : Tess, handle : Int32) -> Unit {
  let heap = self.h_heap
  let heap_index = get_at(self.h_handles, handle, 0)
  set_at(heap, heap_index, get_at(heap, self.h_size, 0))
  set_at(self.h_handles, get_at(heap, heap_index, 0), heap_index)
  self.h_size -= 1
  if heap_index <= self.h_size {
    if heap_index <= 1 {
      self.h_float_down(heap_index)
    } else {
      let vert = get_at(self.h_verts, get_at(heap, heap_index, 0), -1)
      let parent_vert = get_at(
        self.h_verts,
        get_at(heap, heap_index >> 1, 0),
        -1,
      )
      if self.vert_leq(parent_vert, vert) {
        self.h_float_down(heap_index)
      } else {
        self.h_float_up(heap_index)
      }
    }
  }
  if handle < self.h_verts.length() {
    self.h_verts[handle] = -1
  }
  set_at(self.h_handles, handle, self.h_free)
  self.h_free = handle
}

///|
fn Tess::pq_insert(self : Tess, vert : Int32) -> Int32 {
  if self.pq_init {
    return self.h_insert(vert)
  }
  let curr = self.pq_size
  self.pq_size += 1
  set_at(self.pq_verts, curr, vert)
  -(curr + 1)
}

///|
/// JavaScript's `Array.prototype.sort` with a comparator, so ties are
/// broken exactly as in p5.js.
extern "js" fn js_sort_by(
  a : FixedArray[Int32],
  cmp : (Int32, Int32) -> Int32,
) -> FixedArray[Int32] =
  #|(a, cmp) => a.sort((x, y) => cmp(x, y))

///|
fn Tess::pq_init_queue(self : Tess) -> Unit {
  let order = FixedArray::makei(self.pq_size, i => i)
  let sorted = js_sort_by(order, (a, b) => {
    if self.vert_leq(self.pq_verts[a], self.pq_verts[b]) {
      1
    } else {
      -1
    }
  })
  self.pq_order = [ for x in sorted => x ]
  self.pq_init = true
  let mut i = self.h_size
  while i >= 1 {
    self.h_float_down(i)
    i -= 1
  }
  self.h_init = true
}

///|
fn Tess::pq_vert_at_top(self : Tess) -> Int32 {
  self.pq_verts[self.pq_order[self.pq_size - 1]]
}

///|
fn Tess::pq_extract_min(self : Tess) -> Int32 {
  if self.pq_size == 0 {
    return self.h_extract_min()
  }
  let sort_min = self.pq_vert_at_top()
  if self.h_size != 0 {
    let heap_min = self.h_minimum()
    if self.vert_leq(heap_min, sort_min) {
      return self.h_extract_min()
    }
  }
  for ;; {
    self.pq_size -= 1
    if !(self.pq_size > 0 && self.pq_vert_at_top() == -1) {
      break
    }
  }
  sort_min
}

///|
fn Tess::pq_minimum(self : Tess) -> Int32 {
  if self.pq_size == 0 {
    return self.h_minimum()
  }
  let sort_min = self.pq_vert_at_top()
  if self.h_size != 0 {
    let heap_min = self.h_minimum()
    if self.vert_leq(heap_min, sort_min) {
      return heap_min
    }
  }
  sort_min
}

///|
fn Tess::pq_remove(self : Tess, handle : Int32) -> Unit {
  if handle >= 0 {
    self.h_remove(handle)
    return
  }
  let h = -(handle + 1)
  self.pq_verts[h] = -1
  while self.pq_size > 0 && self.pq_vert_at_top() == -1 {
    self.pq_size -= 1
  }
}

// ---- edge dictionary (Dict) ----

///|
fn Tess::dict_insert_before(self : Tess, node : Int32, key : Int32) -> Int32 {
  let mut node = node
  for ;; {
    node = self.d_prev[node]
    if self.d_key[node] == -1 || self.edge_leq(self.d_key[node], key) {
      break
    }
  }
  let new_node = self.d_key.length()
  self.d_key.push(key)
  self.d_next.push(self.d_next[node])
  self.d_prev.push(node)
  self.d_prev[self.d_next[node]] = new_node
  self.d_next[node] = new_node
  new_node
}

///|
fn Tess::dict_delete(self : Tess, node : Int32) -> Unit {
  self.d_prev[self.d_next[node]] = self.d_prev[node]
  self.d_next[self.d_prev[node]] = self.d_next[node]
}

///|
fn Tess::dict_search(self : Tess, key : Int32) -> Int32 {
  let mut node = 0
  for ;; {
    node = self.d_next[node]
    if self.d_key[node] == -1 || self.edge_leq(key, self.d_key[node]) {
      break
    }
  }
  node
}

///|
fn Tess::region_below(self : Tess, r : Int32) -> Int32 {
  self.d_key[self.d_prev[self.r_node[r]]]
}

///|
fn Tess::region_above(self : Tess, r : Int32) -> Int32 {
  self.d_key[self.d_next[self.r_node[r]]]
}

// ---- sweep (sweep.js) ----

///|
fn Tess::edge_leq(self : Tess, reg1 : Int32, reg2 : Int32) -> Bool {
  let event = self.event
  let e1 = self.r_eup[reg1]
  let e2 = self.r_eup[reg2]
  if self.dst(e1) == event {
    if self.dst(e2) == event {
      if self.vert_leq(self.e_org[e1], self.e_org[e2]) {
        return self.edge_sign(self.dst(e2), self.e_org[e1], self.e_org[e2]) <= 0
      }
      return self.edge_sign(self.dst(e1), self.e_org[e2], self.e_org[e1]) >= 0
    }
    return self.edge_sign(self.dst(e2), event, self.e_org[e2]) <= 0
  }
  if self.dst(e2) == event {
    return self.edge_sign(self.dst(e1), event, self.e_org[e1]) >= 0
  }
  let t1 = self.edge_eval(self.dst(e1), event, self.e_org[e1])
  let t2 = self.edge_eval(self.dst(e2), event, self.e_org[e2])
  t1 >= t2
}

///|
fn Tess::add_winding(self : Tess, e_dst : Int32, e_src : Int32) -> Unit {
  self.e_winding[e_dst] += self.e_winding[e_src]
  self.e_winding[self.e_sym[e_dst]] += self.e_winding[self.e_sym[e_src]]
}

///|
fn Tess::delete_region(self : Tess, reg : Int32) -> Unit {
  self.e_region[self.r_eup[reg]] = -1
  self.dict_delete(self.r_node[reg])
  self.r_node[reg] = -1
}

///|
fn Tess::fix_upper_edge(self : Tess, reg : Int32, new_edge : Int32) -> Unit {
  self.delete_edge(self.r_eup[reg])
  self.r_fix[reg] = false
  self.r_eup[reg] = new_edge
  self.e_region[new_edge] = reg
}

///|
fn Tess::top_left_region(self : Tess, reg : Int32) -> Int32 {
  let org = self.e_org[self.r_eup[reg]]
  let mut reg = reg
  for ;; {
    reg = self.region_above(reg)
    if self.e_org[self.r_eup[reg]] != org {
      break
    }
  }
  if self.r_fix[reg] {
    let e = self.connect(
      self.e_sym[self.r_eup[self.region_below(reg)]],
      self.e_lnext[self.r_eup[reg]],
    )
    self.fix_upper_edge(reg, e)
    reg = self.region_above(reg)
  }
  reg
}

///|
fn Tess::top_right_region(self : Tess, reg : Int32) -> Int32 {
  let dst = self.dst(self.r_eup[reg])
  let mut reg = reg
  for ;; {
    reg = self.region_above(reg)
    if self.dst(self.r_eup[reg]) != dst {
      break
    }
  }
  reg
}

///|
fn Tess::add_region_below(
  self : Tess,
  reg_above : Int32,
  e_new_up : Int32,
) -> Int32 {
  let reg_new = self.new_region()
  self.r_eup[reg_new] = e_new_up
  self.r_node[reg_new] = self.dict_insert_before(
    self.r_node[reg_above],
    reg_new,
  )
  self.e_region[e_new_up] = reg_new
  reg_new
}

///|
fn Tess::compute_winding(self : Tess, reg : Int32) -> Unit {
  self.r_winding[reg] = self.r_winding[self.region_above(reg)] +
    self.e_winding[self.r_eup[reg]]
  self.r_inside[reg] = self.r_winding[reg] != 0
}

///|
fn Tess::finish_region(self : Tess, reg : Int32) -> Unit {
  let e = self.r_eup[reg]
  let f = self.e_lface[e]
  self.f_inside[f] = self.r_inside[reg]
  self.f_edge[f] = e
  self.delete_region(reg)
}

///|
fn Tess::finish_left_regions(
  self : Tess,
  reg_first : Int32,
  reg_last : Int32,
) -> Int32 {
  let mut reg_prev = reg_first
  let mut e_prev = self.r_eup[reg_first]
  while reg_prev != reg_last {
    self.r_fix[reg_prev] = false
    let reg = self.region_below(reg_prev)
    let mut e = self.r_eup[reg]
    if self.e_org[e] != self.e_org[e_prev] {
      if !self.r_fix[reg] {
        self.finish_region(reg_prev)
        break
      }
      e = self.connect(self.lprev(e_prev), self.e_sym[e])
      self.fix_upper_edge(reg, e)
    }
    if self.e_onext[e_prev] != e {
      self.mesh_splice(self.oprev(e), e)
      self.mesh_splice(e_prev, e)
    }
    self.finish_region(reg_prev)
    e_prev = self.r_eup[reg]
    reg_prev = reg
  }
  e_prev
}

///|
fn Tess::add_right_edges(
  self : Tess,
  reg_up : Int32,
  e_first : Int32,
  e_last : Int32,
  e_top_left : Int32,
  clean_up : Bool,
) -> Unit {
  let mut first_time = true
  let mut e = e_first
  for ;; {
    ignore(self.add_region_below(reg_up, self.e_sym[e]))
    e = self.e_onext[e]
    if e == e_last {
      break
    }
  }
  let e_top_left = if e_top_left == -1 {
    self.rprev(self.r_eup[self.region_below(reg_up)])
  } else {
    e_top_left
  }
  let mut reg_prev = reg_up
  let mut e_prev = e_top_left
  for ;; {
    let reg = self.region_below(reg_prev)
    e = self.e_sym[self.r_eup[reg]]
    if self.e_org[e] != self.e_org[e_prev] {
      break
    }
    if self.e_onext[e] != e_prev {
      self.mesh_splice(self.oprev(e), e)
      self.mesh_splice(self.oprev(e_prev), e)
    }
    self.r_winding[reg] = self.r_winding[reg_prev] - self.e_winding[e]
    self.r_inside[reg] = self.r_winding[reg] != 0
    self.r_dirty[reg_prev] = true
    if !first_time && self.check_for_right_splice(reg_prev) {
      self.add_winding(e, e_prev)
      self.delete_region(reg_prev)
      self.delete_edge(e_prev)
    }
    first_time = false
    reg_prev = reg
    e_prev = e
  }
  self.r_dirty[reg_prev] = true
  if clean_up {
    self.walk_dirty_regions(reg_prev)
  }
}

///|
/// p5's combine callback: a weighted sum of the vertices' data arrays.
fn Tess::combine(
  self : Tess,
  data : Array[Int32],
  weights : Array[Double],
) -> Int32 {
  let result = FixedArray::make(self.stride, 0.0)
  for i in 0.. Unit {
  let data = [self.v_data[self.e_org[e1]], self.v_data[self.e_org[e2]], -1, -1]
  self.v_data[self.e_org[e1]] = self.combine(data, [0.5, 0.5, 0, 0])
  self.mesh_splice(e1, e2)
}

///|
fn Tess::vertex_weights(
  self : Tess,
  isect : Int32,
  org : Int32,
  dst : Int32,
  weights : Array[Double],
  wi : Int32,
) -> Unit {
  let t1 = self.vert_l1dist(org, isect)
  let t2 = self.vert_l1dist(dst, isect)
  weights[wi] = 0.5 * t2 / (t1 + t2)
  weights[wi + 1] = 0.5 * t1 / (t1 + t2)
  self.v_x[isect] += weights[wi] * self.v_x[org] +
    weights[wi + 1] * self.v_x[dst]
  self.v_y[isect] += weights[wi] * self.v_y[org] +
    weights[wi + 1] * self.v_y[dst]
  self.v_z[isect] += weights[wi] * self.v_z[org] +
    weights[wi + 1] * self.v_z[dst]
}

///|
fn Tess::get_intersect_data(
  self : Tess,
  isect : Int32,
  org_up : Int32,
  dst_up : Int32,
  org_lo : Int32,
  dst_lo : Int32,
) -> Unit {
  let weights = [0.0, 0, 0, 0]
  let data = [
    self.v_data[org_up],
    self.v_data[dst_up],
    self.v_data[org_lo],
    self.v_data[dst_lo],
  ]
  self.v_x[isect] = 0
  self.v_y[isect] = 0
  self.v_z[isect] = 0
  self.vertex_weights(isect, org_up, dst_up, weights, 0)
  self.vertex_weights(isect, org_lo, dst_lo, weights, 2)
  self.v_data[isect] = self.combine(data, weights)
}

///|
fn Tess::check_for_right_splice(self : Tess, reg_up : Int32) -> Bool {
  let reg_lo = self.region_below(reg_up)
  let e_up = self.r_eup[reg_up]
  let e_lo = self.r_eup[reg_lo]
  if self.vert_leq(self.e_org[e_up], self.e_org[e_lo]) {
    if self.edge_sign(self.dst(e_lo), self.e_org[e_up], self.e_org[e_lo]) > 0 {
      return false
    }
    if !self.vert_eq(self.e_org[e_up], self.e_org[e_lo]) {
      ignore(self.split_edge(self.e_sym[e_lo]))
      self.mesh_splice(e_up, self.oprev(e_lo))
      self.r_dirty[reg_up] = true
      self.r_dirty[reg_lo] = true
    } else if self.e_org[e_up] != self.e_org[e_lo] {
      self.pq_remove(self.v_pq[self.e_org[e_up]])
      self.splice_merge_vertices(self.oprev(e_lo), e_up)
    }
  } else {
    if self.edge_sign(self.dst(e_up), self.e_org[e_lo], self.e_org[e_up]) < 0 {
      return false
    }
    self.r_dirty[self.region_above(reg_up)] = true
    self.r_dirty[reg_up] = true
    ignore(self.split_edge(self.e_sym[e_up]))
    self.mesh_splice(self.oprev(e_lo), e_up)
  }
  true
}

///|
fn Tess::check_for_left_splice(self : Tess, reg_up : Int32) -> Bool {
  let reg_lo = self.region_below(reg_up)
  let e_up = self.r_eup[reg_up]
  let e_lo = self.r_eup[reg_lo]
  if self.vert_leq(self.dst(e_up), self.dst(e_lo)) {
    if self.edge_sign(self.dst(e_up), self.dst(e_lo), self.e_org[e_up]) < 0 {
      return false
    }
    self.r_dirty[self.region_above(reg_up)] = true
    self.r_dirty[reg_up] = true
    let e = self.split_edge(e_up)
    self.mesh_splice(self.e_sym[e_lo], e)
    self.f_inside[self.e_lface[e]] = self.r_inside[reg_up]
  } else {
    if self.edge_sign(self.dst(e_lo), self.dst(e_up), self.e_org[e_lo]) > 0 {
      return false
    }
    self.r_dirty[reg_up] = true
    self.r_dirty[reg_lo] = true
    let e = self.split_edge(e_lo)
    self.mesh_splice(self.e_lnext[e_up], self.e_sym[e_lo])
    self.f_inside[self.rface(e)] = self.r_inside[reg_up]
  }
  true
}

///|
fn Tess::check_for_intersect(self : Tess, reg_up : Int32) -> Bool {
  let mut reg_up = reg_up
  let mut reg_lo = self.region_below(reg_up)
  let mut e_up = self.r_eup[reg_up]
  let mut e_lo = self.r_eup[reg_lo]
  let org_up = self.e_org[e_up]
  let org_lo = self.e_org[e_lo]
  let dst_up = self.dst(e_up)
  let dst_lo = self.dst(e_lo)
  let isect = self.new_vertex(-1, -1)
  if org_up == org_lo {
    return false
  }
  let t_min_up = self.v_t[org_up].min(self.v_t[dst_up])
  let t_max_lo = self.v_t[org_lo].max(self.v_t[dst_lo])
  if t_min_up > t_max_lo {
    return false
  }
  if self.vert_leq(org_up, org_lo) {
    if self.edge_sign(dst_lo, org_up, org_lo) > 0 {
      return false
    }
  } else if self.edge_sign(dst_up, org_lo, org_up) < 0 {
    return false
  }
  self.edge_intersect(dst_up, org_up, dst_lo, org_lo, isect)
  let event = self.event
  if self.vert_leq(isect, event) {
    self.v_s[isect] = self.v_s[event]
    self.v_t[isect] = self.v_t[event]
  }
  let org_min = if self.vert_leq(org_up, org_lo) { org_up } else { org_lo }
  if self.vert_leq(org_min, isect) {
    self.v_s[isect] = self.v_s[org_min]
    self.v_t[isect] = self.v_t[org_min]
  }
  if self.vert_eq(isect, org_up) || self.vert_eq(isect, org_lo) {
    ignore(self.check_for_right_splice(reg_up))
    return false
  }
  if (!self.vert_eq(dst_up, event) && self.edge_sign(dst_up, event, isect) >= 0) ||
    (!self.vert_eq(dst_lo, event) && self.edge_sign(dst_lo, event, isect) <= 0) {
    if dst_lo == event {
      ignore(self.split_edge(self.e_sym[e_up]))
      self.mesh_splice(self.e_sym[e_lo], e_up)
      reg_up = self.top_left_region(reg_up)
      e_up = self.r_eup[self.region_below(reg_up)]
      ignore(self.finish_left_regions(self.region_below(reg_up), reg_lo))
      self.add_right_edges(reg_up, self.oprev(e_up), e_up, e_up, true)
      return true
    }
    if dst_up == event {
      ignore(self.split_edge(self.e_sym[e_lo]))
      self.mesh_splice(self.e_lnext[e_up], self.oprev(e_lo))
      reg_lo = reg_up
      reg_up = self.top_right_region(reg_up)
      let e = self.rprev(self.r_eup[self.region_below(reg_up)])
      self.r_eup[reg_lo] = self.oprev(e_lo)
      e_lo = self.finish_left_regions(reg_lo, -1)
      self.add_right_edges(
        reg_up,
        self.e_onext[e_lo],
        self.rprev(e_up),
        e,
        true,
      )
      return true
    }
    if self.edge_sign(dst_up, event, isect) >= 0 {
      self.r_dirty[self.region_above(reg_up)] = true
      self.r_dirty[reg_up] = true
      ignore(self.split_edge(self.e_sym[e_up]))
      self.v_s[self.e_org[e_up]] = self.v_s[event]
      self.v_t[self.e_org[e_up]] = self.v_t[event]
    }
    if self.edge_sign(dst_lo, event, isect) <= 0 {
      self.r_dirty[reg_up] = true
      self.r_dirty[reg_lo] = true
      ignore(self.split_edge(self.e_sym[e_lo]))
      self.v_s[self.e_org[e_lo]] = self.v_s[event]
      self.v_t[self.e_org[e_lo]] = self.v_t[event]
    }
    return false
  }
  ignore(self.split_edge(self.e_sym[e_up]))
  ignore(self.split_edge(self.e_sym[e_lo]))
  self.mesh_splice(self.oprev(e_lo), e_up)
  let v = self.e_org[e_up]
  self.v_s[v] = self.v_s[isect]
  self.v_t[v] = self.v_t[isect]
  self.v_pq[v] = self.pq_insert(v)
  self.get_intersect_data(v, org_up, dst_up, org_lo, dst_lo)
  self.r_dirty[self.region_above(reg_up)] = true
  self.r_dirty[reg_up] = true
  self.r_dirty[reg_lo] = true
  false
}

///|
fn Tess::walk_dirty_regions(self : Tess, reg_up : Int32) -> Unit {
  let mut reg_up = reg_up
  let mut reg_lo = self.region_below(reg_up)
  for ;; {
    while self.r_dirty[reg_lo] {
      reg_up = reg_lo
      reg_lo = self.region_below(reg_lo)
    }
    if !self.r_dirty[reg_up] {
      reg_lo = reg_up
      reg_up = self.region_above(reg_up)
      if reg_up == -1 || !self.r_dirty[reg_up] {
        return
      }
    }
    self.r_dirty[reg_up] = false
    let mut e_up = self.r_eup[reg_up]
    let mut e_lo = self.r_eup[reg_lo]
    if self.dst(e_up) != self.dst(e_lo) {
      if self.check_for_left_splice(reg_up) {
        if self.r_fix[reg_lo] {
          self.delete_region(reg_lo)
          self.delete_edge(e_lo)
          reg_lo = self.region_below(reg_up)
          e_lo = self.r_eup[reg_lo]
        } else if self.r_fix[reg_up] {
          self.delete_region(reg_up)
          self.delete_edge(e_up)
          reg_up = self.region_above(reg_lo)
          e_up = self.r_eup[reg_up]
        }
      }
    }
    if self.e_org[e_up] != self.e_org[e_lo] {
      if self.dst(e_up) != self.dst(e_lo) &&
        !self.r_fix[reg_up] &&
        !self.r_fix[reg_lo] &&
        (self.dst(e_up) == self.event || self.dst(e_lo) == self.event) {
        if self.check_for_intersect(reg_up) {
          return
        }
      } else {
        ignore(self.check_for_right_splice(reg_up))
      }
    }
    if self.e_org[e_up] == self.e_org[e_lo] && self.dst(e_up) == self.dst(e_lo) {
      self.add_winding(e_lo, e_up)
      self.delete_region(reg_up)
      self.delete_edge(e_up)
      reg_up = self.region_above(reg_lo)
    }
  }
}

///|
fn Tess::connect_right_vertex(
  self : Tess,
  reg_up : Int32,
  e_bottom_left : Int32,
) -> Unit {
  let mut reg_up = reg_up
  let mut e_bottom_left = e_bottom_left
  let mut e_top_left = self.e_onext[e_bottom_left]
  let reg_lo = self.region_below(reg_up)
  let e_up = self.r_eup[reg_up]
  let e_lo = self.r_eup[reg_lo]
  let mut degenerate = false
  if self.dst(e_up) != self.dst(e_lo) {
    ignore(self.check_for_intersect(reg_up))
  }
  if self.vert_eq(self.e_org[e_up], self.event) {
    self.mesh_splice(self.oprev(e_top_left), e_up)
    reg_up = self.top_left_region(reg_up)
    e_top_left = self.r_eup[self.region_below(reg_up)]
    ignore(self.finish_left_regions(self.region_below(reg_up), reg_lo))
    degenerate = true
  }
  if self.vert_eq(self.e_org[e_lo], self.event) {
    self.mesh_splice(e_bottom_left, self.oprev(e_lo))
    e_bottom_left = self.finish_left_regions(reg_lo, -1)
    degenerate = true
  }
  if degenerate {
    self.add_right_edges(
      reg_up,
      self.e_onext[e_bottom_left],
      e_top_left,
      e_top_left,
      true,
    )
    return
  }
  let e_new = if self.vert_leq(self.e_org[e_lo], self.e_org[e_up]) {
    self.oprev(e_lo)
  } else {
    e_up
  }
  let e_new = self.connect(self.lprev(e_bottom_left), e_new)
  self.add_right_edges(
    reg_up,
    e_new,
    self.e_onext[e_new],
    self.e_onext[e_new],
    false,
  )
  self.r_fix[self.e_region[self.e_sym[e_new]]] = true
  self.walk_dirty_regions(reg_up)
}

///|
fn Tess::connect_left_degenerate(
  self : Tess,
  reg_up : Int32,
  v_event : Int32,
) -> Unit {
  let e = self.r_eup[reg_up]
  if self.vert_eq(self.e_org[e], v_event) {
    return
  }
  if !self.vert_eq(self.dst(e), v_event) {
    ignore(self.split_edge(self.e_sym[e]))
    if self.r_fix[reg_up] {
      self.delete_edge(self.e_onext[e])
      self.r_fix[reg_up] = false
    }
    self.mesh_splice(self.v_edge[v_event], e)
    self.sweep_event(v_event)
    return
  }
}

///|
fn Tess::connect_left_vertex(self : Tess, v_event : Int32) -> Unit {
  let tmp = self.new_region()
  self.r_eup[tmp] = self.e_sym[self.v_edge[v_event]]
  let reg_up = self.d_key[self.dict_search(tmp)]
  let reg_lo = self.region_below(reg_up)
  let e_up = self.r_eup[reg_up]
  let e_lo = self.r_eup[reg_lo]
  if self.edge_sign(self.dst(e_up), v_event, self.e_org[e_up]) == 0 {
    self.connect_left_degenerate(reg_up, v_event)
    return
  }
  let reg = if self.vert_leq(self.dst(e_lo), self.dst(e_up)) {
    reg_up
  } else {
    reg_lo
  }
  if self.r_inside[reg_up] || self.r_fix[reg] {
    let e_new = if reg == reg_up {
      self.connect(self.e_sym[self.v_edge[v_event]], self.e_lnext[e_up])
    } else {
      self.e_sym[self.connect(self.dnext(e_lo), self.v_edge[v_event])]
    }
    if self.r_fix[reg] {
      self.fix_upper_edge(reg, e_new)
    } else {
      self.compute_winding(self.add_region_below(reg_up, e_new))
    }
    self.sweep_event(v_event)
  } else {
    self.add_right_edges(
      reg_up,
      self.v_edge[v_event],
      self.v_edge[v_event],
      -1,
      true,
    )
  }
}

///|
fn Tess::sweep_event(self : Tess, v_event : Int32) -> Unit {
  self.event = v_event
  let mut e = self.v_edge[v_event]
  while self.e_region[e] == -1 {
    e = self.e_onext[e]
    if e == self.v_edge[v_event] {
      self.connect_left_vertex(v_event)
      return
    }
  }
  let reg_up = self.top_left_region(self.e_region[e])
  let reg = self.region_below(reg_up)
  let e_top_left = self.r_eup[reg]
  let e_bottom_left = self.finish_left_regions(reg, -1)
  if self.e_onext[e_bottom_left] == e_top_left {
    self.connect_right_vertex(reg_up, e_bottom_left)
  } else {
    self.add_right_edges(
      reg_up,
      self.e_onext[e_bottom_left],
      e_top_left,
      e_top_left,
      true,
    )
  }
}

///|
fn Tess::add_sentinel(self : Tess, t : Double) -> Unit {
  let reg = self.new_region()
  let e = self.make_edge_in_mesh()
  self.v_s[self.e_org[e]] = sentinel_coord
  self.v_t[self.e_org[e]] = t
  self.v_s[self.dst(e)] = -sentinel_coord
  self.v_t[self.dst(e)] = t
  self.event = self.dst(e)
  self.r_eup[reg] = e
  self.r_winding[reg] = 0
  self.r_inside[reg] = false
  self.r_fix[reg] = false
  self.r_sentinel[reg] = true
  self.r_dirty[reg] = false
  self.r_node[reg] = self.dict_insert_before(0, reg)
}

///|
fn Tess::remove_degenerate_edges(self : Tess) -> Unit {
  let e_head = 0
  let mut e = self.e_next[e_head]
  while e != e_head {
    let mut e_next = self.e_next[e]
    let mut e_lnext = self.e_lnext[e]
    if self.vert_eq(self.e_org[e], self.dst(e)) &&
      self.e_lnext[self.e_lnext[e]] != e {
      self.splice_merge_vertices(e_lnext, e)
      self.delete_edge(e)
      e = e_lnext
      e_lnext = self.e_lnext[e]
    }
    if self.e_lnext[e_lnext] == e {
      if e_lnext != e {
        if e_lnext == e_next || e_lnext == self.e_sym[e_next] {
          e_next = self.e_next[e_next]
        }
        self.delete_edge(e_lnext)
      }
      if e == e_next || e == self.e_sym[e_next] {
        e_next = self.e_next[e_next]
      }
      self.delete_edge(e)
    }
    e = e_next
  }
}

///|
fn Tess::remove_degenerate_faces(self : Tess) -> Unit {
  let mut f = self.f_next[0]
  while f != 0 {
    let f_next = self.f_next[f]
    let e = self.f_edge[f]
    if self.e_lnext[self.e_lnext[e]] == e {
      self.add_winding(self.e_onext[e], e)
      self.delete_edge(e)
    }
    f = f_next
  }
}

///|
fn Tess::compute_interior(self : Tess) -> Unit {
  self.remove_degenerate_edges()
  // initPriorityQ
  let mut v = self.v_next[0]
  while v != 0 {
    self.v_pq[v] = self.pq_insert(v)
    v = self.v_next[v]
  }
  self.pq_init_queue()
  // initEdgeDict
  self.add_sentinel(-sentinel_coord)
  self.add_sentinel(sentinel_coord)
  for ;; {
    let v = self.pq_extract_min()
    if v == -1 {
      break
    }
    for ;; {
      let v_next = self.pq_minimum()
      if v_next == -1 || !self.vert_eq(v_next, v) {
        break
      }
      let v_next = self.pq_extract_min()
      self.splice_merge_vertices(self.v_edge[v], self.v_edge[v_next])
    }
    self.sweep_event(v)
  }
  let min_region = self.d_key[self.d_next[0]]
  self.event = self.e_org[self.r_eup[min_region]]
  // doneEdgeDict
  for ;; {
    let reg = self.d_key[self.d_next[0]]
    if reg == -1 {
      break
    }
    self.delete_region(reg)
  }
  self.remove_degenerate_faces()
}

// ---- monotone tessellation (tessmono.js) ----

///|
fn Tess::tessellate_mono_region(self : Tess, face : Int32) -> Unit {
  let mut up = self.f_edge[face]
  while self.vert_leq(self.dst(up), self.e_org[up]) {
    up = self.lprev(up)
  }
  while self.vert_leq(self.e_org[up], self.dst(up)) {
    up = self.e_lnext[up]
  }
  let mut lo = self.lprev(up)
  while self.e_lnext[up] != lo {
    if self.vert_leq(self.dst(up), self.e_org[lo]) {
      while self.e_lnext[lo] != up &&
            (
              self.edge_goes_left(self.e_lnext[lo]) ||
              self.edge_sign(
                self.e_org[lo],
                self.dst(lo),
                self.dst(self.e_lnext[lo]),
              ) <=
              0
            ) {
        lo = self.e_sym[self.connect(self.e_lnext[lo], lo)]
      }
      lo = self.lprev(lo)
    } else {
      while self.e_lnext[lo] != up &&
            (
              self.edge_goes_right(self.lprev(up)) ||
              self.edge_sign(
                self.dst(up),
                self.e_org[up],
                self.e_org[self.lprev(up)],
              ) >=
              0
            ) {
        up = self.e_sym[self.connect(up, self.lprev(up))]
      }
      up = self.e_lnext[up]
    }
  }
  while self.e_lnext[self.e_lnext[lo]] != up {
    lo = self.e_sym[self.connect(self.e_lnext[lo], lo)]
  }
}

///|
fn Tess::tessellate_interior(self : Tess) -> Unit {
  let mut f = self.f_next[0]
  while f != 0 {
    let next = self.f_next[f]
    if self.f_inside[f] {
      self.tessellate_mono_region(f)
    }
    f = next
  }
}

// ---- normal and projection (normal.js) ----

///|
fn long_axis(v : FixedArray[Double]) -> Int32 {
  let mut i = 0
  if v[1].abs() > v[0].abs() {
    i = 1
  }
  if v[2].abs() > v[i].abs() {
    i = 2
  }
  i
}

///|
fn Tess::coord(self : Tess, v : Int32, i : Int32) -> Double {
  match i {
    0 => self.v_x[v]
    1 => self.v_y[v]
    _ => self.v_z[v]
  }
}

///|
fn Tess::compute_normal(self : Tess, norm : FixedArray[Double]) -> Unit {
  let max_val = FixedArray::make(3, -2.0 * glu_max_coord)
  let min_val = FixedArray::make(3, 2.0 * glu_max_coord)
  let max_vert = FixedArray::make(3, -1)
  let min_vert = FixedArray::make(3, -1)
  let mut v = self.v_next[0]
  while v != 0 {
    for i in 0..<3 {
      let c = self.coord(v, i)
      if c < min_val[i] {
        min_val[i] = c
        min_vert[i] = v
      }
      if c > max_val[i] {
        max_val[i] = c
        max_vert[i] = v
      }
    }
    v = self.v_next[v]
  }
  let mut index = 0
  if max_val[1] - min_val[1] > max_val[0] - min_val[0] {
    index = 1
  }
  if max_val[2] - min_val[2] > max_val[index] - min_val[index] {
    index = 2
  }
  if min_val[index] >= max_val[index] {
    norm[0] = 0
    norm[1] = 0
    norm[2] = 1
    return
  }
  let mut max_len2 = 0.0
  let v1 = min_vert[index]
  let v2 = max_vert[index]
  let d1 : FixedArray[Double] = [
    self.v_x[v1] - self.v_x[v2],
    self.v_y[v1] - self.v_y[v2],
    self.v_z[v1] - self.v_z[v2],
  ]
  let mut v = self.v_next[0]
  while v != 0 {
    let d20 = self.v_x[v] - self.v_x[v2]
    let d21 = self.v_y[v] - self.v_y[v2]
    let d22 = self.v_z[v] - self.v_z[v2]
    let t0 = d1[1] * d22 - d1[2] * d21
    let t1 = d1[2] * d20 - d1[0] * d22
    let t2 = d1[0] * d21 - d1[1] * d20
    let len2 = t0 * t0 + t1 * t1 + t2 * t2
    if len2 > max_len2 {
      max_len2 = len2
      norm[0] = t0
      norm[1] = t1
      norm[2] = t2
    }
    v = self.v_next[v]
  }
  if max_len2 <= 0 {
    norm[0] = 0
    norm[1] = 0
    norm[2] = 0
    norm[long_axis(d1)] = 1
  }
}

///|
fn Tess::check_orientation(self : Tess) -> Unit {
  let mut area = 0.0
  let mut f = self.f_next[0]
  while f != 0 {
    let mut e = self.f_edge[f]
    if self.e_winding[e] > 0 {
      for ;; {
        area += (self.v_s[self.e_org[e]] - self.v_s[self.dst(e)]) *
          (self.v_t[self.e_org[e]] + self.v_t[self.dst(e)])
        e = self.e_lnext[e]
        if e == self.f_edge[f] {
          break
        }
      }
    }
    f = self.f_next[f]
  }
  if area < 0 {
    let mut v = self.v_next[0]
    while v != 0 {
      self.v_t[v] = -self.v_t[v]
      v = self.v_next[v]
    }
  }
}

///|
fn Tess::project_polygon(
  self : Tess,
  nx : Double,
  ny : Double,
  nz : Double,
) -> Unit {
  let norm : FixedArray[Double] = [nx, ny, nz]
  let mut computed = false
  if nx == 0 && ny == 0 && nz == 0 {
    self.compute_normal(norm)
    computed = true
  }
  let i = long_axis(norm)
  let s_axis = (i + 1) % 3
  let t_axis = (i + 2) % 3
  let t_negate = if norm[i] > 0 { 1.0 } else { -1.0 }
  let mut v = self.v_next[0]
  while v != 0 {
    self.v_s[v] = self.coord(v, s_axis)
    self.v_t[v] = t_negate * self.coord(v, t_axis)
    v = self.v_next[v]
  }
  if computed {
    self.check_orientation()
  }
}

///|
/// Tessellates contours of p5 vertex arrays (`x, y, z` first) like p5's
/// `_triangulate` with libtess (nonzero winding, triangles). Returns the
/// flattened triangle vertex data.
pub fn libtess_triangulate(
  contours : Array[Array[FixedArray[Double]]],
  stride : Int32,
) -> Array[Double] {
  let t = Tess::new(stride)
  // gluTessNormal: (0, 0, 1) when every vertex has the same z
  let z = contours.get(0).bind(c => c.get(0)).map(a => a[2])
  let mut all_same_z = true
  for c in contours {
    for a in c {
      if Some(a[2]) != z {
        all_same_z = false
        break
      }
    }
  }
  // gluTessBeginPolygon / contours / vertices
  for c in contours {
    let mut last = -1
    for a in c {
      let coords = [a[0], a[1], a[2]].map(x => {
        x.clamp(min=-glu_max_coord, max=glu_max_coord)
      })
      let e = if last == -1 {
        let e = t.make_edge_in_mesh()
        t.mesh_splice(e, t.e_sym[e])
        e
      } else {
        ignore(t.split_edge(last))
        t.e_lnext[last]
      }
      let v = t.e_org[e]
      t.data.push(a)
      t.v_data[v] = t.data.length() - 1
      t.v_x[v] = coords[0]
      t.v_y[v] = coords[1]
      t.v_z[v] = coords[2]
      t.e_winding[e] = 1
      t.e_winding[t.e_sym[e]] = -1
      last = e
    }
  }
  // gluTessEndPolygon
  if all_same_z {
    t.project_polygon(0, 0, 1)
  } else {
    t.project_polygon(0, 0, 0)
  }
  t.compute_interior()
  t.tessellate_interior()
  // renderMesh: faces in reverse order
  let out : Array[Double] = []
  let mut f = t.f_prev[0]
  while f != 0 {
    if t.f_inside[f] {
      let mut e = t.f_edge[f]
      for ;; {
        let d = t.v_data[t.e_org[e]]
        if d >= 0 {
          for x in t.data[d] {
            out.push(x)
          }
        }
        e = t.e_lnext[e]
        if e == t.f_edge[f] {
          break
        }
      }
    }
    f = t.f_prev[f]
  }
  out
}