CODEWITHSUNDEEP
c++algorithmstl
Robert Hönig
Robert Hönig

Reputation: 683

Implementing Bentley-Ottmann in C++ using the STL

I want to implement the Bentley-Ottmann line segment crossing algorithm based on this description, using STL elements. Bentley-Ottmann Wikipedia

What I am struggling with is the implementation of the priority queue. The description asks me to erase any intersection:

If p is the left endpoint of a line segment s, insert s into T. Find the segments r and t that are immediately below and above s in T (if they exist) and if their crossing forms a potential future event in the event queue, remove it. If s crosses r or t, add those crossing points as potential future events in the event queue.

It doesn't seem to be possible to use an STL priority queue as the event queue, since its searching complexity is linear and I would need to find and remove any crossing of s and t. Should I use a set instead? Or is it possible with a priority queue?

Upvotes: 1

Views: 1141

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59174

There are priority queue structures that you can quickly delete from, but they will require a lot of additional memory.

It is actually more efficient just to leave the r-t intersection in the queue. Then, when it comes time to process the event, just ignore it if it's invalid (because r and t are not adjacent) or if it's already been done.

In order to detect when r-t has already been done, just make sure that your priority queue is ordered by a total ordering, i.e., don't just compare the x value of the events. When multiple events have the same x value, use the identifiers of the segments involved to break ties. Then, when r-t appears multiple times in the queue, all of the occurrences will be together and you can just pop them all off in sequence.

Upvotes: 4

Related Questions