6

同じ円の 2 つの円セグメントが与えられた場合: A=[a1, a2] と B=[b1, b2] の場合:

  • -inf と +inf の間の a1、a2、b1、b2 の値 (度単位)
  • a1 <= a2; b1 <= b2
  • a2-a1<=360; b2-b1<=360

これらの 2 つの円セグメントが重なっているかどうかを確認するにはどうすればよいですか? (つまり、少なくとも 1 点で交差または接触している場合)

例:

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° を横切る場合に 2 つに分割するという解決策の基本的なアイデアを持っていますが、それがすべてのケースをカバーするかどうかはわかりません。また、エレガントな式があるかどうか疑問に思っていました。

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と円で重なることを証明できるのは、次の場合のみです。

正規化(A) 間隔-正規化(B)と重複

また

normalize(A) スライドとの間隔の重複( normalize(B))

interval- overlaps は、adamolak の投稿の「交差」と同じ方法で定義されます。

また、 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 に答える
-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 に答える