Skip to content

Continue sorting if all elements are in one quarter in hilbert sort middle - #9806

Open
LeoValque wants to merge 14 commits into
CGAL:mainfrom
LeoValque:SS-Fix_issue_9769
Open

LeoValque wants to merge 14 commits into
CGAL:mainfrom
LeoValque:SS-Fix_issue_9769

Conversation

@LeoValque

Copy link
Copy Markdown
Contributor

Summary of Changes

Hilber_sort_middle_2 (and 3) stops if all elements are contained in one quarter.

Release Management

@pedro-machado-manhaes-de-castro

Copy link
Copy Markdown
Contributor

Thanks for the PR, @LeoValque. I tested c5c5535 using Hilbert_sort_middle_2<Simple_cartesian> with limit=1 and found two issues.

equal_2_object()(*begin, *end) dereferences the past-the-end iterator. Two identical points already trigger an ASan heap-buffer-overflow. The coincidence check needs to cover the whole range: replacing end with end - 1 still stops prematurely for (1,1), (2,2), (1,1), (64,64).

There is also a termination issue in skip_empty_cells: (0,0), (1,0), (2,0), (64,0) causes a stack overflow, even after fixing the coincidence check. Returning to sort requires an actual separation under the partition comparator. Subdivision also needs to stop when the midpoints can no longer progress.

These checks are implemented in compute_bounds() and skip_empty_cells() in the candidate implementation. I suggest reusing those checks, retaining the existing empty-range guard, and adding these examples as regression tests.

@MaelRL MaelRL added the TODO label Nov 3, 2026
@MaelRL MaelRL added this to the 6.1.4 milestone Nov 3, 2026
@pedro-machado-manhaes-de-castro

Copy link
Copy Markdown
Contributor

Hello, @LeoValque. I retested 302b6b3 with Simple_cartesian<double> and limit=1. The original witness now passes. The points (0,0), (1,0), (2,0), (64,0) still cause a stack overflow in 2D, as does the same input with z=0 in 3D. Two adjacent 2D points, (1,1) and (std::nextafter(1.,2.), std::nextafter(1.,2.)), also overflow; their 3D counterparts do too.

In skip_empty_cells(), (!y_lower && !y_upper) calls sort() when ymed = bb.ymin() = bb.ymax() = 0, although the strict < partition keeps every point in one child. With adjacent coordinates, midpoint rounding can prevent progress. I think calling sort() only after an actual split, stopping when subdivision cannot progress, would be good. Maybe consider adding these cases as regression tests with limit=1?

@LeoValque

Copy link
Copy Markdown
Contributor Author

Hi, @pedro-machado-manhaes-de-castro , I didn't reproduce this stackoverflow problem (I add tests with nextafter too), could you give more details? I consider add a tolerance parameter to stop sorting if the width of a cell become smaller than this tolerance, what do you think about?

@pedro-machado-manhaes-de-castro

Copy link
Copy Markdown
Contributor

@LeoValque I think the new 2D test passes because its Point type is Cartesian_d<double>::Point_d, so it calls Hilbert_sort_middle_d. The failing path is Hilbert_sort_middle_2. Your 3D test with nextafter(0.,1.) also completes here with /O2. I compiled this public-API reproduction against a sparse checkout of your branch at 302b6b3:

#include <CGAL/Simple_cartesian.h>
#include <CGAL/hilbert_sort.h>
#include <vector>
int main() {
  using K = CGAL::Simple_cartesian<double>;
  std::vector<K::Point_2> points{{0,0}, {1,0}, {2,0}, {64,0}};
  CGAL::hilbert_sort(points.begin(), points.end(), CGAL::Hilbert_sort_middle_policy());
}

On Windows with MSVC 14.51, this exits with stack overflow (0xC00000FD) under both /Od and /O2; it still overflows with an 8 MiB stack in the debug build. After the first split, the 0,1,2 subrange has bounds (xmin,ymin,xmax,ymax)=(0,0,32,0). Then ymed=bb.ymin()=bb.ymax()=0 makes (!y_lower && !y_upper) true, and skip_empty_cells() calls sort() again with the same range and bounds. The pair (1,1), (std::nextafter(1.,2.),std::nextafter(1.,2.)) makes another no-progress loop. The same thing happens in the 3D cases, which also overflow in both builds.

