void naiveXYCluster()

in libraries/hvvr/raycaster/sample_clustering.h [18:49]

• 26 lines of code
• 8 McCabe index (conditional complexity)

void naiveXYCluster(ArrayView<PointClass> samples, size_t k) {
    size_t yStrata = (size_t)sqrt(k);
    size_t xStrata = (k + yStrata - 1) / yStrata;

    size_t tilesPerBlock = TILES_PER_BLOCK;
    size_t blockYStrata = (size_t)sqrt(tilesPerBlock);
    size_t blockXStrata = (tilesPerBlock + blockYStrata - 1) / blockYStrata;

    auto yThenXComparator = [](const PointClass& a, const PointClass& b) {
        return (a.position.y < b.position.y) || (a.position.y == b.position.y && a.position.x < b.position.x);
    };
    auto xThenYComparator = [](const PointClass& a, const PointClass& b) {
        return (a.position.x < b.position.x) || (a.position.x == b.position.x && a.position.y < b.position.y);
    };

    std::sort(samples.begin(), samples.end(), yThenXComparator);

    for (size_t i = 0; i < yStrata; ++i) {
        std::sort(samples.begin() + (i * BLOCK_SIZE * xStrata),
                  samples.begin() + std::min(((i + 1) * BLOCK_SIZE * xStrata), samples.size()), xThenYComparator);
    }

    for (size_t i = 0; i < k; ++i) {
        std::sort(samples.begin() + (i * BLOCK_SIZE),
                  samples.begin() + std::min(((i + 1) * BLOCK_SIZE), samples.size()), yThenXComparator);
    }

    for (size_t i = 0; i < samples.size(); i += TILE_SIZE * blockXStrata) {
        std::sort(samples.begin() + i, samples.begin() + std::min(i + TILE_SIZE * blockXStrata, samples.size()),
                  xThenYComparator);
    }
}