Building a Mutable Set

I recently implemented an algorithm that computes the intersection (if any) among each pair of segments in a collection of nonvertical line segments, as shown in Figure 1. The requirements of the algorithm and the application in which it was used forced me to look for a new type of container to provide the flexibility and efficiency I needed. What I found was not a new container, but a twisted version of std::set that perfectly suited my needs. Though based on std::set, this construction is by no means general-purpose; it was developed to help solve a very specific problem. On the other hand, this is not just a fancy parlor trick. I have used this construction effectively in production code.

The Algorithm

The basic algorithm is shown in Figure 2. As the algorithm proceeds and intersections are found, the x-coordinates of these intersection points are added to ScanSet. The segments in the subcollection ActiveSegs are ordered based on the current scan position x_c. For each segment in ActiveSegs, its intersection with the vertical line at x_c is calculated. The segments are then sorted by increasing value of the y-coordinates of these points of intersection. What makes this algorithm difficult is that this sort order changes each time the scan position moves. In particular, if two or more segments intersect at x_c, the relative order of their y-coordinates to the left of x_c is the reverse of their order to the right of x_c (see Figure 3). A naive implementation of the algorithm would reorder the entire collection of segments each time the scanline moves. But this is a very inefficient ( O(n^2 * log(n) ) algorithm. A more efficient solution exploits the fact that the algorithm only needs to re-order small groups of intersecting segments, rather than the entire collection. I'll describe that solution later in this article.

The details of detecting and reporting segment intersections are not fundamental to this article, so they are omitted. To put the algorithm into context, the line segment collections may contain several hundred thousand segments, so runtime efficiency is paramount. On the other hand, the users of this code typically have ample memory on their machines, so memory efficiency is of lesser importance. Also, all segment endpoints and intersections have integer coordinates.

Choosing a Container

1. Change the sort order of ActiveSegs on each iteration.

2. Insert a segment in sorted order.

3. Remove a segment.

4. Reverse the order of intersecting segments.

The following chart summarizes the runtime behavior of the standard containers on each of the four requirements. map is excluded, since no associations are being formed, as is deque, since it behaves more or less like vector. That leaves list, vector, and set as possible candidates.

    Requirement      list          vector        set
   -----------------------------------------------------------
1) Change sorting    O(n*log(n))   O(n*log(n))   not possible
2) Insert segment    O(n)          O(n)          O(log(n))
   in sorted order
3) Remove segment    constant      O(n)          O(log(n))
4) Reverse segments  O(n)          O(n)          not possible

That leaves set, which does quite well on insertion and removal, because that is what it is designed to do. Unfortunately, set is not designed for any form of reorganization. Copying the data from one set to another could satisfy requirements 1 and 4, but this approach would be very slow.

In summary, the standard containers make trade offs between flexibility and runtime efficiency. list and vector are flexible and slow, while set is fast but limited in what it can do. Or is it?

Building an std::set

The set declaration looks like this:

int x_coord = some_scan_position;
std::set<Segment, fCompare> 
 SegSet(fCompare(x_coord));

Messing With a Good Thing

A first attempt at circumventing this problem might be to make the state data m_scan_pos a static variable within fCompare, and then provide a static method set_scan_position() to change the data. This way, a copy of the comparison object could be modified and the changes would be reflected in the object stored by the set. Of course, this strategy would prevent fCompare from being used in more than one set at a time unless all the sets want their scan positions changed simultaneously.

A more subtle approach would be to pass the set a reference to the comparison object, rather than the object itself. Then the referenced object could be modified and the changes would be reflected within the set. Unfortunately (for this discussion), the Standards committee knew the dangers in allowing a set's comparison object to be modified in this way, so the Standard explicitly prevents std::set from storing such a reference [2].

It's Dangerous, But it Works

class fCompare
{
  public:
    fCompare(const int& coord) : 
      m_scan_pos(coord) {}
  private:
    const int& m_scan_pos;
};

int scan_pos;

std::set<Segment, fCompare> 
  SegSet( fCompare(scan_pos) );

I Was Warned...

0 1 2 3 4 
4 3 2 0 1 2 3 4 1 0 

Being Careful

Getting back to the algorithm, at each scan position x_c, the collection of active segments needs to have its ordering updated to reflect this new position. If intersections exist at this scan position, manual reordering of the segments is required to keep the segment order compatible with the comparison object. That is, if segment s1 intersects segment s2 at x_c, the order of these two segments needs to be reversed when the scanline crosses their point of intersection. But their order relative to the remaining segments in the collection does not change; any segments that were above or below the two intersecting segments will still be above or below them. The upshot of this is that if the order of the segments in each intersecting group is manually reversed each time the scan position is updated, the segment order will agree with the current state of the comparison object, and the underlying std::set will behave consistently.

I have two options for performing the reversal of intersecting segments:

MutableIter mi_first(first);
MutableIter mi_last(last);
std::reverse(mi_first, mi_last);