計算相鄰框的數量

假設我有一組1000（X，Y）座標的框。計算相鄰框的數量

  ( x1, y1) ( x2, y2)  Area 

     (0.0000,0.0000) (0.3412,0.4175) 0.1424 
     (0.7445,0.0000) (1.0000,0.6553) 0.1674 
     (0.7445,0.6553) (1.0000,1.0000) 0.0881 
     (0.0000,0.6553) (0.7445,1.0000) 0.2566 
     (0.3412,0.0000) (0.7445,0.4175) 0.1684 
     (0.3412,0.4175) (0.7445,0.6553) 0.0959 
     (0.0000,0.4175) (0.3412,0.6553) 0.0812 ....etc

我想用c/C++來計算每個盒子的相鄰盒子的數量。我該怎麼做？

例

enter image description here

在這張照片中，相鄰盒框中-7的總數量爲6個，對於盒-3是三。我如何使用C++來計算它們？

編輯和新的價值觀更新

讓我們試一下16值 -

1 0.0000 0.0000  0.8147 0.1355 
2 0.8147 0.0000  1.0000 0.1355 
3 0.8147 0.1355  0.9058 0.8350 
4 0.0000 0.1355  0.1270 0.9689 
5 0.9058 0.1355  0.9134 0.2210 
6 0.9058 0.8350  1.0000 1.0000 
7 0.8147 0.8350  0.9058 1.0000 
8 0.1270 0.1355  0.6324 0.3082 
9 0.1270 0.9689  0.8147 1.0000 
10 0.0000 0.9689  0.1270 1.0000 
11 0.9134 0.1355  1.0000 0.2210 
12 0.9134 0.2210  1.0000 0.8350 
13 0.9058 0.2210  0.9134 0.8350 
14 0.6324 0.1355  0.8147 0.3082 
15 0.6324 0.3082  0.8147 0.9689 
16 0.1270 0.3082  0.6324 0.9689

這些值的單位正方形變成了這個樣子圖片 -

enter image description here

並更新了代碼 -

#include <iostream> 
    #include <cstdlib> 
    #include <vector> 

    using namespace std; 

    class Rect { 
    public: 
     double x1, x2, y1, y2; // assuming x1 <= x2 and y1 <= y2 

     Rect(double X1, double Y1, double X2, double Y2) { 
     if (X1 < X2) { 
      x1 = X1; x2 = X2; 
     } else { 
      x2 = X1; x1 = X2; 
     } 
     if (Y1 < Y2) { 
      y1 = Y1; y2 = Y2; 
     } else { 
      y2 = Y1; y1 = Y2; 
     } 
     } 

     bool isAdjacent(Rect rect) { 

    //for x-axis 
      if (x1 == rect.x2 || x2 == rect.x1) {  
    // use only < when comparing y1 and rect.y2 avoids sharing only a corner 
        if (y1 >= rect.y1 && y1 < rect.y2) { 
        return true; 
        } 
        if (y2 > rect.y1 && y2 <= rect.y2) { 
        return true; 
        } 
    }    
    // for y-axis  

       if (y1 == rect.y2 || y2 == rect.y1) { 
       if (x1 >= rect.x1 && x1 < rect.x2) { 
        return true; 
        } 
        if (x2 > rect.x1 && x2 <= rect.x2) { 
        return true; 
        } 
       } 

       return false; 

    } 
    }; 

