Question about grid radius calculation in nearest neighbor search

[sergcpp]

Hey! Apologies in advance if I’m overlooking something obvious - I’ve been reading through the code to better understand the logic and came across this line in the nearest neighbor search:

const double grid_radius = grid_size * (i + 0.7072);

From my understanding, the early exit condition needs to account for the worst-case scenario where the sample lies exactly in the corner of a grid cell. In that case, we can only break the loop if we found the point within the inscribed circle. So adding sqrt(0.5) (0.7072) to the search range seems incorrect.

Here’s an illustration of what I mean:

To validate my thinking, I added a brute-force check after the original loop:

double min_dist_sq2 = 2.0;
for (int y = 0; y < dim; ++y) {
  for (int x = 0; x < dim; ++x) {
      if (x == x_pos && y == y_pos) {
          continue;
      }
      UpdateMinDistSqWithPointInCell(sample, sample_grid, x, y, dim, &min_dist_sq2);
      assert(min_dist_sq <= min_dist_sq2 || min_dist_sq < max_min_dist_sq);
  }
}

This ensures no closer point is missed. The assertion would fail when + sqrt(0.5) is present, but it no longer fails once that addition is removed - which suggests the search radius may be slightly too large otherwise.

It's not a huge difference in practice though - here’s a comparison of 4096 samples with 100 candidates and the same seed:

I should probably try to compare the 'bluenoisiness' of before/after. But decided to ask first. Could you clarify if I’m correct in this reasoning? Thanks so much!