Sorting segments from high to low

Question

I have a set of segments. None of them intersect or touch each other, and none of them have slope $0$ or infinity (i.e. the endpoints have different $x$ and $y$). All segments have length $> 0$.

What I want to achieve is, a sorting order similar to what would happen if they were ceilings in a house and rain falls on them. If rain falls on a segment $i$ which covers completely or partially $j$, then segment $i$ goes before $j$ in the order desired.

In the figure above, the order would be (using the black letters, not the blue ones):

h → f → g → i → k → j

Note that some other orderings are also possible, like for example:

h → f → g → i → j → k

What I have tried so far:

• Sweep line algorithm. I tried a vertical and horizontal approach, but got nowhere.
• Sorting the segments with C++'s sort procedure. I tried several comparators, for example using the cross product to check the orientation of one segment's endpoints against the compared segment, etc. I tried several ways, but none worked. Corner cases kept appearing.

I've also been thinking about somehow turning it into a graph and running some algorithm similar to topological sort. This idea is still in development and have no progress as of yet.

I think sweep line might work, but I don't exactly what and how to implement.

Any ideas appreciated.

Answer 1

For a point $A$, its coordinates are $(A_x, A_y)$.

When does a line segment cover another line segment?

Suppose we have line segments $\overline{AB}$ and $\overline{CD}$. Assume $A_x\le B_x$ and $C_x\le D_x$.

Let $k_{\ell}$ be the slope of line segment $\ell$. Let $m=\max(A_x,C_x)$.

