Having a line and a grid, the aim is to discretise the line into grid lines. In the following figure, the given line is in black, its intersections with grid lines are blue, the desired is set of segments (polyline) in red.

Any idea or solution?

enter image description here

Note that we know Bresenham's method. However, it does not work for our case as shown in the figures. Green cells are indeed pixels not squares based on Bresenham's method. It is not easy to generate our desired polyline (red) based on those Bresenham's green pixels. Note that the figure shown is a simplistic case.

enter image description here Important Update:
We are interested in general solution which works for any grid complexity. enter image description here

  • By curiosity, what do you need that for? – julien Sep 8 '13 at 16:07
  • 1
    You are asking for Bresenham's algorithm. This is the standard method to rasterize a line segment. – whuber Sep 8 '13 at 16:45
  • 1
    @julien Curiosity is good and we like that. One application in our mind is to approximate a move that can be done only horizontally or vertically. – Developer Sep 8 '13 at 23:49
  • @whuber We should have mentioned that we were aware of Bresenham's algorithm. But it generates pixel map not lines. As you see in the figure, which line to be chosen from four sides if a pixel is shown as rectangle is not easy. If it is trivial, would you please be more kind putting some code snippet that generates polyline above instead of pixels? – Developer Sep 9 '13 at 0:16
  • A "pixel map" in this case is perfectly equivalent to a set of line segments. To see this equivalence, draw a grid of points where your coordinate lines intersect and then draw pixels centered at those coordinates. The pink segments you have drawn correspond to a subset of these pixels; conversely, any connected subset of pixels can be interpreted as a representation of a polyline. – whuber Sep 9 '13 at 14:32

Bresenham's algorithm is just exactly what you are looking for, but you have to adapt it a little bit.

Using this algorithm is the most efficient and easy way to solve the problem.

Look at this example from Wikipedia:

enter image description here

The blue points are almost what you want, we just have to add a new point when the y value changes.

So, when the y value is "jumping", check the value of f(x - 0.5) in order to see if the new point have to be added below or above.

You can use the line equation:

Line equation

I ended up with something like this while "simplified" the equation to avoid float arithmetic operations (Python):

def bresenham(A, B):
    x0, y0 = P(0, 0)
    x1, y1 = P(B.x - A.x, B.y - A.y)

    octant = get_octant(A, B)

    x1, y1 = switch_octant_to_zero(octant, x1, y1)

    line = []

    e = x1 - x0

    dx = 2 * e
    dy = (y1 - y0) * 2

    x, y = x0, y0

    while x < x1:
        line.append(P(x, y))
        x += 1
        e -= dy

        if e < 0:
            if 2*y1*x > 2*x1*y + x1 + y1:
                line.append(P(x - 1, y + 1))
                line.append(P(x, y))

            y += 1
            e += dx

    line = [switch_octant_from_zero(octant, x, y) for x, y in line]
    return [P(x + A.x, y + A.y) for x, y in line]

The segment from P(1, 1) to P(9, 6) is discretised like this:


| improve this answer | |

The most obvious solution seems to be to chop the line into segments, where it crosses the grid lines. Calculate the bearing of each line. If it's 0-45 degrees then take the nearest vertical grid section and add that to your final line. If it's 45-90 degrees then take the nearest horizontal grid section. Obviously ignore duplicates. Then simply connect the chosen sections together by adding missing connections.

It works for your simplistic example. Not sure how well it works for more complex examples but just throwing it out in case it's of use.

NB: I had to have a crack at this. So, in the event that you have FME, I created a workspace that does this. You can get it from https://dl.dropboxusercontent.com/u/4200566/Community/StackExchangeDiscretizeQuestion.fmw - by posting this I guess I should point out that I do work for Safe Software (makers of FME) and that other solutions are available! And that this one may (or may not) need additional work to exactly fit your data.

The result looks like this:

enter image description here

| improve this answer | |
  • I believe this is equivalent to Bresenham's algorithm (but takes considerably more computation :-)). One has to wonder how it would perform on a line segment that is coincident with one of the row lines or column lines: those are the tricky cases. – whuber Sep 16 '13 at 16:58

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.