Organize centroid points into Array Structure

Community Help
6

It’s a tricky problem, and what solution is viable really depends on how much those points are shifted diagonally. At least for this image though the following solution should work:

{
  // Don't mutate original array.
  const points = final_result[1].slice();
  // Sort vertically.
  points.sort((a, b) => a.y - b.y);
  // Calculate vertical jumps.
  const yDeltas = points.map((p, i, arr) => p.y - arr[i - 1]?.y || 0);
  // Find safe threshold at which to start a new row.
  const threshold = d3.bin().thresholds(2)(yDeltas).reduce((max, bin) => Math.max(max, bin.x0), 0);
  // Split points into rows.
  const rows = yDeltas.reduce((rows, d, i) => {
    // Difference exceeds threshold, create a new row.
    if(d >= threshold) rows.push([]);
    // Add point to most recent row.
    rows[rows.length - 1].push(points[i]);
    return rows;
  }, [[]]);
  // Sort by x in each row.
  rows.forEach(arr => arr.sort((a, b) => a.x - b.x));
  return rows;
}
1 Like