检查同一圆上的两个段是否重叠/相交
检查同一圆上的两个段是否重叠/相交
提问于 2012-08-02 10:18:40
给定同一圆圈的两个圆段: 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
Stack Overflow用户
回答已采纳
发布于 2012-08-02 12:00:47
正如@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)Stack Overflow用户
发布于 2012-08-02 12:04:27
对于间隔期i.X，i.Y，让我们定义规范化i_norm =正常化(I)，以便：
1. 0 <= i_norm.X < 360
2. i_norm.X <=i_norm.Y然后，我们定义了另一个操作i_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)间隔-与幻灯片重叠(标准化(B))
区间重叠的定义与在adamoldak的文章中的“交集”定义相同。
而且，、normalize()、和幻灯片()这两个操作都很容易实现。
举你的例子：A=[-45°,45°]; B=[10°,20°]，我们有
normalize(A) = [315,405]
normalize(B) = [10,20]
slide( normalize(B) ) = [370,380]315 405次间隔与370 380次重叠
Stack Overflow用户
发布于 2021-05-12 07:38:44
我有一个类似的问题，一个游戏引擎与矩形重叠在一个循环地图。我想了很多，看了你们中的一些答案。如果你在寻找性能，这是你能得到的最好的结果(直到有人证明我错了: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)优雅。优雅又丑陋。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/11775473
复制相关文章
相似问题
腾讯云开发者
