在一组垂直线段中查找所有脱节的交叉点 [英] Find all disjointed intersections in a set of vertical line segments

问题描述

我有一组由y1和y2坐标定义的垂直区域，其中y1是起点，y2是每个区域的终点。我的坐标系的原点是左上角，所以y2总是大于y1。

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.

这是一个例子：

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

我想找出所有超过一定大小的脱节交叉点，比如说， 20个单位。

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

到目前为止，我只能得到所有的交叉点： [50,100]，[60,100]，[60,120] ，[140,180] 但我期待这个结果： [60,100]，[140,180] 。
有没有算法可以得到这个结果？

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?

小提琴： https://jsfiddle.net/4v5qnex5/

推荐答案

我相信问题很清楚。它在给定的垂直边缘范围数组中请求脱节的交叉点。这意味着

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]]

数组给我们两个脱节的交叉点来自 [10,100] ，[50,120]，[60,180] ，结果 [60,100] ，另一个来自 [60 ，180]，[140,220]] 并得到 [140,180] 。因此，当您注意到结果交叉点 [60,100] 和 [140,180] 从这组给定的垂直边缘获得的那些是脱节。

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.

在JS中实现此功能的一种方法如下：

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(a.map((_,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]];
console.log(getDisjointedIntersections(regions));

说明：首先，很容易将工作视为简单的减少工作，但我想不是。有些情况下你应该考虑以前的垂直边缘，因此可能需要多次传递。

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.

所以我们将从给定的数组开始并开始将我们的垂直边缘减少到他们的交叉尽可能多。这样做的每个垂直边缘都会导致成功的交叉点被分配一个名为的属性，其值为 true 。完成此传递后，我们将向上旋转输入数组，直到未使用的垂直边缘到达索引位置0并再次开始通过交叉点减少垂直边缘，但这次是从之前未使用的项目开始。

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

这很简单减少没有初始。它首先将交集分配给 di 。

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])]

然后如果交集成功则将当前元素标记为已使用并返回 di ，这将是下一个缩减周期的前一个元素。如果交叉点不成功，那么它将返回上一个交叉点到下一个减少周期。

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

好的，我们已完成一个周期 [10,100]，[50,120]，[60,180] 相交并导致 [60,100] 。因此我们将此结果推送到外部减少初始数组。

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(a.map((_,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(a.map((_,j) => a[(i+j)%a.length])
                                 .redu...

但是你也会注意到我们没有浪费轮换。我们先来等到我们的外部reduce的当前元素（ c ）遇到一个未使用的项目。然后我们旋转输入数组以形成我们的新输入数组。例如两个输入数组我们必须研究这个例子。

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.

计算15~16msecs的1000项输入数据和400-500msecs的10000项数据。您可以查看代码并使用参数此处

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

确定以下版本被修改为仅显示允许的大小脱节交叉点。您可以尝试此处，了解不同数量的垂直边，轴大小和脱节交叉点的最小尺寸。

OK the following version is modified to show only the allowed size disjointed intersections. You might like to try here for different number of vertical edges, axis sizes, and minimum size of disjointed intersections.

function getDisjointedIntersections(a,n){
  var di,                                  // disjointed intersections
      ri;                                  // resulting intersections
  return a.reduce(function(p,c,i,a){
                    if (c.used) return p;
                    ri = a.map((_,j) => a[(i+j)%a.length])
                          .reduce(function(s,e){
                                    di = [Math.max(s[0],e[0]), Math.min(s[1],e[1])];
                                    return di[0] < di[1] ? (e.used = true, di) : s;
                                  });
                    ri[1] - ri[0] > n && p.push(ri);
                    return p;
                  },[]);
}

var regions = [[10, 100],[50, 120],[60, 180],[140, 220],[150, 330]];
console.log(getDisjointedIntersections(regions,20));

这篇关于在一组垂直线段中查找所有脱节的交叉点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！