兩個圓形扇區的交集

Question

我想解決簡單的任務，但我沒有找到任何優雅的解決方案。

我基本上解決了兩個圓形扇區的交集。 每個扇區由（-pi，PI]範圍內2角（從ATAN2 FUNC）給出。 每個選擇佔據179.999最大角度。因此，它可以是告訴每兩個角度其中圓形扇區。

返回值應描述了基於相互交叉點上以下內容：

value <1 if one angle is contained by second one (value represents how much space occupy percentually)

value >1 if first angle (the dotted one) is outside the other one, value represents how much of dotted angle is out of the other one

基本情況和一些例子是在圖像波紋管

的問題是，有應處理的，我尋找一些優雅的方式來解決這麼多的情況下。

只有當它們位於單位圓的右側（cos> 0）時，我纔可以比較兩個角度，因爲在左側，數字上較大的角度在圖形上較低。我試圖用一些投影右半：

if(x not in <-pi/2, pi/2>) 
{ 
    c = getSign(x)*pi/2; 
    x = c - (x - c); 
} 

，但有一個問題，它佔用單位圓的兩半部分行業...

有這麼多的情況下...是否有人知道如何優雅地解決這個問題？ （我使用C++，但任何提示或僞代碼是罰款）

Answer 1

你可以做到以下幾點：

1. 每個扇區正常化的形式（s_start，s_end），其中s_start是在（-pi，PI ]和s_end [s_start,s_start+pi）。
2. 排序（交換）的扇區，使得s0_start < s1_start

3. 現在我們僅3例（A，B1，B2）：

   一個）s1_start <= s0_end：路口，內S0 s1_start

   b ）s1_start > s0_end：

   B1）s0_start + 2*pi <= s1_end：內部S1相交，（s0_start + 2 * PI）

   B2）s0_start + 2*pi > s1_end：沒有交集

因此我們得到如下代碼：

const double PI = 2.*acos(0.); 
struct TSector { double a0, a1; }; 

// normalized range for angle 
bool isNormalized(double a) 
{ return -PI < a && a <= PI; } 
// special normal form for sector 
bool isNormalized(TSector const& s) 
{ return isNormalized(s.a0) && s.a0 <= s.a1 && s.a1 < s.a0+PI; } 

// normalize a sector to the special form: 
// * -PI < a0 <= PI 
// * a0 < a1 < a0+PI 
void normalize(TSector& s) 
{ 
    assert(isNormalized(s.a0) && isNormalized(s.a1)); 

    // choose a representation of s.a1 s.t. s.a0 < s.a1 < s.a0+2*PI 
    double a1_bigger = (s.a0 <= s.a1) ? s.a1 : s.a1+2*PI; 
    if (a1_bigger >= s.a0+PI) 
    std::swap(s.a0, s.a1); 
    if (s.a1 < s.a0) 
    s.a1 += 2*PI; 

    assert(isNormalized(s)); 
} 

bool intersectionNormalized(TSector const& s0, TSector const& s1, 
          TSector& intersection) 
{ 
    assert(isNormalized(s0) && isNormalized(s1) && s0.a0 <= s1.a0); 

    bool isIntersecting = false; 
    if (s1.a0 <= s0.a1) // s1.a0 inside s0 ? 
    { 
    isIntersecting = true; 
    intersection.a0 = s1.a0; 
    intersection.a1 = std::min(s0.a1, s1.a1); 
    } 
    else if (s0.a0+2*PI <= s1.a1) // (s0.a0+2*PI) inside s1 ? 
    { 
    isIntersecting = true; 
    intersection.a0 = s0.a0; 
    intersection.a1 = std::min(s0.a1, s1.a1-2*PI); 
    } 
    assert(!isIntersecting || isNormalized(intersection)); 

    return isIntersecting; 
} 

main() 
{ 
    TSector s0, s1; 
    s0.a0 = ... 
    normalize(s0); 
    normalize(s1); 
    if (s1.a0 < s0.a0) 
    std::swap(s0, s1); 
    TSection intersection; 
    bool isIntersection = intersectionNormalized(s0, s1, intersection); 
}