![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jackIntroduction
Suppose you want to draw a straight line using a grid of pixels. I say "suppose"; of course, almost all of my friends and acquaintances do so daily[1]. I'm now going to describe a classic method to get it straight in my mind. (Most techie friends likely know this already, and those who've done any graphics programming a lot more, but this is a necessary precursor to the sequel on hex grids.)
Part I
Suppose we divide the plane into 1x1 sqaures:
One of the oldest tricks is referred to as Bresenham's. Don't worry about calculating it yet, just imagine each 1x1 box on the plane and wonder which ones you'd like to fill in. Lay a ruler at an angle from the centre of box (0,0) to the centre of box X and sketch that line. For now we'll assume the line is drawn further right than it is down, and assume we fill in one box in each column.
Which boxes should those be? Well, now it seems obvious. Look at the centre of the column. Where does our diagonal line cross the centre? Whichever box that's in, fill in that one. (AKA, if there were a pixel in the centre of each box, light up the one in each column that's vertically closest to the diagonal line.)
Aside
There's even a neat side effect. Pedantic people are probably asking themselves "Which box? What if it's on the edge between two boxes? Well, that was implicit in our original assumption. Imagine:
Alternatively, colour in both. That probably makes the line look wonky, though.
Part II
How do we calculate this? Well, fortunately (AKA, why this algorithm is well known), it's really easy. Let DX be the centre-to-centre distance horizontally, and DY the centre-to-centre distance vertically. Then the slope of the line is to move vertically DY/DX for each 1 we move horizontally.
Move across horizontally in steps of 1 box. Keep a running tally of how far vertically our diagonal line should have moved by the middle of that column -- since we know the desired slope, this is just incremented by DY/DX each time. When this offset is below the bottom of the first row, the next box should be coloured in the second row, etc.
But we're incrementing by DY/DX each time, and comparing to 1. We're dealing with integers, so it's a lot easier to instead increment by DY each time, and compare to DX. We don't care how many times, we can just measure when we've overshot. We assume we're moving further X than Y, so we know which coord to increment. And we're starting from the centre, so we want to start our offset from DX/2 rather than 0. (If DX was odd, multiply both DY and DX by 2.)
Aside
That's not the sum of my knowledge of drawing lines, but I'm no expert. There's lots more that could be said. And please correct any typos above.
This is probably most relevant for drawing things. AFAIK lines-of-sight, eg. in rougelike/nethack games or with roleplaying miniatures, which squares are visible from which, are a bit different. But I'm using this algorithm for that anyway, because it's simple and widely available.
Footnotes
[1] I'm referring to using a computer, which even if you don't implement the algorithm yourself, if you're using any program, draws lots and lots of lines on the screen. However, that's probably not actually true; most programs and operating systems deal with rectangles and bitmaps most of the time. But in principle, you're likely to want to represent a line by lighting up some pixels but not others.
References
cf. http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
Suppose you want to draw a straight line using a grid of pixels. I say "suppose"; of course, almost all of my friends and acquaintances do so daily[1]. I'm now going to describe a classic method to get it straight in my mind. (Most techie friends likely know this already, and those who've done any graphics programming a lot more, but this is a necessary precursor to the sequel on hex grids.)
Part I
Suppose we divide the plane into 1x1 sqaures:
0 1 2 3 4 5 6 1 # # # # # # 2 # # # # # XEach number, dot, and X represent a 1x1 box, and we want to fill in some of the boxes to draw a line from (0,0) to X at (6,2). Eg. we might fill in 01 on the first row, 234 on the second row, and 56 on the last row. How can we calculate that deterministically?
One of the oldest tricks is referred to as Bresenham's. Don't worry about calculating it yet, just imagine each 1x1 box on the plane and wonder which ones you'd like to fill in. Lay a ruler at an angle from the centre of box (0,0) to the centre of box X and sketch that line. For now we'll assume the line is drawn further right than it is down, and assume we fill in one box in each column.
Which boxes should those be? Well, now it seems obvious. Look at the centre of the column. Where does our diagonal line cross the centre? Whichever box that's in, fill in that one. (AKA, if there were a pixel in the centre of each box, light up the one in each column that's vertically closest to the diagonal line.)
Aside
There's even a neat side effect. Pedantic people are probably asking themselves "Which box? What if it's on the edge between two boxes? Well, that was implicit in our original assumption. Imagine:
A # # # # BAnd draw a line from the centre of A to the centre of B. It passes right through the middle of the edge between the middle two boxes. We can stick to our "one in each column" rule, and colour the top one. Or the bottom one. (This will be represented in our algorithm by choosing between >= and >) It will just look a lot neater if we always choose the SAME one if we have to choose multiple times.
Alternatively, colour in both. That probably makes the line look wonky, though.
Part II
How do we calculate this? Well, fortunately (AKA, why this algorithm is well known), it's really easy. Let DX be the centre-to-centre distance horizontally, and DY the centre-to-centre distance vertically. Then the slope of the line is to move vertically DY/DX for each 1 we move horizontally.
Move across horizontally in steps of 1 box. Keep a running tally of how far vertically our diagonal line should have moved by the middle of that column -- since we know the desired slope, this is just incremented by DY/DX each time. When this offset is below the bottom of the first row, the next box should be coloured in the second row, etc.
But we're incrementing by DY/DX each time, and comparing to 1. We're dealing with integers, so it's a lot easier to instead increment by DY each time, and compare to DX. We don't care how many times, we can just measure when we've overshot. We assume we're moving further X than Y, so we know which coord to increment. And we're starting from the centre, so we want to start our offset from DX/2 rather than 0. (If DX was odd, multiply both DY and DX by 2.)
while (...) {
x += 1; // Increment by one, next pixel draw one to the right of previous pixel
offset += DY; // Increment current position of diagonal
if (offset>DX) offset-=DX, // Reduce it so it always stays between 0 and DX (NB: DY<DX)
y += 1; // Next pixel also on next row (diag of previous pixel)
draw(x,y)
}
There's a number of small but fiddly details in making the algorithm work in any direction, and seeing when you are done. You can look them up on wikipedia if you need to implement it.Aside
That's not the sum of my knowledge of drawing lines, but I'm no expert. There's lots more that could be said. And please correct any typos above.
This is probably most relevant for drawing things. AFAIK lines-of-sight, eg. in rougelike/nethack games or with roleplaying miniatures, which squares are visible from which, are a bit different. But I'm using this algorithm for that anyway, because it's simple and widely available.
Footnotes
[1] I'm referring to using a computer, which even if you don't implement the algorithm yourself, if you're using any program, draws lots and lots of lines on the screen. However, that's probably not actually true; most programs and operating systems deal with rectangles and bitmaps most of the time. But in principle, you're likely to want to represent a line by lighting up some pixels but not others.
References
cf. http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
no subject
Date: 2008-09-22 12:53 pm (UTC)I don't think simon's hypothesised equivalence holds, either, assuming the #s are assumed to extend all the way into the corners of their squares.
You're right, I think it works in the case we were thinking about (directly along an edge in a hex grid), but I overgeneralised. I think the same might be relevant for corners in a square grid, though I'm not positive.
In fact, even on a hex grid, the straight line for a 4x1 step passes through both "O" squares. But I think it's right for my purposes to treat it as the 1x1 step and require either of the squares to be free. It looks like you ought to be able to see :) But I don't know what rigorous condition, if any, it corresponds to :)