CODEWITHSUNDEEP
javaalgorithmgeometrycomputational-geometry
mrMoonpenguin
mrMoonpenguin

Reputation: 57

Bentley-Ottmann algorithm: swap operation in Java

I'm trying to implement the Bentley-Ottmann algorithm in Java, but am stuck at actually implementing the swap operation (see: Bentley-Ottmann on Wikipedia) that is needed when processing intersection points.

If I'm understanding the algorithm correctly, there are 3 different types of event points:

  1. Start-point: This is the leftmost point of a segment, add this segment to the tree and check if it intersects with the segments directly above and below this segment (if they exist)
  2. End-point: This is the rightmost point of a segment, remove this segment from the tree and check if the segments directly above and below intersect with eachother
  3. Intersection-point: This is the intersection point of two segments, swap the two segments' positions in the tree [...]

(I'm leaving out a lot of details since they aren't very relevant here)

I'm using a TreeMap as my data structure to store my segments. I don't think there is a swap operation for TreeMaps that lets you just swap two elements, so that's where I'm stuck.

Upvotes: 3

Views: 443

Answers (1)

Sneftel
Sneftel

Reputation: 41503

This comes up a lot when people try to implement Bentley-Ottmann. See, for example, Implementing Bentley–Ottmann Algorithm with an AVL tree .

tl;dr: You cannot use standard self-balancing binary tree implementations like TreeMap for the state structure in Bentley-Ottmann.

When most people use a balanced binary tree like an AVL tree or a Red-Black tree, it's coupled with an immutable ordering over the elements in the tree. 3 is always greater than 2. There will never be a need to swap them. But with Bentley-Ottmann, the ordering is a function of the sweep point, meaning the algorithm needs to directly participate with the tree in reordering elements. In some trees it's possible to hack in a mutable comparator, but even then the only way to convince the tree to rethink its ordering is to remove the element, update the comparator, and re-insert the element -- which is much, much slower than it should be.

Moreover, using a standalone (extrusive) tree structure makes it more difficult to achieve an optimal implementation, because of the frequency with which you directly access elements in the tree. When a line segment ends, you want to go straight to that segment's node in the tree in O(1), not meander along the tree to it in O(log n). That means that your Segment structure should serve double-duty as a tree node, not have some way to navigate to the tree node.

So the good news: You get to implement your own balanced binary tree! Have fun. ;-) If you haven't implemented one before, I suggest an AA tree. But if you're looking for more of a challenge, and would like a more exotic structure which tends to be a perfect match for Bentley-Ottmann's normal access patterns, try a Treap.

Looking in the other direction, if you want to get something working quickly and you don't care about the technical asymptotic bounds, consider just using a linked list for your state structure, locating nodes by a linear scan rather than a tree traversal. In my experience time to locate state nodes is rarely the bottleneck of a Bentley-Ottmann-involving system, and if you're only working with hundreds or thousands of segments, the logarithmic lookups of a binary tree will not be significant.

Upvotes: 5

Related Questions