deblocker deblocker - 1 year ago 62
Javascript Question

Find all disjointed intersections in a set of vertical line segments

I have a set of vertical regions defined by y1 and y2 coordinates, where y1 is the starting point and y2 is the ending point of each region. Origin of my coordinates system is the top-left corner, so y2 is always greater than y1.

This is an example:

var regions = [
[10, 100],
[50, 120],
[60, 180],
[140, 220]

I would like to find out all disjointed intersections greater than a certain size, let say, for example, 20 units.

Until now I'm only able to get all intersections:
[50, 100],[60, 100],[60, 120],[140, 180]
but I'm expecting this result:
[60, 100],[140, 180]
Is there any algorithm to get this result?


Answer Source

I believe the question is clear. It requests the disjointed intersections in a given array of vertical edge ranges. Which means

[[10, 100], [50, 120], [60, 180], [140, 220]]

array gives us two disjointed intersection one being from [10, 100], [50, 120], [60, 180] and resulting [60,100] and the other being from [60, 180], [140, 220]] and resulting [140,180]. So as you notice the resulting intersections [60,100] and [140,180] those obtained from this given set of vertical edges are disjointed.

One way of implementing this functionality in JS is as follows;

function getDisjointedIntersections(a){
  var di;
  return a.reduce((p,c,i,a) => c.used ? p
                                      : (p.push(,j) => a[(i+j)%a.length])
                                                 .reduce((s,e) =>  (di = [Math.max(s[0],e[0]), Math.min(s[1],e[1])],
                                                                    di[0] < di[1] ? (e.used = true, di) : s))),p),[]);

var regions = [[10, 100],[50, 120],[60, 180],[140, 220],[150, 330]];

Explanation: At first it's easy to perceive the job as a simple reducing job but i guess it is not. There are cases you that you should consider the previous vertical edges so multiple passes might be required.

So we will start with the given array and start reducing our vertical edges into their intersection as much as we can. While doing so every vertical edge that results a successful intersection will be assigned a property named used with value true. Once this pass is finished we will rotate our input array up until an unused vertical edge comes to index position 0 and start reducing the vertical edges by intersection again but this time from an item that was not used previously.

So the heart of the code, the intersection reducer is

.reduce((s,e) =>  (di = [Math.max(s[0],e[0]), Math.min(s[1],e[1])],
                   di[0] < di[1] ? (e.used = true, di) : s))

This is a simple reduce without an initial. It first assigns the intersection to di.

di = [Math.max(s[0],e[0]), Math.min(s[1],e[1])]

and then if the intersection is successful then it marks the current element as used and returns di which will be the previous element of the next reduce cycle. If the intersection is not successful then it will return the previous intersection to the next reduce cycle.

di[0] < di[1] ? (e.used = true, di) : s))

Ok we have finished a cycle and only [10, 100], [50, 120], [60, 180] have intersected and resulted [60,100]. So we push this result to the outer reduces initial array.

(p.push(,j) => a[(i+j)%a.length])
         .reduce((s,e) => ... // the code that we already know

But what is the map function that we chained our reduce to. The map is rotating our input array by one index per the iteration of the outer reduce. OK have a look at it and you will understand how it does it's job

a.reduce((p,c,i,a) => c.used ? p
                             : (p.push(,j) => a[(i+j)%a.length])

But as you will also notice we are not making wasteful rotations. We first wait until our outer reduce's current element (c) meets an unused item. Only then we rotate the input array to form up our new input array. For instance the two input arrays that we have to work on this example are.

[ [ 10, 100 ],[ 50, 120 ],[ 60, 180 ],[ 140, 220 ],[ 150, 330 ] ]


[ [ 140, 220 ],[ 150, 330 ],[ 10, 100, used: true ],[ 50, 120, used: true ],[ 60, 180, used: true ] ]

So in this particular case just two passes marks all vertical edges as used and gives us all two disconnected intersections... regardless how many times you shuffle the input array.

It calculates a 1000 item input data in 15~16msecs and 10000 item data in about 400-500msecs. You may check the code and play with the parameters here