Skip to content

Spatial_sorting: middle-policy refinement stops while points remain separable #9769

Open

Description

Issue Details

Hilbert_sort_middle_2 stops refining when every point falls into one child, even when later midpoint cuts would separate distinct points. The guard appears inconsistent with the documented recursive midpoint subdivision.

For six diagonal points with 64*x = 64*y = 0,5,9,7,11,64, the default functor returns 0 5 9 7 11 64; the expected order is 0 5 7 9 11 64. All coordinates are exact binary fractions. Five points enter the same child and then the same grandchild, where refinement stops prematurely. The exhaustive diagnostic finds 714 failures among 720 permutations, both for the functor and for hilbert_sort with explicit middle policy.

The candidate patch continues through single-child cells and passes all permutations. It computes point bounds once, resumes partitioning at a separating cut, retains the leaf-size limit, and stops for coincident converted coordinates or when midpoint subdivision cannot progress.

Performance is mixed. Across 46 cases, seven paired seeds and 2,730 constructions, corrected/original total-time estimates are below one in 32 cases; seven individual 95% intervals are entirely above one. Examples:

Input n Corrected/original total time (95% interval)
New York 264,346 1.0515 [1.0208, 1.0958]
Western USA 6,262,104 0.4123 [0.3940, 0.4373]
Uniform 4,194,304 1.0426 [0.9960, 1.1353]

A separate New York run gave 0.9519 [0.8502, 1.0128], with matching insertion-order hashes, geometry and paths. It did not reproduce the slowdown. These are exploratory, unadjusted intervals from one machine. The complete phase table and raw measurements include favorable and unfavorable results. Default Delaunay range insertion uses median; these comparisons explicitly select middle.

Should middle continue refinement here, or is the early stop an intended heuristic? If correction is preferred, what performance tradeoff and target branches would be acceptable?

Source Code

Download the reproduction package, follow setup, and run sha256sum --check SHA256SUMS. Each command below measures one complete dataset with original middle, corrected middle and median, using seven seeds (21 constructions), after diagnostic and sanitizer checks:

Dataset Coordinates Independent command
Western USA 6,262,104 python reproduce_dataset.py --dataset roads_w
California/Nevada 1,890,815 python reproduce_dataset.py --dataset roads_cal
GSHHG European crop 1,826,772 python reproduce_dataset.py --dataset shorelines_europe
New York 264,346 python reproduce_dataset.py --dataset roads_ny

Western USA is the largest real input; only New York's projected coordinates are bundled. The other selected inputs are downloaded and projected automatically, with source and coordinate SHA-256 checks. Sources, projections and licenses are supplied. Each command runs only its selected case and preserves its relative process order from the original schedule.

Outputs are dataset_results/<dataset>-<size>/samples.jsonl, comparison.csv and validation.json, recording insertion path, sorting, insertion, contiguous total, CPU and memory. For Western USA at 65,536 points, add --size 65536; reproducing its seeded subset still requires the full coordinate file. Use --list for all dataset/size choices, or --dataset uniform for the uniform case above. The README gives all individual commands.

python rebuild_data.py --dataset roads_w only reconstructs and verifies coordinates; replace the identifier for another dataset. python check_recorded.py recomputes the supplied statistics. New timing results are stored separately and may differ from the recorded observations.

Minimal example (original output 0 5 9 7 11 64):

#include <CGAL/Simple_cartesian.h>
#include <CGAL/hilbert_sort.h>

#include <iostream>
#include <vector>

int main()
{
    using Kernel = CGAL::Simple_cartesian<double>;
    using Point = Kernel::Point_2;

    std::vector<Point> points;
    for (int numerator : {0, 5, 9, 7, 11, 64})
        points.emplace_back(numerator / 64.0, numerator / 64.0);

    CGAL::Hilbert_sort_2<Kernel, CGAL::Hilbert_sort_middle_policy> sort;
    sort(points.begin(), points.end());

    for (const Point& point : points)
        std::cout << point.x() * 64 << ' ';
    std::cout << '\n';
}

Environment

CGAL 6.1.x at 0490d81af4220f33005914676f362f349933fbc1; the affected header is identical in the linked main snapshot. Linux x86_64, GCC 15.2.0/libstdc++, Python 3.14.4, NumPy 2.5.3. The benchmark uses Exact_predicates_inexact_constructions_kernel, sequential sorting and -O3 -DNDEBUG; the diagnostic uses Simple_cartesian<double> and -O1 -UNDEBUG. See the measurement protocol and recorded environment.

Activity

  1. pedro-machado-manhaes-de-castro commented on Oct 20, 2026

    @pedro-machado-manhaes-de-castro
    ContributorAuthor

    This occurs regardless of colinearity or kernel (e.g., Simple_cartesian<double>, EPICK and EPECK). Take the points A=(0,0), B=(5,6), C=(9,10), D=(7,5), E=(11,13), F=(64,64) the result is the same.

  2. pedro-machado-manhaes-de-castro commented on Oct 26, 2026

    @pedro-machado-manhaes-de-castro
    ContributorAuthor

    Hi everyone. Have you had a chance to look at this? I can open a PR with the proposed fix if that would make it easier to discuss.

  3. LeoValque commented on Oct 29, 2026

    @LeoValque
    Contributor

    Hi Pedro, I looked into it, and indeed, the sort is cancelled when all the elements fall into the same quarter. I see two distinct fixes:

    • Don’t stop sorting when all the elements are in the same quarter.
    • Update the minimum and maximum values in each recursive call.
      You mentioned that you have a fix in mind. What do you propose?
  4. pedro-machado-manhaes-de-castro commented on Oct 29, 2026

    @pedro-machado-manhaes-de-castro
    ContributorAuthor

    Thanks for looking into this. I agree with continuing refinement. I have implemented and tested this approach in the candidate patch linked in the opening report. It preserves the existing midpoint hierarchy and Hilbert orientations. When a range stays in one child, it computes its point bounds once and reuses them to skip levels until a cut separates points.

    If your second option means recomputing each subset’s tight bounding box, that would change the subdivision.

    The ordering diagnostic passes all 720 permutations of the example. The Delaunay experiments cover 46 cases and seven seeds, with lower total-time estimates in 32 cases and some regressions. The README includes commands to reproduce each dataset independently.

    My preference is to fix the existing middle policy. The performance tradeoffs are why I wanted your input before opening a PR. We might also consider retaining the current behavior as a documented heuristic if you see fit.

  5. LeoValque commented on Oct 29, 2026

    @LeoValque
    Contributor

    I’ve created a more compact version of your fix that uses CGAL functions. I’m also fixing Hilbert_sort_middle_3, which has the same issue.

  6. pedro-machado-manhaes-de-castro commented on Oct 30, 2026

    @pedro-machado-manhaes-de-castro
    ContributorAuthor

    Thanks, Leo. I tested the 2D version and added the reproductions and suggested fixes to #9806.

  7. added this to the 6.1.4 milestone on Nov 3, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Type

No type

Projects

No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions