console.clear()

var ƒ = d3.f
var width = innerWidth
var height = innerHeight

var idToActual = {}
function hId(hEdge){
  if (!hEdge.iFace) return null

  var id = hEdge.iFace.id
  var wrongIds = []
  while (id != idToActual[id]){
    wrongIds.push(id)
    id = idToActual[id]
  }

  wrongIds.forEach(d => idToActual[d] = id)
  
  return idToActual[hEdge.iFace.id] = id
}

var container = d3.select("body").html('').append('div')
var svg = container.append('svg').at({width, height})
var tt = d3.select('body').selectAppend('div.tooltip')

var sites = window.sites || d3.range(100)
var sites = d3.range(200)
    .map(function(d){
      var rv = [Math.random() * width, Math.random() * height]
      rv.black = Math.random() < .5
      return rv;
    })

sites.forEach((d, i) => d.black = i % 2)

var polygons = d3.voronoi(sites)
  .extent([[-1, -1], [width + 1, height + 1]])
  .polygons(sites).filter(d => d)

var hEdges;
if (window.interval) interval.stop()
var interval = d3.interval(d => {
  // interval.stop()
  hEdges   = polygonsToEdges(polygons)
  polygons = edgesToPolygons(hEdges)
  console.log(hEdges.length, polygons.length)
}, 2000)
interval._call()


function polygonsToEdges(polygons){
  svg.selectAll('path')
    .transition().duration(1500)
    .remove()

  var polySel = svg.appendMany(leftSort(polygons), 'path.area')
    .at({
      d: d => 'M' + d.filter(ƒ()).join('L') + 'Z', 
      fill: d => d.data.black ? '#fff' : '#000',
      stroke: d => d.data.black ? '#fff' : '#000',
      opacity: 0
    })
    .transition().delay((d, i) => i/polygons.length*1000).duration(300)
    .at({opacity: 1})

  var hEdges = []
  var coord2hEdge = {}

  idToActual = {}
  polygons.forEach(function(poly, i){
    poly.data.id = d3.format('02')(i)
    idToActual[poly.data.id] = poly.data.id
    poly.ogID = poly.data.id
    poly.data.ogID = poly.data.id

    poly.data.removed = false
    poly.data.hEdges = poly.map(function(d, i){
      return {
        iFace: poly.data,
        origin: d
      }
    })

    poly.data.hEdges.forEach((d, i) => {
      d.next = poly.data.hEdges[mod(i + 1, poly.data.hEdges.length)]
      d.prev = poly.data.hEdges[mod(i - 1, poly.data.hEdges.length)]

      hEdges.push(d)
      coord2hEdge[d.origin + d.next.origin] = d
    })
  })

  hEdges.forEach(function(d, i){
    d.twin = coord2hEdge[d.next.origin + d.origin] || {}
    d.hIdStr = d3.format('03')(i)
    if (d.twin == d.next) throw 'up'
  })

  // remove edges between polygons of the same color
  hEdges.forEach(e => {
    if (!(e.iFace && e.twin && e.twin.iFace && e.iFace.black == e.twin.iFace.black)) return
    if (e.removed) return

    e.twin.iFace.removed = true

    var eId = hId(e)
    var start = next = knitEdge(e)

    knitEdge(e.twin)

    function knitEdge(e){
      var twinId = hId(e.twin)
      e.removed = e.twin.removed = true

      while (twinId == hId(e.next.twin)) {
        e = e.next
        e.removed = e.twin.removed = true
      }
      e.next.prev = e.twin.prev
      e.next.prev.next = e.next

      return e.next
    }

    var prev = {}

    var i = 0
    do {
      idToActual[hId(next)] = eId
      prev = next
      next = next.next
    } while (next != start && i++ < 198)
    if (i == 197) throw 'up'
  })

  hEdges.filter(d => !d.removed).forEach(d => d.faceID = hId(d))

  return hEdges.filter(d => !d.removed)
}



function edgesToPolygons(hEdges){
  hEdges.forEach(d => d.ringAdded = false)
  var byFace = d3.nestBy(hEdges, ƒ('faceID'))
  var allTriangles = []
  _.sortBy(byFace, d => d3.min(d, d => d.origin[0])).forEach((face, faceI) => {
    window.face = face
    facePolygons = []
    face.forEach(d => d.ringAdded = false)
    face.forEach(d => {
      if (d.ringAdded == true) return

      var points = []
      var start = next = d
      do {
        if (points.length > 1000) throw 'up origin'
        next.ringAdded = true
        var isXline = next.prev.origin[0] == next.origin[0] && 
                      next.origin[0] == next.next.origin[0]
        var isYline = next.prev.origin[1] == next.origin[1] && 
                      next.origin[1] == next.next.origin[1]
        if (!isXline && !isYline) points.push(next.origin)
        next = next.next
      } while (next != start && points.length < 900)

      points.isOuter = d3.polygonArea(points) > 0
      facePolygons.push(points)
    })

    var points = facePolygons.filter(d => d.isOuter)[0]

    if (!points){
      svg.appendMany(face, 'path').at({
        d: d => 'M' + d.origin  + 'L' + d.next.origin,
        stroke: 'pink',
        strokeWidth: 1
      })
      console.log(face)

      return
      throw 'up'
    }
    var holes = facePolygons.filter(d => !d.isOuter).map(d => {
      var n = points.length
      points = points.concat(d)
      return n
    })

    var earout = earcut(_.flatten(points), holes)
    var triangles = []
    earout.forEach((d, i) => {
      if (i % 3) return
      triangles.push([
        points[d], 
        points[earout[i + 2]],
        points[earout[i + 1]] 
      ])
    })

    var isBlack = face[0].iFace.black
    svg.appendMany(leftSort(triangles), 'path')
      .at({
        d: d => 'M' + d.join('L') + 'Z',
        stroke: isBlack ? '#000' : '#fff',
        stroke: '#ccc',
        fill: 'none',
        opacity: 0
      })
      .transition().duration(300).delay((d, i) => 1000 + faceI/byFace.length*1000)
      .at({opacity: 1})

    triangles.forEach(d => d.data = {black: isBlack})
    allTriangles = allTriangles.concat(triangles)
  })

  var updatedTriangles = _.shuffle(allTriangles)
    .filter((d, i) => i <= Math.ceil(.1*allTriangles.length))
  updatedTriangles.forEach(d => d.data.black = !d.data.black)

  svg.appendMany(leftSort(updatedTriangles), 'path')
    .at({
      d: d => 'M' + d.join('L') + 'Z',
      fill: d => d.data.black ? '#fff' : '#000',
      stroke: 'none',
      opacity: 0
    })
    .transition('add').delay((d, i) => 2000 + i/updatedTriangles.length*1000)
    .at({opacity: 1})

  return allTriangles
  
}

function mod(n, m){
  return ((n % m) + m) % m
}

function leftSort(array){
  return _.sortBy(array, d => d3.min(d, ƒ(0)))
}