• $P:=A$ if $k_{\overline{AB}}$ is infinity. Otherwise, $P:=(m,A_x+k_{\overline{AB}}(m-A_x))$.
• $Q:=C$ if $k_{\overline{CD}}$ is infinity. Otherwise, $Q:=(m,C_x + k_{\overline{CD}}(m-C_x)$.

So, $P$ and $Q$ are points on $\overline{AB}$ and $\overline{CD}$ respectively that share the same $x$-coordinate.

Then $$\begin{aligned} \overline{AB}\text{ covers }\overline{CD}\ &\iff \ m\le \min(B_x,D_x) \text{ and } P_y\gt Q_y \\ \overline{CD}\text{ covers }\overline{AB}\ &\iff \ m\le \min(B_x,D_x) \text{ and } P_y\lt Q_y \\ \end{aligned}$$

The algorithm, which uses topological sort

1. For each line segment $g$, collect all line segments covered by it into a list, which will be denoted by $\mathcal C[g]$.
2. Let $stack$ be an empty stack and $visited$ be an empty set.

Define recursive function "$\mathsf{topo\_sort}$", mimicking Python syntax.
$\quad\quad$function $\mathsf{topo\_sort}$(line segment $high$):
$\quad\quad\quad\quad$if $high$ is not in $visited$:
$\quad\quad\quad\quad\quad\quad$Add $high$ to $visited$
$\quad\quad\quad\quad\quad\quad$for each line segment $low$ in $\mathcal C[high]$:
$\quad\quad\quad\quad\quad\quad\quad\quad$$\mathsf{topo\_sort}$(line segment $low$)
$\quad\quad\quad\quad\quad\quad$append $high$ to $stack$

3. For each line segment $h$, call $\mathsf{topo\_sort}$($h$).
4. Return all elements in $stack$ in the natural order of a stack.

The algorithm above runs in $O(n^2)$-time, where $n$ is the number of line segments, because of step 1.

A vertical sweep line

Let us use a vertical sweep line to implement the step 1 above, which will boost performance especially when there are not many pairs of covering line segments.

1. Initialize an empty map $\mathcal C$ and an empty set $S$.
2. Sort all endpoints of all line segments by $x$-coordinate.
3. For each endpoint $e$, do the following.
   • If $e$ is the left endpoint of line segment $r$.
     • For each line segment $\ell$ in $S$,
       • If $r$ covers $\ell$, add $\ell$ to $\mathcal C[r]$.
       • Else $\ell$ must cover $r$. Add $r$ to $\mathcal C[\ell]$.
     • Add $r$ to $S$.
   • Otherwise, $e$ is the right endpoint of some line segment $r$. Remove $r$ from $S$.

With this sweep line technique, the time-complexity of the algorithm is $O(\max(n\log n, c))$ where $c$ is the number of covering pairs.

Answer 2

I found an algorithm similar to the one posted by John, but with lower complexity.

First start by creating a comparator for the segment. This comparator is only used for the sweep line and doesn't work elsewhere, i.e. doesn't give you an actual topological order, but does give you a "partial" (?) order during the sweep line. This exploits the fact that during the sweep line, the segment events enter in order from left to right.

struct Segment {
  Point p, q; // endpoints

  // "to_vec()" transforms the segment to a vector
  // "^" is the operator for cross product.
  // "to" creates a vector from A to B

  bool operator<(const Segment& s) const {
    if (p.x < s.p.x) {
      // "this" enters first (in the sweep line)
      return (to_vec() ^ p.to(s.p)) < 0;
    } else {
      // "this" enters after the one being compared
      return (s.to_vec() ^ s.p.to(p)) > 0;
    }
  }
}

Then the sweep line.

Before starting, sort the segments by ascending X coordinate (only left endpoint). Then, assign an idx (index) starting from 0 to each segment. This must be done after sorting for the following code to work properly.

I explain the sweep line in the comments:

typedef pair<int, int> pii;

// ....

// Sort segments by left endpoint X
sort(segments.begin(), segments.end(),
       [](const Segment& a, const Segment& b) { return a.p.x < b.p.x; });

// Create a graph with the same amount of segments +1.
// The last node will be used for a imaginary node that's the
// starting point (i.e. imagine it coming from Y=infinite above)
vector<vector<int>> graph(N + 1);

// Assign an ID to each segment
for (int i = 0; i < N; i++) segments[i].idx = i;

// Create a Segment set. Starts empty.
// Note that this is a set with order (tree set)
set<Segment> s;

// Create a priority queue containing integer pairs.
// Order of the queue is ascending.
priority_queue<pii, vector<pii>, greater<pii>> events;

// For every segment
for (int i = 0; i < N; i++) {
  // Iterate through all the events in the priority queue until
  // the X value in the queue becomes higher than the current left endpoint
  // X value. In other words consume all values that are to the left of the
  // current segment. Delete them from the set as well as from the queue.
  while (!events.empty() && events.top().first < segments[i].p.x) {
    s.erase(segments.at(events.top().second));
    events.pop();
  }

  // Insert the segment in the set. This order won't be topological,
  // but it's enough for the current sweep line state.
  auto it = s.insert(segments[i]).first;

  // If the segment inserted is the first one in the set, then add it
  // to the imaginary node. Else add it to the previous one.
  // This is the step that gets faster than the algorithm of the accepted
  // answer, since we can find where to insert it in just one O(log N) step,
  // without caring how many covered segments there are.
  if (it == s.begin())
    graph[N].push_back(i);
  else
    graph.at((--it)->idx).push_back(i);

  // Insert the right endpoint X to the priority queue along with the current
  // segment index.
  events.push({segments[i].q.x, i});
}

Also it seems that idx must be set to each segment after sorting. By doing this, when doing the toposort it will deal with some corner cases such as:

Segment 1 enters the vertical sweep line. It's not covered, so it's parent in the DAG is the extra imaginary node. Segment 2 enters the vertical sweep line and it covers 1. It's not covered, so it's parent is the extra imaginary node.

But we didn't set segment 2 to be parent of segment 1. However, there's no problem, because when doing the toposort, and if we do it in the correct order, the post order traversal will be 1 2 0 (zero being the extra node), so we invert the array and remove the first element, becoming 2 1, which means that the segment 2 does cover 1 (although it may not necessarily cover it in some situations).

In other words, with this approach the resulting graph will have some edges "missing", but when you do the toposort, the segments which left endpoint X coordinate is higher will appear first in the toposort result anyway, so the missing edges don't matter.

UPDATE: My code is here:

https://github.com/ChrisVilches/Algorithms/blob/main/spoj/RAIN1-november_rain.cpp

I refactored it a bit, so it's slightly different from annotated code I wrote above (for example instead of assigning a idx property, I just use the actual index in the array, and pass it to the set grouped as a pair<Segment, int>). Take a look at the vector<Segment> sort_segments(vector<Segment>& segments) method (also the structs and toposort are of interest, maybe).

This program solves the November Rain problem (https://www.spoj.com/problems/RAIN1/) which only has 40,000 segments and at most 25 segments being covered at each X coordinate, so a slower algorithm works. But there's a more complicated problem called Directing Rainfall (https://open.kattis.com/problems/directingrainfall - I haven't solved it yet) which requires a similar algorithm, but does not have any limit for how many segments are covered. I learnt this algorithm by checking some existing solutions to that last problem.

Alternative implementation:

A different implementation done by adding two events per each segment (enter and exit). The only problem is that there's a corner case for when there are two segments with endpoints with equal X coordinate, so I added +1 to the exiting coordinate. The previous implementation using a priority queue is safer, since it doesn't need to deal with this corner case.

  set<pair<Segment, int>> s;
  vector<tuple<ll, bool, int>> events;

  for (int i = 0; i < N; i++) {
    events.push_back({segments[i].p.x, true, i});
    events.push_back({segments[i].q.x + 1, false, i});
  }

  sort(events.begin(), events.end());

  for (const auto& [_, enter, idx] : events) {
    if (enter) {
      const auto it = s.insert({segments[idx], idx}).first;
      graph[it == s.begin() ? N : prev(it)->second].push_back(idx);
    } else {
      s.erase({segments[idx], idx});
    }
  }