A width tolerance alone seems not good enough here: the y width is zero while distinct x values still need sorting, and the repeated cell keeps an x width of 32. It could be nice to check of an actual comparator split before returning to sort(), and stop when subdivision cannot progress.

@pedro-machado-manhaes-de-castro

Copy link
Copy Markdown
Contributor

@LeoValque. I retested 879a03a with Simple_cartesian<double> and limit=1. The 2D horizontal and adjacent-point cases now pass. The analogous 3D horizontal case reaches the assertion in Hilbert_sort_middle_3.h:143. At that point, the bounds are x=(0,0), y=(0,0), and z=(16,0): the z interval is reversed by the traversal, so zmax > zmin is false even though that axis can still be subdivided. Changing the three > comparisons in that assertion to != made this case pass with assertions enabled under both /Od and /O2, preserving the input points. Could you add this Point_3 case and a horizontal Point_2 case as regression tests?

@LeoValque

Copy link
Copy Markdown
Contributor Author

Sorry for the leftover assertion. At this point, xmin == xmax because a dimension is now simply ignored when the points are axis-aligned. So I removed the assertion.

@tashimir

tashimir commented Nov 5, 2026

Copy link
Copy Markdown
#include <CGAL/Simple_cartesian.h>
#include <CGAL/hilbert_sort.h>
#include <vector>

int main() {
  using K = CGAL::Simple_cartesian<double>;
  std::vector<K::Point_2> points{{0, 8}, {8, 0}, {2, 2}, {3, 2}};
  CGAL::hilbert_sort(points.begin(), points.end(), CGAL::Hilbert_sort_middle_policy());
}

With GCC 15.2 (-O3 -DNDEBUG), we have something that exceeds 12 seconds. The pair (2,2),(3,2) reaches sort<1,false,false> with bounds (0,0,4,4). The strict y < 2 split moves neither point, but skip_empty_cells() calls sort() again with the same range and bounds. I think we should add these four integer points as a test.

Also I suggest the following patch:

diff --git a/Spatial_sorting/include/CGAL/Hilbert_sort_middle_2.h b/Spatial_sorting/include/CGAL/Hilbert_sort_middle_2.h
index b23fcaf454ecfff622b6158ddc7a5ea22475b24b..8f2ba96eba214dc7799f8c5fd21922e8cf9bd3ea 100644
--- a/Spatial_sorting/include/CGAL/Hilbert_sort_middle_2.h
+++ b/Spatial_sorting/include/CGAL/Hilbert_sort_middle_2.h
@@ -94,12 +94,6 @@
     : _k(k), _limit (limit)
   {}

-  // Hilbert sort use double representations so two points not strictly equal will treat identically by hilbert sort
-  bool have_equal_representations(Point a, Point b) const{
-    return (to_double(_k.compute_x_2_object()(a)) == to_double(_k.compute_x_2_object()(b))) &&
-           (to_double(_k.compute_y_2_object()(a)) == to_double(_k.compute_y_2_object()(b)));
-  }
-
   template <int x, bool upx, bool upy, class RandomAccessIterator>
   void skip_empty_cells (RandomAccessIterator begin, RandomAccessIterator end,
                          double xmin, double ymin, double xmax, double ymax, Bbox_2 bb) const
@@ -109,19 +103,19 @@
     double ymed= (ymin+ymax)/2;
     const bool x_degen = (xmin == xmed || xmed == xmax);
     const bool y_degen = (ymin == ymed || ymed == ymax);
