1

I am asking here because I feel that this question can be filed under the "algorithm and data structure concepts" category.

Background: I have been recently assigned the task to design and develop a new program. Specs are still in the discussion phase and I can have my say, given my experience I will go for either for C++ or C, also depending on hardware and legal (certification) requirements.

One of the main problems that I have to solve in this program is to check collisions between a (2D or 3D) line and a (2D or 3D again) grid. I am looking for suggestions about which kind of data structures would be optimal (runtime wise) to perform such checks and/or if there is an overview of possible algorithms with a comparison of the various costs and benefits connected to them?

EDIT To address Useless' comment, the grid is a regular square one (x % 0.5 == 0, same for y) and the segments are straight between two known points (x_0, y_0) and (x_1,y_1). In the 3D case I should add the z coordinate, but these properties would remain unchanged. The result of the algorthm would be the list of grid squares crossed by the line.

Since the time I asked this question, I found out about Bresenham's algorithm. The output would be the one I look for, but is it optimal or are there better approaches?

  • A regular orthogonal grid like x % 5 == 0, y % 5 == 0, or an arbitrary grid you have to store somewhere? A straight line segment, or a complete (infinite) straight line, or a curved line or segment? – Useless Oct 6 '15 at 16:25
  • @Useless thanks for the comment, question updated. – Federico Oct 6 '15 at 16:42
2

The standard algorithm is 2D-DDA and 3D-DDA. This returns every intersected cell in a 2D or 3D grid. Bresenham's algorithm is more for line rendering.

Rough pseudo-code for a ray (for a line just stop at the end by setting minBoundary and maxBoundary to be the bounding box of the line. This will stop it from both leaving the grid and going past the end):

var rayPosition = { x: 25, y: 25 };
var rayDirection = { x: 1, y: 1 };

var cellSize = 50;

var cell = { x: Math.floor(rayPosition.x / cellSize), y: Math.floor(rayPosition.y / cellSize) };

var step = { x: Math.sign(rayDirection.x), y: Math.sign(rayDirection.y) }; // sign returns -1, 0, or 1

var offsetFromAxis =
{
    x: step.x > 0 ? cellSize - (rayPosition.x - Math.floor(rayPosition.x / cellSize) * cellSize) : (rayPosition.x - Math.floor(rayPosition.x / cellSize) * cellSize),
    y: step.y > 0 ? cellSize - (rayPosition.y - Math.floor(rayPosition.y / cellSize) * cellSize) : (rayPosition.y - Math.floor(rayPosition.y / cellSize) * cellSize)
};
var tMax = { x: offsetFromAxis.x / Math.abs(rayDirection.x), y: offsetFromAxis.y / Math.abs(rayDirection.y) };
var tDelta = { x: cellSize / Math.abs(rayDirection.x), y: cellSize / Math.abs(rayDirection.y) };
var minBoundary = { x: -1, y: -1 }; // for a line just do something like (might be off by one):
/* var minBoundary =
{
    x: Math.max(0, Math.min(Math.floor(lineStart.x / cellSize), Math.floor(lineEnd.x / cellSize)) - 1,
    y: Math.max(0, Math.min(Math.floor(lineStart.y / cellSize), Math.floor(lineEnd.y / cellSize)) - 1
}
*/
var maxBoundary = { x: width + 1, y: height + 1 }; // for a line just do something like (might be off by one):
/* var maxBoundary =
{
    x: Math.min(width, Math.max(Math.floor(lineStart.x / cellSize), Math.floor(lineEnd.x / cellSize)) + 1,
    y: Math.min(height, Math.max(Math.floor(lineStart.y / cellSize), Math.floor(lineEnd.y / cellSize)) + 1
}
*/
var boundary = { x: step.x > 0 ? maxBoundary.x : minBoundary.x, y: step.y > 0 ? maxBoundary.y : minBoundary.y };
var cells = [];
do
{
    cells.push({ x: cell.x, y: cell.y });
    if (tMax.x < tMax.y)
    {
        cell.x += step.x;
        if (cell.x == boundary.x)
        {
            break;
        }
        tMax.x += tDelta.x;
    }
    else
    {
        cell.y += step.y;
        if (cell.y == boundary.y)
        {
            break;
        }
        tMax.y += tDelta.y;
    }
} while (true);

The 3D-DDA is nearly identical adding a z-axis. (You can find examples though online). The only big change is the if statement:

if (tMax.x < tMax.y)
{
    if (tMax.x < tMax.z)
    {
        // x
    }
    else
    {
        // z
    }
}
else
{
    if (tMax.y < tMax.z)
    {
        // y
    }
    else
    {
        // z
    }
}

Regarding data structures you can just use a 1D array and index it with something like:

index = z * xDimension * yDimension + y * xDimension + x;

Not sure what your exact application is though, but that should suffice.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.