Search code examples
cgal

Segment tree in CGAL with intervals of size 0


I am using a multidimensional segment tree in CGAL (Segment_tree_d), with 11 dimensions. My objective is to find overlapping intervals, given a query interval (window_query). I am able to do that, except when intervals are of size 0. I am showing minimal example, with a 3-dimensional tree, that produces the same issues. Is this a fundamental limitation? Is there a configuration option or a different class that I can use? My use case has only integer coordinates, so I can work around this problem by adding a small fraction to either side of the interval, but I do not want to do that if there is a better solution.

Source Code

#include <CGAL/Cartesian.h>
#include <CGAL/Segment_tree_k.h>
#include <CGAL/Range_segment_tree_traits.h>
typedef CGAL::Cartesian<int> K;
typedef CGAL::Range_segment_tree_set_traits_3<K> Traits;
typedef CGAL::Segment_tree_3<Traits > Segment_tree_3_type;
int main()
{
  typedef Traits::Interval Interval;
  typedef Traits::Key Key;
  std::list<Interval> InputList, OutputList;

  InputList.push_back(Interval(Key(1,5,7), Key(1,5,7)));
  Segment_tree_3_type Segment_tree_3(InputList.begin(),InputList.end());

  Interval a(Key(3,6,5), Key(3,6,5));
  Segment_tree_3.window_query(a,std::back_inserter(OutputList));
}

Output:

CGAL warning: check violation!
Expression : m_interface.comp(m_interface.get_left(*count), m_interface.get_right(*count))
File       : /usr/include/CGAL/Segment_tree_d.h
Line       : 542
Explanation: invalid segment ignored
Refer to the bug-reporting instructions at http://www.cgal.org/bug_report.html
CGAL warning: check violation!
Expression : m_interface.comp(m_interface.get_right_win(win), m_interface.get_left_win(win))
File       : /usr/include/CGAL/Segment_tree_d.h
Line       : 636
Explanation: invalid window -- query ignored
Refer to the bug-reporting instructions at http://www.cgal.org/bug_report.html

Solution

  • Extracted from here:

    A one-dimensional segment tree is a binary search tree as well, but with one-dimensional interval data as input data. One-dimensional interval data is a pair (i.e., 2-tuple) (a,b), where a and b are one-dimensional point data of the same type and a< b. The pair (a,b) represents a half open interval [a,b). Analogously, a d-dimensional interval is represented by a d-tuple of one-dimensional intervals.