检查同一圆上的两条线段是否重叠/相交。

Question

给定同一圆的两个圆弧：A=[a1，a2]和B=[b1，b2]，其中：

• a1，a2，b1，b2的值在-无穷大到+无穷大之间
• a1 <= a2; b1 <= b2
• a2-a1<=360; b2-b1<=360

如何确定这两个圆弧是否重叠？（即它们是否在至少一个点相交或接触）

示例：

A=[  -45°,    45°]; B=[   10°,   20°] ==> overlap
A=[  -45°,    45°]; B=[   90°,  180°] ==> no overlap
A=[  -45°,    45°]; B=[  180°,  360°] ==> overlap
A=[ -405°,  -315°]; B=[  180°,  360°] ==> overlap
A=[-3600°, -3601°]; B=[ 3601°, 3602°] ==> overlap (touching counts as overlap)
A=[ 3600°,  3601°]; B=[-3601°,-3602°] ==> overlap (touching counts as overlap)
A=[    -1°,    1°]; B=[ 3602°, 3603°] ==> no overlap 

这似乎是一个看似简单的问题，但我无法理解它。 目前我有一个基本的解决方案想法，其中涉及将每个段分成两个部分，如果它跨越0°的话，但我不确定是否覆盖了所有情况，我想知道是否有一种优雅的公式可以解决这个问题。

- HugoRune

---

可能是重复的问题：两个弧之间的交点？（弧=一对角度之间的距离） - High Performance Mark

由于您没有指定圆的半径或中心，我们是否应该假设这些弧都在同一个圆上？ - Chris

@HighPerformanceMark 我不认为那个问题是重复的。那个问题的答案涉及到对数组进行排序和管理相邻段列表。 - HugoRune

@Chris 是的，这些部分在同一个圆上；我在文本中已经提到了，但是标题可能不太清楚，我修改了问题标题以反映这一事实。 - HugoRune

@HighPerformanceMark，我刚看到你修改了链接；那个问题似乎确实相关，尽管它们只出现在0°和360°之间。答案似乎类似于我的基本想法，即分割线段，我很想知道这是否是解决我的问题的有效方法，以及是否有更好的方法？ - HugoRune

Answer 1

如@admaoldak所提到的，先将角度标准化：

a1_norm = a1 % 360
a2_norm = a2 % 360
b1_norm = b1 % 360
b2_norm = b2 % 360

现在要检查b1是否在(a1,a2)范围内，

def intersect(b, as, ae
    Intersect = False
    If as > ae:
        if b >= as or b <= ae:
            return True
    Else:
        if b>=as and b<=ae:
            return True
    return False

最终答案是：

intersect(b1_norm,a1_norm,a2_norm)||intersect(b2_norm,a1_norm,a2_norm)||
intersect(a1_norm,b1_norm,b2_norm)||intersect(a2_norm,b1_norm,b2_norm)

- ElKamina

---

谢谢！这是我使用的代码；虽然如果速度成为一个问题的话，我认为只检查 intersect(b1_norm,a1_norm,a2_norm)||intersect(a1_norm,b1_norm,b2_norm) 就足以涵盖所有情况。 - HugoRune

A=[-45°, 45°]; B=[180°, 359°] ==> 重叠 - Shaobo Zi

注意，对于负数，取模运算通常没有正确实现（我不知道Python是否有这种情况，但在大多数C语系的编程语言中都是如此）。 - mako

Answer 2

对于一个区间 [i.X, i.Y]，我们定义归一化值 i_norm = normalize(i)，使得：

1. 0 <= i_norm.X < 360
2. i_norm.X <=i_norm.Y

然后我们定义另一个操作 i_slide = slide(i)，以便：

1. i_slide.X = i.X + 360
2. i_slide.Y = i.Y + 360

我们可以证明，对于你的输入A和B，A圆形重叠 B当且仅当：

normalize(A) 区间重叠 normalize(B)

或者

normalize(A) 区间重叠 slide(normalize(B))

区间重叠 的定义与 adamoldak 帖子中的“交集”相同。

而且两个操作 normalize()和 slide() 都很容易实现。

以你的例子为例： A = [-45°，45°]；B=[10°，20°]，我们有

normalize(A) = [315,405] 
normalize(B) = [10,20] 
slide( normalize(B) ) = [370,380]

并且 [315,405] 区间重叠 [370,380]

- lavin

---

交换A和B，你的例子就会出问题。你需要检查norm(A)与norm(B)，slide(norm(A))与norm(B)以及norm(A)与slide(norm(B))之间的关系。 - Jxtps

Answer 3

我有一个类似的问题，涉及到游戏引擎中在循环地图中重叠的矩形。我已经思考了很久，并查看了一些你们的答案。如果你想要性能，这是你能得到的最好的（除非有人证明我错了 :P）：

#assume the angles are already normalised
def overlap(a1, a2, b1, b2):
  if a2 - a1 + b2 - b1 > 360: #must overlap
    return True
  return (b1 > a2) ^ (b2 > a1) ^ (a2 < a1) ^ (b2 < b1)

优雅。优雅而有点丑陋。

- BlobKat

Answer 4

将每个角度值归一化为0-360，怎么样？

a1_norm = a1 % 360
a2_norm = a2 % 360
b1_norm = b1 % 360
b2_norm = b2 % 360

然后你只需要检查是否有交集：

(a1_norm <= b2_norm) and (a2_norm<= b1_norm) 

- adamoldak

---

A=[-45°,45°]; B=[10°,20°] ==> A=[315°,45°]; B=[10°,20°]，尽管有重叠，但a1_norm > b2_norm。 - HugoRune