int main() { 

     vector<Rect> rects;  

     rects.push_back(Rect(0.0000,0.0000, 0.8147,0.1355)); 
     rects.push_back(Rect(0.8147,0.0000, 1.0000,0.1355)); 

     rects.push_back(Rect(0.8147,0.1355, 0.9058,0.8350)); 
     rects.push_back(Rect(0.0000,0.1355, 0.1270,0.9689)); 

     rects.push_back(Rect(0.9058,0.1355, 0.9134,0.2210)); 
     rects.push_back(Rect(0.9058,0.8350, 1.0000,1.0000)); 
     rects.push_back(Rect(0.8147,0.8350, 0.9058,1.0000)); 



     rects.push_back(Rect(0.1270,0.1355, 0.6324,0.3082)); 
     rects.push_back(Rect(0.1270,0.9689, 0.8147,1.0000)); 
     rects.push_back(Rect(0.0000,0.9689, 0.1270,1.0000)); 

     rects.push_back(Rect(0.9134,0.1355, 1.0000,0.2210)); 
     rects.push_back(Rect(0.9134,0.2210, 1.0000,0.8350)); 
     rects.push_back(Rect(0.9058,0.2210, 0.9134,0.8350)); 


     rects.push_back(Rect(0.6324,0.1355, 0.8147,0.3082)); 
     rects.push_back(Rect(0.6324,0.3082, 0.8147,0.9689)); 
     rects.push_back(Rect(0.1270,0.3082, 0.6324,0.9689)); 

int adj_count = 0; 
     int b; 
     cin>>b; 

     for (int x = 0; x < rects.size(); ++x) { 


     if (rects[b].isAdjacent(rects[x])) { 


    if (x==b) { 
     continue; //this is our rectangle , so do not count it. 
    } 


      adj_count++; 
     cout << "rect["<<(b+1)<<"] is adjacent with rect["<<(x+1)<<"]"<<endl; 


    } 
     } 
     cout<<"adjacent count of rect["<<(b+1)<<"] is = "<<adj_count<<endl; 


     return 0; 
    }

問題

現在對於矩形＃1它shows-

rect[1] is adjacent with rect[2] 
rect[1] is adjacent with rect[4] 
rect[1] is adjacent with rect[14] 
adjacent count of rect[1] is = 3

它射門矩形＃8和9 & 10 !! （請在新畫面）

而對於矩形＃2之shows-

rect[2] is adjacent with rect[1] 
rect[2] is adjacent with rect[3] 
rect[2] is adjacent with rect[11] 
adjacent count of rect[2] is = 3

它忽略了矩形＃5和7 & 6！（請檢查新圖片）

我該如何解決？

來源

2013-06-26 aries0152

您將有更好的反應，如果你發佈的代碼和更具體的問題。像這樣的問題通常會被降低和/或被忽略。 –

@JakeSellers我在算法標籤下非常活躍，這個問題在標籤的世界中似乎相當好。但是，當然，你的建議總的來說很好。 –

