1
$\begingroup$

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.

Ceilings

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.

$\endgroup$
2
  • $\begingroup$ There is a possible sweep-line algorithm. If this is an exercise from a course you should be vaguely familiar with how a sweep-line algorithm works. So as a hint: the events are upper points and the lower points of the segments sorted by y-coord. A segment is added to the sorted list if either its lower point is reached and no other segment covers it or another segment is removed and a segment that was covered by it is now not covered by any other segment. $\endgroup$
    – plshelp
    Mar 17, 2022 at 18:10
  • $\begingroup$ Think visible from high above. $\endgroup$
    – greybeard
    Mar 18, 2022 at 8:32

2 Answers 2

2
$\begingroup$

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$

  1. For each line segment $h$, call $\mathsf{topo\_sort}$($h$).
  2. 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.

$\endgroup$
2
  • $\begingroup$ Thanks. I ended up using this, and seems to work. There are not many segments being covered at each $X$ point, so this is good enough (it there were many, that'd be a bottleneck). I don't understand the toposort so I ended up creating a graph and running the vanilla toposort algorithm. And for detecting covering, I just used cross product while doing the sweep line, but I guess it works the same as your technique. $\endgroup$ Mar 19, 2022 at 4:58
  • $\begingroup$ @ChrisVilches Glad to hear you have solved the problem. I just rephrased the method topo_sort so that it is the same as the vanilla topologicalSort here. $\endgroup$
    – John L.
    Mar 19, 2022 at 7:03
0
$\begingroup$

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});
    }
  }
$\endgroup$
2
  • $\begingroup$ Could you share your working code? For example, go to ide.geeksforgeeks.org. Select "C++14". Paste your code there. Click "Run+URL (Generates URL as well)" button. Paste the generated URL here. $\endgroup$
    – John L.
    Mar 19, 2022 at 21:32
  • $\begingroup$ @JohnL. I updated my answer and posted my code. $\endgroup$ Mar 20, 2022 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.