计算两个角度间隔的重叠

Question

假设我有两个间隔，

[a1, a2] and [b1, b2]

其中a1,a2,b1,b2都在[0, 2 pi]范围内。现在，给定这两个间隔，我想找到它们的重叠间隔。这非常棘手。由于两个区间的例子是

[5, 1] and [0, 6]

下面描绘了（红色区域是间隔）。

请注意，这两个间隔返回一个由两个间隔组成的重叠间隔：

[0,1] and [5,6]

必须处理多种不同的情况，是否有任何已知的算法可以做到这一点？

Answer 1

我不知道现有的算法（这并不意味着没有算法），但这是我提出的算法。

正如@Michael Kenzel已经提到的那样，数字不会单调增加，这使得一切都变得非常复杂。

但我们可以观察到我们可以将圆圈展开到数字线上。然后每个间隔无限次出现，周期为2π。

我们首先定义一个规范化操作，如下所示：

normalize([a, b]):
    if (a > b):
        a -= 2π

使用此操作，我们将两个间隔展开到数字线的[-2π，2π]部分。

示例间隔：

[2, 5] -> [2, 5]

[4，π] - > [-2，π]

圆上的两个间隔最多可重叠2次。

（我没有这方面的正确证据，但直观地说：重叠开始于一个间隔开始而另一个间隔尚未结束。在数字线上只发生一次，在我们的情况下只发生两次。）

通过查看标准化间隔，我们可以错过其中一个重叠。在上面的例子中，我们将检测[2，π]重叠和未命中[4,5]。发生这种情况是因为我们已经将原始间隔展开到[0,2π]上，而是将数字线的两倍长部分展开，[ - 2π，2π]。

为了纠正这个问题，例如，我们可以采取落在负线上的部分并将其向右移动2π，这样就可以将所有部分都放在原始的[0,2π]中。但它在计算上是无效的，因为在最坏的情况下，我们必须在一个间隔上测试2个片段而不是另外2个片段 - 总共4个操作。

以下是一个需要进行4次比较的不幸示例的说明：

如果我们想要更有效率，我们将尝试仅进行2次间隔与间隔操作。我们不需要更多，因为最多会有2个重叠。由于区间在数字线上无限重复，周期为2π，我们可以只取第一个区间的2个相邻副本，并将它们与第二个区间进行比较。为了确保第二个区间，也就是说，在这些重复区间之间，我们可以采用先前开始的区间并在其两端添加2π。或者从稍后开始的那个中减去2π。

将存在不超过两个重叠，然后可以通过2π的加/减来使其返回到[0,2π]区间。

在我们的原始示例中，它看起来像这样：

把它们加起来：

given [a, b], [c, d]
[A, B] = normalize([a, b])
[C, D] = normalize([c, d])
if (A < C):
    [E, F] = [A + 2π, B + 2π]
else:
    [E, F] = [A - 2π, B - 2π]
I_1 = intersect([A, B], [C, D])
I_2 = intersect([E, F], [C, D])
bring I_1 and I_2 back to the [0, 2π]

我想我没有错过任何角落案例，但我可以随意指出我的逻辑中的任何错误。

Answer 2

只要你有数字只是单调增加的间隔，它就很简单;你只需要拿最小值的max()和最大值的min()完成。似乎这里复杂化的主要原因是你可以将间隔环绕在0处，即，作为间隔一部分的数字不是单调增加的。在我看来，绕过这个问题的一种方法是简单地处理包围的区间，而不是一个区间，而是两个区间的联合。例如，将[5,1]视为[5,2 pi]∪[0,1]。那么找到[5,1]和[0,6]的交点的问题变成了找到[5,2 pi]和[0,6]的交点以及[0,1]的交点的问题。 ]和[0,6]。在数学上，你将利用distributive law of set intersection，即（A∪B）∩C=（A∩C）∪（B∩C）。因此，给定两个间隔A和B，我们首先将每个间隔分成两个间​​隔，A1和A2，以及B1和B2，其中A1和B1各自在0之后开始并在2 pi之前结束，而A2和B2在2 pi之前开始并且在2 pi之前结束。像这样分切，我们可以计算我们的交叉点

（A1∪A2）∩（B1∪B2）=（A1∩（B1∪B2））∪（A2∩（B1∪B2）=（A1∩B1）∪（A1∩B2）∪（A2∩B1）∪（ A2∩B2）

即，计算A1，A2，B1和B2的所有组合的交集......