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 `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 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.

1. A functor is an object that behaves like a function. In C++, a functor is a `class` or `struct` that does this by overloading the () operator. Unlike function pointers, they are fast since they are generated at compilation time.

2. Most people choose to mimic the value of the < (less than) operator, which is what `set` and `map` do for plain old types.