呃......你正在比較** rect **本身** .... if（rect [b] .x1 == rect [b] .x2 || rect [b] .x2 == rect [ b] .x1）{'，它總是'[b]'索引... – keelar

一個天真的解決方案需要O（N^2）其中N是矩形的數量，這裏是如何更快地做到這一點。

只有當兩個矩形有一個共同的座標（注意反向不正確）時，兩個矩形才相鄰。因此，您可以通過首先使用兩個散列分割輸入矩形，其中一個基於矩形的x位置，另一個基於y位置，從而更快地計算相鄰框的數量。結果，一個矩形將根據x1，y1，x2和y2放入四個不同的散列桶中。

例

例如，RECT (0.0000,0.0000) (0.3412,0.4175)將散列到bucketX(0.000)，bucketX(0.3412)，bucketY(0.0000)，和bucketY(0.4175)。

從OP中的輸入中，bucketX（0.000）和bucketX（1。000）將具有以下矩形：

bucketX(0.0000): 
    (0.0000,0.0000) (0.3412,0.4175) 
    (0.0000,0.4175) (0.3412,0.6553) 
    (0.0000,0.6553) (0.7445,1.0000) 
    (0.0000,0.4175) (0.3412,0.6553) 

bucketX(1.0000): 
    (0.7445,0.0000) (1.0000,0.6553) 
    (0.7445,0.6553) (1.0000,1.0000)

時間複雜度

散列步驟僅需要O（N）計算時間，其中N是矩形的數目，並且將所得檢查需要O（m^2），其中m是最大桶的尺寸，其在大多數情況下遠小於N.

檢查鄰接每個散列桶

內。然後，對於相同的散列桶中的所有的矩形。通過確定它們是否具有相同的x值和y中的重疊值來檢查兩個矩形是否相鄰，反之亦然。

以下是檢查兩個矩形是否爲相鄰的一個示例：

class Rect { 
public: 
    double x1, x2, y1, y2; // assuming x1 <= x2 and y1 <= y2 

    ... 

    bool isAdjacent(Rect rect) { 
    if (x1 == rect.x1 || x1 == rect.x2 || 
     x2 == rect.x1 || x2 == rect.x2) { 
     // use only < when comparing y1 and rect.y2 avoids sharing only a corner 
     if (y1 >= rect.y1 && y1 < rect.y2) { 
     return true; 
     } 
     if (y2 > rect.y1 && y2 <= rect.y2) { 
     return true; 
     } 
     if (rect.y1 >= y1 && rect.y1 < y2) { 
     return true; 
     } 
     if (rect.y2 > y1 && rect.y2 <= y2) { 
     return true; 
     } 
    } 
    if (y1 == rect.y1 || y1 == rect.y2 || 
     y2 == rect.y1 || y2 == rect.y2) { 
     if (x1 >= rect.x1 && x1 < rect.x2) { 
     return true; 
     } 
     if (x2 > rect.x1 && x2 <= rect.x2) { 
     return true; 
     } 
     if (rect.x1 >= x1 && rect.x1 < x2) { 
     return true; 
     } 
     if (rect.x2 > x1 && rect.x2 <= x2) { 
     return true; 
     } 
    } 
    return false; 
    } 
}

可運行的實施例

這裏鄰接支票提供樣本代碼：

#include <stdio.h> 
#include <stdlib.h> 
#include <vector> 

class Rect { 
public: 
    double x1, x2, y1, y2; // assuming x1 <= x2 and y1 <= y2 

    Rect(double X1, double Y1, double X2, double Y2) { 
    if (X1 < X2) { 
     x1 = X1; x2 = X2; 
    } else { 
     x2 = X1; x1 = X2; 
    } 
    if (Y1 < Y2) { 
     y1 = Y1; y2 = Y2; 
    } else { 
     y2 = Y1; y1 = Y2; 
    } 
    } 

    double area() { 
    return (x2 - x1) * (y2 - y1); 
    } 

    bool isAdjacent(Rect rect) { 
    if (x1 == rect.x1 || x1 == rect.x2 || 
     x2 == rect.x1 || x2 == rect.x2) { 
     // use only < when comparing y1 and rect.y2 avoids sharing only a corner 
     if (y1 >= rect.y1 && y1 < rect.y2) { 
     return true; 
     } 
     if (y2 > rect.y1 && y2 <= rect.y2) { 
     return true; 
     } 
     if (rect.y1 >= y1 && rect.y1 < y2) { 
     return true; 
     } 
     if (rect.y2 > y1 && rect.y2 <= y2) { 
     return true; 
     } 
    } 
    if (y1 == rect.y1 || y1 == rect.y2 || 
     y2 == rect.y1 || y2 == rect.y2) { 
     if (x1 >= rect.x1 && x1 < rect.x2) { 
     return true; 
     } 
     if (x2 > rect.x1 && x2 <= rect.x2) { 
     return true; 
     } 
     if (rect.x1 >= x1 && rect.x1 < x2) { 
     return true; 
     } 
     if (rect.x2 > x1 && rect.x2 <= x2) { 
     return true; 
     } 
    } 
    return false; 
    } 
}; 

int main() { 

    std::vector<Rect> rects; 

    rects.push_back(Rect(9999, 9999, 9999, 9999)); 
    rects.push_back(Rect(0.0000,0.0000, 0.8147,0.1355)); 
    rects.push_back(Rect(0.8147,0.0000, 1.0000,0.1355)); 
    rects.push_back(Rect(0.8147,0.1355, 0.9058,0.8350)); 
    rects.push_back(Rect(0.0000,0.1355, 0.1270,0.9689)); 
    rects.push_back(Rect(0.9058,0.1355, 0.9134,0.2210)); 

    rects.push_back(Rect(0.9058,0.8350, 1.0000,1.0000)); 
    rects.push_back(Rect(0.8147,0.8350, 0.9058,1.0000)); 
    rects.push_back(Rect(0.1270,0.1355, 0.6324,0.3082)); 
    rects.push_back(Rect(0.1270,0.9689, 0.8147,1.0000)); 
    rects.push_back(Rect(0.0000,0.9689, 0.1270,1.0000)); 

    rects.push_back(Rect(0.9134,0.1355, 1.0000,0.2210)); 
    rects.push_back(Rect(0.9134,0.2210, 1.0000,0.8350)); 
    rects.push_back(Rect(0.9058,0.2210, 0.9134,0.8350)); 
    rects.push_back(Rect(0.6324,0.1355, 0.8147,0.3082)); 
    rects.push_back(Rect(0.6324,0.3082, 0.8147,0.9689)); 

    rects.push_back(Rect(0.1270,0.3082, 0.6324,0.9689)); 


    int adj_count = 0; 
    int y = 1; 
    for (int x = 0; x < rects.size(); ++x) { 
    if (x == y) continue; 
    if (rects[y].isAdjacent(rects[x])) { 
     printf("rect[%d] is adjacent with rect[%d]\n", y, x); 
    } 
    } 
    y = 2; 
    for (int x = 0; x < rects.size(); ++x) { 
    if (x == y) continue; 
    if (rects[y].isAdjacent(rects[x])) { 
     printf("rect[%d] is adjacent with rect[%d]\n", y, x); 
    } 
    } 
}

，輸出爲：

rect[1] is adjacent with rect[2] 
rect[1] is adjacent with rect[4] 
rect[1] is adjacent with rect[8] 
rect[1] is adjacent with rect[14] 
rect[2] is adjacent with rect[1] 
rect[2] is adjacent with rect[3] 
rect[2] is adjacent with rect[5] 
rect[2] is adjacent with rect[11]

來源

2013-06-26 18:52:42 keelar

謝謝你的迴應。我正在使用數組來存儲座標。所以我試圖用你的* if..else *節來計算矩形。但它**只返回'0'**。。:(我已經編輯我的問題，並添加我的代碼片段我在做什麼錯 – aries0152

@ aries0152：？你確保X1 <= x2和Y1 <= Y2 – keelar

是，（X1，Y1）是座標的財產？（x2，y2）是右上角的座標，所以x1 aries0152

在你描述箱份額角落的情況，所以如果你計算的所有箱子的角落，那麼你能看到哪些是觸摸

// O(n) 
foreach box b { 
    // compute b's other 2 corners and save them 
} 

// 16 * O(n^2) = O(n^2) 
foreach box b { 
    foreach box other { 
     // match if any of b's corners match any of others points 
    } 
}

有可能是一個更高效/優雅的解決方案，這個有點幼稚。

來源

2013-06-26 18:52:55

但是，如果兩個矩形共享邊而不共享任何角落，這將是錯誤的？ –

@ZiyaoWei嗯，我明白你的意思了。像上面的6＆2一樣？ –

@ZiyaoWei等6的底部和2的底部仍然共享。 –

比方說，你有興趣櫃B表示（X0，Y0，X1，Y1）座標是：（B.x0，B.y0，B.x1，B.y1）

然後用：

ax0 = min(x0,x1); 
ax1 = max(x0,x1); 
ay0 = min(y0,y1); 
ay1 = max(y0,y1); 
bx0 = min(B.x0,B.x1); 
bx1 = max(B.x0,B.x1); 
by0 = min(B.y0,B.y1); 
by1 = max(B.y0,B.y1);

你經歷的箱子全部列表（for循環）和您選擇的人，其中：

(((ay0 <= by1 && ay1 >= by0) && (ax1 == bx0 || ax0 == bx1) || // touch on x axis 
((ax0 <= bx1 && ax1 >= bx0) && (ay1 == by0 || ay0 == by1)) // touch on y axis

來源

2013-06-26 18:54:21

這是不正確的，它們可能只是共享相同的x值或y值，但由於其他座標而不相鄰。 – keelar

是的，我會編輯我的答案。 –

計算相鄰框的數量

回答

相關問題