CODEWITHSUNDEEP
c++linetrace
sgtHale
sgtHale

Reputation: 1567

Finding grid squares from a line

I'm trying to find a decent algorithm that allows me to find all the squares that a line intersects as it passes through a grid. Bresenham's algorithm does not work in my scenario because the endpoints of a line do not necessarily have to start or end in the center of a square. Even if it passes through a corner, a square will be counted.

Ive tried googling and I have not found many results.

enter image description here

Red is Bresenham's algorithm that does what I want it to do but it only works if the line endpoints start in the center of a square. Green is my ideal scenario.

Upvotes: 1

Views: 735

Answers (2)

Truls Henriksson
Truls Henriksson

Reputation: 101

Had the same problem, found a useful answer on a question in gamedev.stackexchange.com, which linked to a blog post: http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html

Below is the relevant code if you're in a rush, but do check out the gamedev question for more relevant answers. The blog post also explains in more detail how it works, and has two additional algorithms - one more general, easier to adapt to three dimensions, and one simpler, for the case where the line always starts and ends in the center of a square.

#include <limits> // for infinity
void raytrace(double x0, double y0, double x1, double y1)
{
    double dx = fabs(x1 - x0);
    double dy = fabs(y1 - y0);

    int x = int(floor(x0));
    int y = int(floor(y0));

    int n = 1;
    int x_inc, y_inc;
    double error;

    if (dx == 0)
    {
        x_inc = 0;
        error = std::numeric_limits<double>::infinity();
    }
    else if (x1 > x0)
    {
        x_inc = 1;
        n += int(floor(x1)) - x;
        error = (floor(x0) + 1 - x0) * dy;
    }
    else
    {
        x_inc = -1;
        n += x - int(floor(x1));
        error = (x0 - floor(x0)) * dy;
    }

    if (dy == 0)
    {
        y_inc = 0;
        error -= std::numeric_limits<double>::infinity();
    }
    else if (y1 > y0)
    {
        y_inc = 1;
        n += int(floor(y1)) - y;
        error -= (floor(y0) + 1 - y0) * dx;
    }
    else
    {
        y_inc = -1;
        n += y - int(floor(y1));
        error -= (y0 - floor(y0)) * dx;
    }

    for (; n > 0; --n)
    {
        visit(x, y);

        if (error > 0)
        {
            y += y_inc;
            error -= dx;
        }
        else
        {
            x += x_inc;
            error += dy;
        }
    }
}

Upvotes: 0

manasij7479
manasij7479

Reputation: 1715

Why not follow a 'numerical' sort of algorithm?
Just evaluate a finitely large number of points in the line.
From the coordinates of the point, it'd be easy to determine which square(s) they fall on.
(You only have to add a new square to your list when the square the point lies in is different from the last point.)

Upvotes: 1

Related Questions