Using a C++ map or set with geometric data
Jun 19, 2016
One of the most typical building blocks of efficient geometric computations is a spatial index. Using a spatial index, it is possible to perform many simple operations quickly, like obtaining a set of unique points. Such an operation can then be used for things like building a topological data structure or indexing more complex objects.
However, properly implementing a spatial index is messy and, frankly, overkill for many practical applications. And yet, computations without one can be mind-bogglingly slow. So, I often resort to a quick hack—using a C++ standard library
map with a custom comparison function. A
map offers logarithmic time access to its elements, much like most spatial indices, and it works out of the box for plain old data types like
int. Moreover, in order for you to use it with any class you’re working with, it only needs a custom comparison functor1 that defines an ordering of its elements2.
So, let’s look at an example of some code I’m currently working on. A CGAL
Point_d is a simple data structure for a d-dimensional point. I personally want to use these kinds of points to quickly access unique geometric objects embedded at those locations, and so I created a custom comparison functor for them. It orders points first by their dimension and then lexicographically by their coordinates:
In a simple example, such a comparison functor can then be used to define a set of unique points (as defined by their coordinates). For instance, this allows you to assign unique IDs to a location.
In a more complex example, the same comparison functor can be used to index a set of edges (as defined by a unique start-end pair of points). I personally use this kind of structure to link a set of adjacent polygons by their common edges and to check if such a set forms a quasi-manifold in 3D. Note that you should make sure to insert the two end-points in a well-defined order, such as the lexicographically smallest first!
For a future blog post, how to do something similar with a more efficient (constant time) C++11
unordered_map and a custom hashing function.
A functor is an object that behaves like a function. In C++, a functor is a
structthat does this by overloading the () operator. Unlike function pointers, they are fast since they are generated at compilation time. ↩
Most people choose to mimic the value of the < (less than) operator, which is what
mapdo for plain old types. ↩