Function dedupPoints

stackgl_modules/index.js:9059–9125

(floatPoints, ratPoints, floatBounds)

// Merge overlapping points
function dedupPoints (floatPoints, ratPoints, floatBounds) {
  var numPoints = ratPoints.length
  var uf = new UnionFind(numPoints)

  // Compute rational bounds
  var bounds = []
  for (var i = 0; i < ratPoints.length; ++i) {
    var p = ratPoints[i]
    var xb = boundRat(p[0])
    var yb = boundRat(p[1])
    bounds.push([
      nextafter(xb[0], -Infinity),
      nextafter(yb[0], -Infinity),
      nextafter(xb[1], Infinity),
      nextafter(yb[1], Infinity)
    ])
  }

  // Link all points with over lapping boxes
  boxIntersect(bounds, function (i, j) {
    uf.link(i, j)
  })

  // Do 1 pass over points to combine points in label sets
  var noDupes = true
  var labels = new Array(numPoints)
  for (var i = 0; i < numPoints; ++i) {
    var j = uf.find(i)
    if (j !== i) {
      // Clear no-dupes flag, zero out label
      noDupes = false
      // Make each point the top-left point from its cell
      floatPoints[j] = [
        Math.min(floatPoints[i][0], floatPoints[j][0]),
        Math.min(floatPoints[i][1], floatPoints[j][1])
      ]
    }
  }

  // If no duplicates, return null to signal termination
  if (noDupes) {
    return null
  }

  var ptr = 0
  for (var i = 0; i < numPoints; ++i) {
    var j = uf.find(i)
    if (j === i) {
      labels[i] = ptr
      floatPoints[ptr++] = floatPoints[i]
    } else {
      labels[i] = -1
    }
  }

  floatPoints.length = ptr

  // Do a second pass to fix up missing labels