The project focuses on applications of rtree data structure.
- Package cgal-swig-bindings, script packages cgal, swig
- Package libspatialindex, rtree
- RealSet Class
- RationalPolyhedralFan Class
- Cut-generating functions
- What is rtree?
- What are the ordinary operations for rtree data structure?
- Is there any variants of rtree? What are they?
- What is the main difference of those variants?
- What problems can rtree be used to solve in this project?
- What are the contributions of this project?
- cgal_swig_bindings, cgal, swig
- libspatialindex and rtree
- RealSet_rtree Class
- RationalPolyhedralFan_rtree Class
CGAL is a software project that provides easy access to efficient and reliable geometric algorithms in the form of a C++ library. We integrated the package cgal-swig-bindings into the SageMath software for calling functions in CGAL. Code and discussion can be found in this ticket.
libspatialindex is a software project that includes C++ implementation of R*-tree, an MVR-tree and a TPR-tree with C API, which are variants of rtree. rtree is a ctypes Python wrapper of libspatialindex that provides a number of advanced spatial indexing features for the spatially curious Python user. We integrated the package libspatialindex and into the SageMath software for the usage of rtree. Code and discussion can be found in this ticket.
RealSet in SageMath contains subsets of the real line that can be constructed as the union of a finite set of open and closed intervals. Compared to trivial storage, rtree data structure provides a fast path for retrieving the possible intersected intervals with accuracy, which could reduce the processing time of contains() and intersection() functions. In detail, noticing that two intervals intersect with each other only if their closure intersects with each other, we can organize all of the intervals of a given Class RealSet() in a one-dimensional rtree by storing their closures to overestimate the status of their intersection, then give a further verification of the intervals. Code and discussion can be found in this ticket.
A rational polyhedral fan is a finite collection of strictly convex rational polyhedral cones, such that the intersection of any two cones of the fan is a face of each of them and each face of each cone is also a cone of the fan. For the Class RationalPolyhedralFan() in SageMath, We added rtree data structure for reducing the time of support_contains() function, which is used for checking if a point is contained in the support of the fan. The idea is similar to the situation in RealSet class, that we will give a preliminary overestimation of the search result first, then we give a further verification. In addition, we also add LP-solver and faceted-based method for automatically determining if it is a pointed fan or not. Code and discussion can be found in this ticket.
Short answer:
rtree is a tree data structure used for queries and storage of multi-dimensional data. The key idea of the data structure is to group local objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "r" in rtree is for rectangle. Another name for rtree is called AABB tree, Axis-Aligned Bounding Box Tree. Since all objects lie within this bounding rectangle, it is possible to make a fast query that does not intersect the bounding rectangle also cannot intersect any of the contained objects.
A friendly introduction can be found here.
A little long slides but with clear details can be found here.
See this link. A simple prototype with inputs and outputs can be found here.
Yep.
The variants of it inlcude PR-tree, R*-trees, R+ tree, Hilbert R-tree, X-tree.
There are two important concepts for rtree:
Coverage is the entire area to cover all related rectangles.
Overlap is the entire area that is contained in two or more nodes.
Minimal coverage reduces the amount of "dead space" (empty area) which is covered by the nodes of the R-tree. Minimal overlap reduces the set of search paths to the leaves (even more critical for the access time than minimal coverage). Efficient search requires minimal coverage and overlap.
The main difference between those variants lies in how they deal with the Coverage and Overlap. For example, R+ trees differ from R trees in that: nodes are not guaranteed to be at least half-filled, the entries of any internal node do not overlap, and an object ID may be stored in more than one leaf node.
In this project, we use the rtree to solve the problem of intersection detection of convex polytopes in a high-dimensional space for mathematical research. Because most mathematicians in this area only focus on pure theoretical research with less attention on how to organize them for computation, it is common to store convex polytopes in the element-to-set form without any interior relationship support. However, as the number of convex polytopes increases, the intersection detection will be slow since it is a linear scanning due to the element-to-set form. The advantage of rtree is that it can store those convex polytopes based on their geometrical neighborhood in a tree organizing, which is a binary search for queries.
We have implemented rtree data structure for RealSet class, (It can be seen as a collection of one-dimensional convex polytopes), and for pointed RationalPolyhedronFan class, (Even though it is a collection of cones, we transformed cones to convex polytopes so that those cones still can be stored in a rtree) for obtaining high speed. See codes of class RealSet_rtree, and class RationalPolyhedralFan_rtree. The details of implementation can be found on this page.
Methods:
- Method for automatically determining whether a Polyhedral fan is pointed or not, see comments50-53.
- Method for quickly computing Minkowski sums of a group of convex polytopes, see this page.
- Method for quickly detecting the intersection of polytope pairs, see this page.
Implementations:
- Class RealSet_rtree
- Class RationalPolyhedralFan_rtree
Packaging:
The following code has been installed successfully on MAC OS. It might not be installed successfully on other systems.
To get access to cgal in sage, please do as follows.
- Install Sage from source.
Since cgal_swig_bindings package currently is waiting for review, it can only be accessed via develop version, instead of a release version, we have to install it from source. To install it, see this page.
- Install CGAL.
Run the following script in terminal:
$brew install cgal
- Install SWIG.
Run the following script in terminal:
$brew install swig
- Install cgal_swig_bindings.
Enter into SAGE_ROOT in terminal:
$cd path/to/SAGE_ROOT
Pull the corresponding version from sage git, which includes the scripts for installing cgal_swig_bindings.
$git pull trac u/mkoeppe/cgal_swig_bindings
Install it via sage:
$./sage -i cgal_swig_bindings
Now, we are done.
To test whether it has been installed successfully, launch sage in terminal:
$./sage
Then import cgal in sage:
sage: import CGAL
If it can be imported without any error, then it shows installation is successful.
To use it properly, please see these examples.
To get access to rtree in sage, please do as follows.
- Install sage from source.
Since cgal_swig_bindings package currently is waiting for review, it can only be accessed via develop version, instead of a release version, we have to install it from source. To install it, see this page.
- Install libspatialindex and rtree in sage.
Enter into SAGE_ROOT in terminal:
$cd path/to/SAGE_ROOT
Pull the corresponding version from sage git, which includes the scripts for installing libspatialindex and rtree:
$git pull trac public/32000
Install libspatialindex and rtree via sage:
$./sage -i libspatialindex
$./sage -i rtree
Now, we are done.
To test whether it has been installed successfully, launch sage in terminal:
$./sage
Then try to import rtree in sage:
sage: from rtree import index
If it can be imported without any error, then it shows installation is successful.
To use it properly, please see these examples.
To get access to RealSet_rtree class in sage, please do as follows.
- Install sage from source.
Since cgal_swig_bindings package currently is waiting for review, it can only be accessed via develop version, instead of a release version, we have to install it from source. To install it, see this page.
- Install libspatialindex and rtree in sage.
Pull the corresponding version from sage git:
$git pull trac public/32170
Install libspatialindex and rtree via sage:
$./sage -i libspatialindex
$./sage -i rtree
Recompile files in sage:
$./sage -b
Now, we are done.
To test whether it has been installed successfully, launch sage in terminal:
$./sage
Then try to import it in sage:
sage: from sage.sets.real_set import RealSet_rtree
If it can be imported without any error, then installation is successful.
To use it, see the following examples.
- Define a RealSet_rtree class:
sage: from sage.sets.real_set import RealSet_rtree
sage: A = RealSet_rtree(0,1)
- Check whether a point is included in a real set class or not.
sage: from sage.sets.real_set import RealSet_rtree
sage: RealSet_rtree(0,1).contains(0.5)
True
sage: RealSet_rtree(0,1).contains(3)
False
sage: (RealSet_rtree(0,1)+RealSet_rtree(3,4)).contains(3)
False
sage: (RealSet_rtree(0,1)+RealSet_rtree([3,4])).contains(3)
True
- The type of the intersection of two
RealSet_rtreeinstances is still maintained.
sage: from sage.sets.real_set import RealSet_rtree
sage: A = RealSet(0,1)
sage: B = RealSet_rtree(0.5,3)
sage: print(type(A.intersection(B)), type(B.intersection(A)))
<class 'sage.sets.real_set.RealSet_with_category'> <class 'sage.sets.real_set.RealSet_rtree_with_category'>
Other examples can be found in docstring of RealSet_rtree class.
To get access to RationalPolyhedralFan_rtree class in sage, please do as follows.
- Install sage from source.
Since cgal_swig_bindings package currently is waiting for review, it can only be accessed via develop version, instead of a release version, we have to install it from source. To install it, see this page.
- Install libspatialindex and rtree in sage.
Pull the corresponding version from sage git:
$git pull trac public/32170
Install libspatialindex and rtree via sage:
$./sage -i libspatialindex
$./sage -i rtree
Recompile files in sage:
$./sage -b
Now, we are done.
To test whether it has been installed successfully, launch sage in terminal:
$./sage
Then try to import it in sage:
sage: from sage.geometry.fan import RationalPolyhedralFan_rtree
If it can be imported without any error, then installation is successful.
To use it, see the following examples.
- Define a
RationalPolyhedralFan_rtreeclass:
Explicitly define it with RationalPolyhedralFan_rtree class,
sage: from sage.geometry.fan import RationalPolyhedralFan_rtree
sage: v1, v2= vector([0,1]), vector([1,0])
sage: v1.set_immutable()
sage: v2.set_immutable()
sage: f = RationalPolyhedralFan_rtree([(0,),(1,)], [v1,v2], None)
Or, define it from Fan, FaceFan, NormalFan and Fan2d function, with setting allow_rtree = True.
sage: from sage.geometry.fan import RationalPolyhedralFan_rtree
sage: cone1 = Cone([(0,-1), (1,0)])
sage: cone2 = Cone([(1,0), (0,1)])
sage: f = Fan([cone1, cone2], allow_rtree = True)
- Check whether a fan is pointed or not.
sage: from sage.geometry.fan import RationalPolyhedralFan_rtree
sage: v1, v2= vector([0,1]), vector([1,0])
sage: v1.set_immutable()
sage: v2.set_immutable()
sage: f = RationalPolyhedralFan_rtree([(0,),(1,)], [v1,v2], None)
sage: f.is_pointed()
True
- Check whether a point is included in a
RationalPolyhedralFan_rtreeclass or not.
sage: from sage.geometry.fan import RationalPolyhedralFan_rtree
sage: cone1 = Cone([(0,-1), (1,0)])
sage: cone2 = Cone([(1,0), (0,1)])
sage: f = Fan([cone1, cone2], allow_rtree = True)
sage: f.support_contains(f.lattice()(1,0))
True
sage: f.support_contains(cone1) # a cone is not a point of the lattice
False
sage: f.support_contains((1,0))
True
sage: f.support_contains(1,1)
True
sage: f.support_contains((-1,0))
False
Other examples can be found in docstring of RationalPolyhedralFan_rtree class.