算法來尋找重疊

基本上我有型船的一些結構這是要去上板，可以具有可變寬度和高度。有關船隻的信息從文件中讀入，我只需要知道確保船隻沒有重疊的最佳方式。算法來尋找重疊

這裏是船舶的結構：

int x // x position of first part of ship 
int y // y position of first part of ship 
char dir // direction of the ship, either 'N','S','E' or 'W' 
int length // length of the ship

而且，這將是處理方向的好辦法。比使用switch語句更清晰並且對每個方向使用不同的條件。

任何幫助將不勝感激！

來源

2010-03-20 Gary

您只需要2個方向（例如南部和東部），以防方向本身無關緊要。 – 2010-03-20 07:01:38

從文件中讀入方向，所以它可能不一定包含船舶的頂部或最左側部分 – Gary 2010-03-20 07:06:01

這看起來像一艘戰列艦遊戲，是嗎？ – erelender 2010-03-20 07:27:34

你可以保持整個電網的布爾數組，最初初始化爲「假」。對於每艘船舶，對於船舶覆蓋的每個位置，檢查該位置是否爲「假」。如果是，將其設置爲「true」。如果沒有，那麼其他一些船就在該地點。

該算法在所有船舶的總面積上是線性的，但也需要與板上的位置數量成比例的額外空間。

來源

2010-03-20 06:59:34

除非你有很多船就用一個簡單的蠻力算法，這將是兩個嵌套的循環，即O（N^2）。

來源

2010-03-20 06:54:55

你是對的 - 但我忘了添加我的問題的其他位，這是處理差異方向（現在編輯）的最佳方式。對此有何想法？感謝您的時間:) – Gary 2010-03-20 06:59:25

保持板的位圖，其中每一位指示是否有一艘船佔據那瓦。對於每個船隻標記它在電路板上佔用的瓷磚，並檢查是否將相同的位標記兩次。

來源

2010-03-20 06:59:02 r0u1i

（戰艦？）

使含有該船舶的ID時存在一個2D陣列（「板」）。因此，當您添加船舶時，您可以檢查O（長度）時間空間是否被佔用。

爲O（n *長度）時間，O（N^2）的空間。

來源

2010-03-20 06:59:45 kennytm

這是同樣的事情作爲測試矩形是否相交，我覺得你的代碼是，如果你不認爲這些船隻作爲一個點，長度和方向，但作爲一個矩形的簡單。

所以它轉換

int x // x position of first part of ship 
int y // y position of first part of ship 
char dir // direction of the ship, either 'N','S','E' or 'W' 
int length // length of the ship

這個（允許負CX & CY得到N，S，E，W）

int x // x position of first part of ship 
int y // y position of first part of ship 
int cx // length of the ship in X 
int cy // length of the ship in Y

或本

int left // x position of Eastern part of the ship 
int top // y position of Northernmost part of ship 
int right // x position of Westernmost part of the ship 
int bottom // y position of Southernmost part of ship 
bool orientation; // so we can tell East from West or North from South.

然後，簡單的功能可以確定兩艘船是否相交。

bool DoShipsIntersect(Ship * a, Ship * b) 
{ 
    if ((a->right < b->left) || (b->right < a->left)) 
     return false; 
    if ((a->bottom < b->top) || (b->bottom < a->top)) 
     return false; 
    return true; 
}

只要你沒有成千上萬的船隻，每艘船與其他船隻的蠻力比較應該是相當快的。

來源

2010-03-20 07:17:34

好的答案:)現在我弄清楚是否值得通過並重寫大量的代碼來做到這一點.. – Gary 2010-03-20 07:41:45

@加里：你可以一次做一點。編寫一個函數將您的Ship轉換爲ShipRect，反之亦然，您的原始結構是存儲船舶的好方法，而不是最有效的方法來比較它們。 – 2010-03-20 09:28:15

表示方向的一種方式是作爲單位向量。這可以是2個整數：dirX和dirY。例如。東部的dirX = 1;或南方的dirY = 1。基於這些值

int cx = x; 
int cy = y; 
for(int i = 0; i < length; i++) { 
    cx += dirX; 
    cy += dirY; 
}

還是得到了邊界框：

然後，您可以遍歷由船與佔領的所有位置

x 
y 
x + dirX * (length - 1) 
y + dirY * (length - 1)

來源

2010-03-20 14:36:57 fgb

你可能想使用一個枚舉類型爲你的方向。在查找重疊方面，創建一個布爾值的二維數組，初始化爲您的董事會爲false。然後，對於每艘船舶，在數組中找到相應的條目，並且如果它們已經爲真，則會有重疊。否則，將這些條目設置爲true。如果你已經放置了所有的船隻，並且沒有遇到一個真實的入口，那麼就沒有重疊。

來源

2010-03-21 23:33:05

算法來尋找重疊

回答

相關問題