Sweep Line Algorithm - Implementation for 1D plane

Question

The problem is simple, There is some given 1D lines on a plane. We need to find the total size of space having at least one line.

Let me discuss this with an example image-

This may a case. Or

This may be a case or anything like this.

I know it is a basic problem of Sweep Line Algorithm.

But there is no proper document in the internet for it to understand properly.

The one best I have is a blog of Top Coder and that is here.

But it is not clear how to implement it or how may be the simulation.

If I want, we can do it in O(n^2) with 2 loops, but I can't realize how would be the procedure.

Or is there any better algorithm better than that O(n log n)?

Can anyone help me by sharing any Sudo Code or a simulation?

If Sudo code or example code is not available, a simulation for understanding is enough from where I can implement this.

---

Re- Problem calculating overlapping date ranges is not what I am looking because firstly, it is O(n^2) and so, it is not what I want. And it is not fully described like this question.

Answer 1

There is not so much info available for this topic.

So, I am sharing algorithm and a simulation with you which created by me for you and it is also with O(n log n) !!!!!

Let's start-

1. Create a priority list of all action points (action points are the starting or ending point of a line). And each item of the PQ has 3 elements (Current Point, Start or End, Comes from what line). (O(n log n) operation if we use Quick Short for sorting).
2. Initialize a Vector for storing current active lines.
3. Initialize an array of size = no of lines + 1 (for storing sum of shadow length).

4. Now remove a item from PQ and run specific operation for that item like described in the following images and you are done.

0

1

2

3

4

5

6

7

8

9

10

11

5. And do it until the PQ is empty.

In your case, find the sum of all the elements of the array from 1 to end (index no 1 to m) and it is your answer.

But with this algorithm and array, you can easily have many more complex question answers like what is the length of space having 3 shadow = Arr3 and so on.

Now the question is what's about order, right?

So, Sorting = O(n log n) and sweeping = O(m) [m=no of action points, so m

So, total order is = O(n log n) + O(m) = O(n log n)

Think you can understand it easily and will be a great help for you and many others. And think you will be able to easily implement it.

Answer 2

Here's an approach that you may try (In C#. I've not tested it, so please forgive typo's and the like; just take the "idea"/strategy).

Performance is O(N log m), where m is the number of disjoint "shadows" you'll create. So, worst case (if ALL linesegments are disjoint with respect to their shadows) you'll have O(N logN), but when you only have few shadows it's essentially O(N).

  public class LineSegment
  {
    public int Begin;
    public int End;
    // assumed to INCLUDE Begin but EXCLUDE End, so that
    // length = End-Begin

    public LineSegment Clone()
    {
      LineSegment clone = new LineSegment();
      clone.Begin=this.Begin;
      clone.End = this.End;
      return clone;
    }
  }

public int TotalShadow(LineSegment[] segments)
{
  // Class LineSegment has int members Begin and End, and Clone method to create a (shallow) Copy.
  // Can/should be adapted if we're dealing with LineSegments with double/float coordinates.

  // Easy special cases: no segements at all, or precisely one.
  int N = segments.Length;
  if (N == 0)
    return 0;
  else if (N == 1)
    return (segments[0].End - segments[0].Begin);

  // build a list of disjoint "shadows", cast onto the x-axis by all line segments together,
  // sorted by their "Begin" (leftmost coordinate).
  List<LineSegment> shadows = new List<LineSegment>();
  // Initialize with the first segment, for convenient iteration below.
  shadows.Add(segments[0].Clone());

  for (int k = 1; k < N; ++k) // start at #1: we handled #0 already.
  {
    // find its position (Begin) in relation to the existing shadows (binary search).
    int xBegin = segments[k].Begin;

    int jLow = 0;
    int xLow = shadows[jLow].Begin;

    int jHigh, xHigh;
    if (xBegin <= xLow)
      jHigh = jLow; // avoid any more binary searching below
    else
    {
      jHigh = shadows.Count - 1;
      xHigh = shadows[jHigh].Begin;
      if (xBegin >= xHigh)
        jLow = jHigh; // avoid any more binary searching below
    }

    while (jHigh - jLow > 1)
    {
      int jTry = (jLow + jHigh) / 2;
      int xTry = shadows[jTry].Begin;

      if (xTry <= xBegin)
        jLow = jTry;
      else
        jHigh = jTry;
    }

    // If it starts BEFORE "low" we create a new one: insert at jLow;
    // Elseif x falls INSIDE "low", we merge it with low;
    // ELSE we create a new shadow "between" low and high (as regards Begin)
    // In all cases we'll make sure jLow points to the applicable shadow (new or existing).
    // Next we'll check whether it overlaps with adjacent higher-lying shadows; if so: merge.
    if (xBegin < shadows[jLow].Begin)
      shadows.Insert(jLow, segments[k].Clone()); // jLow now points to the inserted item
    else if (xBegin <= shadows[jLow].End)
    { // merge: extend existing low if applicable.
      if (segments[k].End > shadows[jLow].End)
        shadows[jLow].End = segments[k].End;
    }
    else // if (xBegin > shadows[jLow].End)
      shadows.Insert(++jLow, segments[k].Clone()); // jLow increased to point to the inserted item.

   // Try to merge, starting at the next higher lying shadow.
    jHigh = jLow + 1;
    while (jHigh < N && shadows[jLow].End >= shadows[jHigh].Begin)
      jHigh++; // jHigh will point to the first one that we do NOT merge with.

    if (jHigh > jLow + 1) // any merges?
    {
      if (shadows[jHigh - 1].End > shadows[jLow].End)
        shadows[jLow].End = shadows[jHigh - 1].End; // set the appropriate End.

      for (int jRemove = jHigh - 1; jRemove > jLow; --jRemove)
        shadows.RemoveAt(jRemove); // Remove all shadaow-entries that we've merged with.
    }
  }

  // Wrap up.
  int shadowTotal = 0;
  foreach (LineSegment shadow in shadows)
    shadowTotal += (shadow.End - shadow.Begin);

  return shadowTotal;
}

Answer 3

Make an array/list of structures containing segment end point coordinate X and +1 attribute for starting point and -1 attribute for ending point A. O(N)

Sort array by X key. O(NlogN)

Init CurrCount to zero, run through array, adding A attribute to CurrCount. O(N)

You'll get ranges where CurrCount is greater than zero (covered), and where CurrCount is zero (uncovered)

Answer 4

Maybe you can do slightly better than with blind sorting, with the following scheme, derived from MergeSort:

• assume you have two lists of non-overlapping intervals, sorted by increasing bounds;

• perform a merging step like in MergeSort (always move to the closest bound from each list), to compute the union of the intervals;

• based on the parity of the indexes from both lists, you can tell which bounds to emit (f.i. merging AB and CDEF with the ordering ACBDEF, the output will be ADEF).

This is a linear-time operation.

Equipped with this modified merge, you can implement a modified MergeSort, which starts with single intervals and recursively forms unions. In the end, you get a single list of intervals that will give you the requested size.

In the worst case, no bound will disappear and the process remains O(N Log(N)). But when sufficiently many interval unions do arise, the number of intervals decreases and the processing time can go down to linear O(N).

Answer 5

This isn't very complicated.

Form an array where you put all interval endpoint abscissas with a flag telling whether it is a starting or ending point.

Sort the array increasingly.

Then scan the array while updating a counter: a starting point increases it, an ending point decreases it.

The requested size is easily found from the values where the counter switches from zero to nonzero and conversely.

I don't think it is possible to make it faster than O(N Log(N)) because of the sort (which I don't think can be avoided), unless the data allows linear-time sorting (such as histogram sort).