減少查找N線交點所需的時間

有N線段可以是水平或垂直。現在我需要找出每個線段的交點總數和交點總數。 N可以高達。我試着檢查每一對線。答案是正確的，但我需要減少它的時間。減少查找N線交點所需的時間

這裏是我的代碼：

using namespace std; 

typedef struct Point 
{ 
    long long int x; 
    long long int y; 
} ; 


bool fun(Point p0, Point p1, Point p2, Point p3) 
{ 
    double s1_x, s1_y, s2_x, s2_y; 
    s1_x = p1.x - p0.x;  s1_y = p1.y - p0.y; 
    s2_x = p3.x - p2.x;  s2_y = p3.y - p2.y; 

    double s, t; 
    s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y))/(-s2_x * s1_y + s1_x * s2_y); 
    t = (s2_x * (p0.y - p2.y) - s2_y * (p0.x - p2.x))/(-s2_x * s1_y + s1_x * s2_y); 

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1) 
    { 
     return 1; // Collision detected 
    } 

    return 0; // No collision 
} 


int main() 
{ 
    long long int n // number of line segments; 

    Point p[n],q[n]; // to store end points of line segments 

    for(long long int i=0;i<n;i++) 
    { 

// line segments is defined by 2 points P(x1,y1) and Q(x2,y2) 
     p[i].x=x1; 
     p[i].y=y1; 
     q[i].x=x2; 
     q[i].y=y2; 
    } 

    for(long long int i=0;i<n-1;i++) 
    { 
     for(long long int j=i+1;j<n;j++) 
     { 
      if(fun(p[i],q[i],p[j],q[j])) 
       count++; 
     } 

    } 

    return 0; 
}

有人能幫助我減少這個程序的時間複雜度？

來源

2016-11-12 sammy

如果它們是水平或垂直的，那麼檢查交點比任意線更容易（如在你的方法中）。此外，從x/y座標開始排序。然後你知道可能的交叉點必須在哪個區域。更復雜的方法是使用分段樹或間隔樹。 –

同一位老師還是比賽？ http://stackoverflow.com/questions/40570886/c-modified-line-segment-intersection – MBo

請參閱[用C＃實現Hoey Shamos算法]（http://stackoverflow.com/q/18512815/2521214）兩個答案.. – Spektre

這是O（n log n）時間算法，它使用Fenwick樹的掃描線。

步驟0：座標重新映射

排序的x座標和由一個整數0..N-1替換的每個值，以便保存順序。對y座標做同樣的操作。交集屬性被保留，同時允許下面的算法更容易實現。

步驟1：平行的線段

我將描述該步驟對於水平段。對垂直線段重複。

將水平線段按y座標分組。一次處理一個組，爲掃描線創建事件如下。每個段在其較小的端點處獲得一個啓動事件，而在較大的端點處收到一個停止事件。如果您想要封閉的線段，排序會在停止之前開始。按排序順序掃描事件，跟蹤當前與掃描線相交的線段數量和處理的開始事件數量。段的平行交叉點的數量爲（在開始時間相交的段的數量+在停止時間處理的開始事件的數量 - 在開始時間處理的開始事件的數量）。（也可用於礦井的此以前的說明，請參見Given a set of intervals, find the interval which has the maximum number of intersections）

步驟2：垂直線段

我將在每個水平線段計數術語描述該步驟多少垂直線段它相交。

我們做另一個掃描線算法。這些事件是水平段開始，垂直段和水平段停止，按假定閉合線段的順序排序。我們使用Fenwick樹跟蹤每個y座標到目前爲止有多少垂直段覆蓋了y座標。要處理水平啓動，請從其交點計數中減去其y座標的樹值。要處理水平停止，請將其y座標的樹值添加到其交點計數。這意味着計數會隨着差值而增加，差值是激活時水平段的垂直段的數量。要處理垂直分段，請使用Fenwick樹的功能快速遞增其較小y座標與其較大值（包含假設閉合分段）之間的所有值。

如果需要，可以組合這些掃描線算法。爲了說明理由，我將它們分開。

來源

2016-12-31 20:48:36

減少查找N線交點所需的時間

回答

相關問題