6

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

  • a1, a2, b1, b2 值在 -inf 和 +inf 之间
  • 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°，则将其分成两部分，但我不确定这是否涵盖所有情况，我想知道是否有一个优雅的公式。

4

4 回答 4

11

正如@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)
于 2012-08-02T12:00:47.650 回答
2

对于区间 [iX , iY] ，让我们定义归一化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)的区间重叠

或者

归一化（A） 与幻灯片的间隔重叠（归一化（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]的区间重叠

于 2012-08-02T12:04:27.017 回答
0

我在循环地图中重叠矩形的游戏引擎也有类似的问题。我已经考虑了很多，并查看了你们中的一些人的答案。如果你正在寻找性能，这是你能得到的最好的（直到有人证明我错了：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)

优雅的。优雅又丑陋。

于 2021-05-12T07:38:44.483 回答
-1

如何将每个度数标准化为 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)
于 2012-08-02T10:44:57.507 回答