c++ - Compute the "lower contour" of a set of segments in the plane in `O(n log n)` -

suppose you've set s of horizontal line segments in plane described starting point p, end point q , y-value.

we can assume values of p , qare pairwise distinct , no 2 segments overlap.

i want compute "lower contour" of segment.

we can sort s p , iterate through each segment j. if i "active" segment , j->y < i->y "switch to" j (and output corresponding contour element).

however, can do, when no such j exists , find j i->q < j->p. then, need switch "next higher segment". how know segment? can't find way such resulting algorithm have running time of o(n log n). ideas?

a sweep line algorithm efficient way solve problem. explained brian, can sort endpoints x-coordinate , process them in order. important distinction make here sorting endpoints of segment , not segments in order of increasing starting point.

if imagine vertical line sweeping left right across segments, notice 2 things:

• at position, vertical line either intersects set of segments or nothing. let's call set active set. lower contour segment within active set smallest y-coordinate.
• the x-coordinates lower contour can change segment endpoints.

this brings 1 observation: lower contour should list of segments. list of points not provide sufficient information define contour, can undefined @ x-coordinates (where there no segments).

we can model active set std::set ordered y position of segment. processing endpoints in order of increasing x-coordinate. when encountering left endpoint, insert segment. when encountering right endpoint, erase segment. can find active segment lowest y-coordinate set::begin() in constant time ordering. since each segment ever inserted once , erased once, maintaining active set takes o(n log n) time in total.

in fact, possible maintain std::multiset of y-coordinates each segment intersects sweep line, if easier.

the assumption segments non-overlapping , have distinct endpoints not entirely necessary. overlapping segments handled both ordered set of segments , multiset of y-coordinates. coinciding endpoints can handled considering endpoints same x-coordinate @ 1 go.

here, assume there no zero-length segments (i.e. points) simplify things, although can handled additional logic.

std::list<segment> lower_contour(std::list<segment> segments) {     enum event_type { open, close };      struct event {         event_type type;         const segment &s;         inline int position() const {             return type == open ? s.sp : s.ep;         }     };      struct order_by_position {         bool operator()(const event& first, const event& second) {             return first.position() < second.position();         }     };      std::list<event> events;     (auto s = segments.cbegin(); s != segments.cend(); ++s)     {         events.push_back( event { open, *s } );         events.push_back( event { close, *s } );     }     events.sort(order_by_position());      // maintain (multi)set of y-positions each segment intersects sweep line     // ordering allows querying lowest segment in o(log n) time     // multiset allows overlapping segments handled correctly     std::multiset<int> active_segments;      bool contour_is_active = false;     int contour_y;     int contour_sp;      // resulting lower contour     std::list<segment> contour;      (auto = events.cbegin(); != events.cend();)     {         auto j = i;         int current_position = i->position();         while (j != events.cend() && j->position() == current_position)         {             switch (j->type)             {                 case open:  active_segments.insert(j->s.y); break;                 case close: active_segments.erase(j->s.y);  break;             }             ++j;         }         = j;          if (contour_is_active)         {             if (active_segments.empty())             {                 // active segment ends here                 contour_is_active = false;                 contour.push_back( segment { contour_sp, current_position, contour_y } );             }             else             {                 // if current lowest position different previous one,                 // old active segment ends here , new active segment begins                 int current_y = *active_segments.cbegin();                 if (current_y != contour_y)                 {                     contour.push_back( segment { contour_sp, current_position, contour_y } );                     contour_y = current_y;                     contour_sp = current_position;                 }             }         }         else         {             if (!active_segments.empty())             {                 // new contour segment begins here                 int current_y = *active_segments.cbegin();                 contour_is_active = true;                 contour_y = current_y;                 contour_sp = current_position;             }         }     }      return contour; } 

as brian mentioned, binary heap std::priority_queue can used maintain active set , tends outperform std::set, if not allow arbitrary elements deleted. can work around flagging segment removed instead of erasing it. then, repeatedly remove top() of priority_queue if flagged segment. might end being faster, may or may not matter use case.