Search code examples
algorithmsortingsimulationimplementationmark-and-sweep

Sweep Line Algorithm - Implementation for 1D plane

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-

Seniario 1

This may a case. Or

Seniario 2

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.

Solution

  • 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).

    Data Structure

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

    Sim 0

    0

    Sim 1

    1

    2

    2

    3

    3

    4

    4

    5

    5

    6

    6

    7

    7

    8

    8

    9

    9

    10

    10

    End

    11

    1. 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.