lib/delaunay.js
function delaunayRefine(points, triangulation) {
  var stack = []

  var numPoints = points.length
  var stars = triangulation.stars
  for(var a=0; a<numPoints; ++a) {
    var star = stars[a]
    for(var j=1; j<star.length; j+=2) {
      var b = star[j]

      //If order is not consistent, then skip edge
      if(b < a) {
        continue
      }

      //Check if edge is constrained
      if(triangulation.isConstraint(a, b)) {
        continue
      }

      //Find opposite edge
      var x = star[j-1], y = -1
      for(var k=1; k<star.length; k+=2) {
        if(star[k-1] === b) {
          y = star[k]
          break
        }
      }

      //If this is a boundary edge, don't flip it
      if(y < 0) {
        continue
      }

      //If edge is in circle, flip it
      if(inCircle(points[a], points[b], points[x], points[y]) < 0) {
        stack.push(a, b)
      }
    }
  }

  while(stack.length > 0) {
    var b = stack.pop()
    var a = stack.pop()

    //Find opposite pairs
    var x = -1, y = -1
    var star = stars[a]
    for(var i=1; i<star.length; i+=2) {
      var s = star[i-1]
      var t = star[i]
      if(s === b) {
        y = t
      } else if(t === b) {
        x = s
      }
    }

    //If x/y are both valid then skip edge
    if(x < 0 || y < 0) {
      continue
    }

    //If edge is now delaunay, then don't flip it
    if(inCircle(points[a], points[b], points[x], points[y]) >= 0) {
      continue
    }

    //Flip the edge
    triangulation.flip(a, b)

    //Test flipping neighboring edges
    testFlip(points, triangulation, stack, x, a, y)
    testFlip(points, triangulation, stack, a, y, x)
    testFlip(points, triangulation, stack, y, b, x)
    testFlip(points, triangulation, stack, b, x, y)
  }
}
function delaunayRefine(points, triangulation) {
  var stack = []

  var numPoints = points.length
  var stars = triangulation.stars
  for(var a=0; a<numPoints; ++a) {
    var star = stars[a]
    for(var j=1; j<star.length; j+=2) {
      var b = star[j]

      //If order is not consistent, then skip edge
      if(b < a) {
        continue
      }

      //Check if edge is constrained
      if(triangulation.isConstraint(a, b)) {
        continue
      }

      //Find opposite edge
      var x = star[j-1], y = -1
      for(var k=1; k<star.length; k+=2) {
        if(star[k-1] === b) {
          y = star[k]
          break
        }
      }

      //If this is a boundary edge, don't flip it
      if(y < 0) {
        continue
      }

      //If edge is in circle, flip it
      if(inCircle(points[a], points[b], points[x], points[y]) < 0) {
        stack.push(a, b)
      }
    }
  }

  while(stack.length > 0) {
    var b = stack.pop()
    var a = stack.pop()

    //Find opposite pairs
    var x = -1, y = -1
    var star = stars[a]
    for(var i=1; i<star.length; i+=2) {
      var s = star[i-1]
      var t = star[i]
      if(s === b) {
        y = t
      } else if(t === b) {
        x = s
      }
    }

    //If x/y are both valid then skip edge
    if(x < 0 || y < 0) {
      continue
    }

    //If edge is now delaunay, then don't flip it
    if(inCircle(points[a], points[b], points[x], points[y]) >= 0) {
      continue
    }

    //Flip the edge
    triangulation.flip(a, b)

    //Test flipping neighboring edges
    testFlip(points, triangulation, stack, x, a, y)
    testFlip(points, triangulation, stack, a, y, x)
    testFlip(points, triangulation, stack, y, b, x)
    testFlip(points, triangulation, stack, b, x, y)
  }
}
function delaunayRefine ( points , triangulation ) { var stack = [ ] var numPoints = points . length var stars = triangulation . stars for ( var a = 0 ; a < numPoints ; ++ a ) { var star = stars [ a ] for ( var j = 1 ; j < star . length ; j += 2 ) { var b = star [ j ] //If order is not consistent, then skip edge if ( b < a ) { continue } //Check if edge is constrained if ( triangulation . isConstraint ( a , b ) ) { continue } //Find opposite edge var x = star [ j - 1 ] , y = - 1 for ( var k = 1 ; k < star . length ; k += 2 ) { if ( star [ k - 1 ] === b ) { y = star [ k ] break } } //If this is a boundary edge, don't flip it if ( y < 0 ) { continue } //If edge is in circle, flip it if ( inCircle ( points [ a ] , points [ b ] , points [ x ] , points [ y ] ) < 0 ) { stack . push ( a , b ) } } } while ( stack . length > 0 ) { var b = stack . pop ( ) var a = stack . pop ( ) //Find opposite pairs var x = - 1 , y = - 1 var star = stars [ a ] for ( var i = 1 ; i < star . length ; i += 2 ) { var s = star [ i - 1 ] var t = star [ i ] if ( s === b ) { y = t } else if ( t === b ) { x = s } } //If x/y are both valid then skip edge if ( x < 0 || y < 0 ) { continue } //If edge is now delaunay, then don't flip it if ( inCircle ( points [ a ] , points [ b ] , points [ x ] , points [ y ] ) >= 0 ) { continue } //Flip the edge triangulation . flip ( a , b ) //Test flipping neighboring edges testFlip ( points , triangulation , stack , x , a , y ) testFlip ( points , triangulation , stack , a , y , x ) testFlip ( points , triangulation , stack , y , b , x ) testFlip ( points , triangulation , stack , b , x , y ) } }
Assume edges are sorted lexicographically
Assume edges are sorted lexicographically