algorithm to find overlaps

Question

Hey,

Basically I've got some structs of type Ship which are going to go on a board which can have a variable width and height. The information about the ships is read in from a file, and I just need to know the best way to make sure that none of the ships overlap.

Here is the structure of Ship:

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

Also, what would be a good way to handle the directions. Something cleaner than using a switch statement and using a different condition for each direction.

Any help would be greatly appreciated!

Answer 1

Unless you have a lot of ships then just use a simple brute force algorithm, which will be two nested loops, i.e. O(n^2).

Answer 2

Keep a bitmap of the board where each bit indicates whether there's a ship occupying that tile. For each ship mark the tiles it occupies on the board, and check out if you mark the same bit twice.

Answer 3

You could keep a boolean array of the entire grid, initially initialized to "false." For each ship, for each location the ship covers, check if the location is "false." If it is, set it to "true". If not, then some other ship is on the location.

This algorithm is linear in the total area of all the ships, but also requires extra space proportional to the number of locations on the board.

Answer 4

(Battleship?)

Make a 2D array ("board") which contains the ID of the ship when one is present. Therefore, when you add the ship you can check in O(length) time whether a space is occupied or not.

O(n * length) time, O(N^2) space.

Answer 5

This is the same thing as a test whether rectangles intersect, I think your code would be simpler if you don't think of these ships as a point,length, and direction but as a rectangle.

So convert this

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

to this (allow negative cx & cy to get 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

or this

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.

Then a simple function can determine if two ships intersect.

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;
}

A brute force compare of every ship to every other ship should be quite fast as long as you don't have thousands of ships.

Answer 6

One way of representing a direction is as a unit vector. This can be 2 integers: dirX and dirY. Eg. dirX=1 for East; or dirY=1 for South.

You can then iterate over all positions occupied by a ship with:

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

Or get a bounding-box based on these values:

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

Answer 7

You might want to use an enum type for your direction. In terms of finding overlaps, create a two dimensional array of booleans initialized to false for your board. Then, for each ship, finding the corresponding entries in the array and, if they are already true, you have an overlap. Otherwise, set those entries to true. If you have placed all your ships and didn't encounter an already true entry, then there is no overlap.