算法来寻找重叠

基本上我有型船的一些结构这是要去上板，可以具有可变宽度和高度。有关船只的信息从文件中读入，我只需要知道确保船只没有重叠的最佳方式。算法来寻找重叠

这里是船舶的结构：

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

算法来寻找重叠

回答

相关问题