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 mindbogglingly slow. So, I often resort to a quick hack—using a C++ standard library set
or map
with a custom comparison function. A set
or 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 float
or int
. Moreover, in order for you to use it with any class you’re working with, it only needs a custom comparison functor^{1} that defines an ordering of its elements^{2}.
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 ddimensional 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 startend 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 quasimanifold in 3D. Note that you should make sure to insert the two endpoints in a welldefined 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
class
orstruct
that 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
set
andmap
do for plain old types. ↩