计算两个角度间隔的重叠

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

只要你有数字单调增加的间隔，那就很简单；您只需取max()最小值和min()最大值即可完成。看起来，这里的复杂性的主要来源是这样的事实：您可以将间隔环绕在 0 处，即，属于间隔的数字不是单调递增的。在我看来，解决这个问题的一种方法是简单地将环绕的间隔视为不是一个间隔，而是两个间隔的并集。例如，将 [5, 1] 视为 [5, 2 pi] \xe2\x88\xaa [0, 1]。那么求[5, 1]和[0, 6]交集的问题就变成了求[5, 2 pi]和[0, 6]交集以及[0, 1]交集的问题] 和 [0, 6]。从数学上讲，您将利用集合交集的分配律，即 (A \xe2\x88\xaa B) \xe2\x88\xa9 C = (A \xe2\x88\xa9 C) \xe2\ x88\xaa (B \xe2\x88\xa9 C)。因此，给定两个间隔 A 和 B，我们首先将每个间隔分为两个间隔，A1 和 A2，以及 B1 和 B2，其中 A1 和 B1 分别在 0 之后开始，在 2 pi 之前结束，A2 和 B2 在 2 pi 之前开始，在 2 pi 之前结束。像这样切分，我们可以像这样计算交叉点

\n\n

(A1 \xe2\x88\xaa A2) \xe2\x88\xa9 (B1 \xe2\x88\xaa B2) = (A1 \xe2\x88\xa9 (B1 \xe2\x88\xaa B2)) \xe2\x88 \xaa (A2 \xe2\x88\xa9 (B1 \xe2\x88\xaa B2) = (A1 \xe2\x88\xa9 B1) \xe2\x88\xaa (A1 \xe2\x88\xa9 B2) \xe2\ x88\xaa (A2 \xe2\x88\xa9 B1) \xe2\x88\xaa (A2 \xe2\x88\xa9 B2)

\n\n

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

\n