Using a C++ map or set with geometric data

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 functor¹ that defines an ordering of its elements².

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:

struct Point_d_comparator {
  bool operator()(const Point_d &p1, const Point_d &p2) const {
    
    if (p1.dimension() < p2.dimension()) return true;
    if (p1.dimension() > p2.dimension()) return false;
    
    Point_d::Cartesian_const_iterator p1_coordinate = p1.cartesian_begin()
    Point_d::Cartesian_const_iterator p2_coordinate = p2.cartesian_begin();
    while (p1_coordinate != p1.cartesian_end()) {
      if (*p1_coordinate < *p2_coordinate) return true;
      if (*p1_coordinate > *p2_coordinate) return false;
      ++p1_coordinate;
      ++p2_coordinate;
    } return false;
  }
};

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.

std::set<Point_d, Point_d_comparator> vertices;

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!

std::map<Point_d, std::map<Point_d, int, Point_d_comparator>, Point_d_comparator> edges;

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.