-    const bool x_lower = (x==0) ? xmed<bb.xmin() : xmed<bb.ymin();
+    const bool x_split = (x==0) ? (bb.xmin()<xmed && xmed<=bb.xmax())
+                                : (bb.ymin()<xmed && xmed<=bb.ymax());
+    const bool y_split = (x==0) ? (bb.ymin()<ymed && ymed<=bb.ymax())
+                                : (bb.xmin()<ymed && ymed<=bb.xmax());
     const bool x_upper = (x==0) ? xmed>bb.xmax() : xmed>bb.ymax();
-    const bool y_lower = (x==0) ? ymed<bb.ymin() : ymed<bb.xmin();
     const bool y_upper = (x==0) ? ymed>bb.ymax() : ymed>bb.xmax();

-    if(x_degen && y_degen)
-      return;
-
-    if( (!x_degen && !x_lower && !x_upper) || (!y_degen && !y_lower && !y_upper)){
-      // Not contain in one quarter
+    if(x_split || y_split){
       sort<x, upx, upy> (begin, end, xmin, ymin, xmax, ymax);
       return;
     }
+    if(x_degen && y_degen)
+      return;

     if( x_upper != upx )
     {
@@ -159,14 +153,15 @@
         ((m2 == m0) && ((m3 == m2) || (m3 == m4))) )
     {
       // All elements are in one quarter
-      bool all_equal = true;
-      for(auto it=begin; it!=end-1; ++it)
-        if(!have_equal_representations(*it, *(it+1))){
-          all_equal = false;
-          break;
-        }
-      if(all_equal) return;
-      Bbox_2 bb=bbox_2(begin, end, Spatial_sorting::internal::Kernel_wrapper_2<Kernel>(_k));
+      const double px = to_double(_k.compute_x_2_object()(*begin));
+      const double py = to_double(_k.compute_y_2_object()(*begin));
+      Bbox_2 bb(px, py, px, py);
+      for(auto it=begin+1; it!=end; ++it){
+        const double point_x = to_double(_k.compute_x_2_object()(*it));
+        const double point_y = to_double(_k.compute_y_2_object()(*it));
+        bb += Bbox_2(point_x, point_y, point_x, point_y);
+      }
+      if(bb.xmin()==bb.xmax() && bb.ymin()==bb.ymax()) return;
       skip_empty_cells<x, upx, upy> (begin, end, xmin, ymin, xmax, ymax, bb);
     }
     else

@pedro-machado-manhaes-de-castro

Copy link
Copy Markdown
Contributor

tashimir is me (sorry to post with the wrong account)

@pedro-machado-manhaes-de-castro

Copy link
Copy Markdown
Contributor

@LeoValque there is a last little thing that seems wrong that I noticed.

In skip_empty_cells(), the partition uses to_double(coordinate) < midpoint. With bounds computed from those same converted values, all points are below the cut exactly when midpoint > max, and all are at or above it exactly when midpoint <= min. A split occurs when min < midpoint && midpoint <= max. The new midpoint >= bb.max() test treats equality at the upper bound as if all points were below the cut. If every point’s coordinate on that axis equals the midpoint, both *_lower and *_upper become true. Could you keep the upper test strict, use bounds consistent with the comparator, and check for a real split before the degenerate-midpoint return in both 2D and 3D?

Using Simple_cartesian<double> with (0,0), (0,4), (3.125,1), (4,1), 3aa0c82 orders the last pair as (3.125,1), (4,1). My local version with the split check orders it as (4,1), (3.125,1). Scaling the planar coordinates by 1/8 and mapping (u,v) to (sqrt(1-u*u-v*v),u,v) produces the same difference through hilbert_sort_on_sphere. That could be a test that checks the correct order at this boundary.

@sloriot

sloriot commented Nov 20, 2026

Copy link
Copy Markdown
Member

Successfully tested in CGAL-6.3-Ic-137

@sloriot sloriot added Tested Not yet approved The feature or pull-request has not yet been approved. and removed Ready to be tested Under Testing labels Nov 20, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

Bug Not yet approved The feature or pull-request has not yet been approved. Pkg::Spatial_sorting Tested

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Spatial_sorting: middle-policy refinement stops while points remain separable

5 participants