#+end_export
I find the easiest way to find these points is to use /linear interpolation/. Let's see how that works.
** Interpolating numbers
:PROPERTIES:
:CUSTOM_ID: interpolation-numbers
:END:
Here's a simple (Javascript) helper function I'll use:
#+begin_src js :tangle yes :exports code
function lerp(start, end, t) {
return start + t * (end-start);
}
#+end_src
@@html:__L__inear int__erp__olation@@ (“lerp”) gives you a number between two other numbers. When =t= = 0.0 you get the start point; when =t= = 1.0 you get the end point. *Try setting t*, the third parameter to lerp():
#+begin_export html

```
lerp( 0, 1, ) =
lerp( 0, 100, ) =
lerp( 3, 5, ) =
lerp( 5, 3, ) =
```

#+end_export
#+begin_src js :tangle yes :exports none
var t0 = make_scrubbable('t0', 0.3, [0.0, 1.0], 0.01);
t0.trigger(function() {
function set(id, fmt, lo, hi) { d3.select(id).text(d3.format(fmt)(lerp(lo, hi, t0.value))); }
set("#lerp1", ".2f", 0, 1);
set("#lerp2", ".0f", 0, 100);
set("#lerp3", ".1f", 3, 5);
set("#lerp4", ".1f", 5, 3);
});
#+end_src
** Interpolating points
:PROPERTIES:
:CUSTOM_ID: interpolation-points
:END:
We can extend the idea of interpolation to work on points, by interpolating both the x and y coordinates. *Try varying t* = @@html:@@:
#+begin_export html
#+end_export
Here's the code to find point x,y between point p_{0} = (x_{0},y_{0}) and point p_{1} = (x_{1},y_{1}):
#+begin_src js :tangle yes
function lerp_point(p0, p1, t) {
return new Point(lerp(p0.x, p1.x, t),
lerp(p0.y, p1.y, t));
}
#+end_src
Let's divide the line into @@html:@@ equal line segments:
#+begin_export html

#+end_export
Here's the code to find those points:
#+begin_src js :tangle yes :exports none
function Point(x, y) { this.x = x; this.y = y; }
#+end_src
#+begin_src js :tangle yes :exports none
// This will make it easier to use with d3+svg
Point.prototype.toString = function() { return this.x + "," + this.y; };
#+end_src
#+begin_src js
var points = [];
for (var step = 0; step <= N; step++) {
var t = step / N;
points.push(lerp_point(p0, p1, t));
}
#+end_src
** Snap to grid
:PROPERTIES:
:CUSTOM_ID: snap-to-grid
:END:
Next we need to figure out which /grid squares/ those points are in. We can round x and y to the nearest integer to find the grid tile:
#+begin_export html

#+end_export
We also need to decide how many points to include. Too few and the line has holes. Too many and the line has overdraw. How many do we need? The right number is the /diagonal distance/ between the endpoints, which in this case is @@html:@@.
*Adjust N* = @@html:@@ to @@html:@@ to see how the line fills in. @@html:@@
That's it!
1. Set N to the diagonal distance between the start and end point.
2. Pick N+1 interpolation points, evenly spaced.
3. Round those points to the nearest grid tile.
Here's the final code:
#+begin_src js :tangle yes
function diagonal_distance(p0, p1) {
var dx = p1.x - p0.x, dy = p1.y - p0.y;
return Math.max(Math.abs(dx), Math.abs(dy));
}
function round_point(p) {
return new Point(Math.round(p.x), Math.round(p.y));
}
function line(p0, p1) {
var points = [];
var N = diagonal_distance(p0, p1);
for (var step = 0; step <= N; step++) {
var t = N == 0? 0.0 : step / N;
points.push(round_point(lerp_point(p0, p1, t)));
}
return points;
}
#+end_src
This is the simplest line drawing algorithm I know of.
#+begin_src js :tangle yes :exports none
// You should use the line() function presented in the article.
// However, for the interactive illustrations I want to show the
// unrounded points, and I also want the reader to choose N, so this
// is a variant of the line() function.
function line_N_unrounded(p0, p1, N) {
var points = [];
for (var step = 0; step <= N; step++) {
var t = N == 0? 0.0 : step / N; // special case: N=0 when p0==p1
points.push(lerp_point(p0, p1, t));
}
return points;
}
#+end_src
#+begin_src js :tangle yes :exports none
// Make a line-drawing diagram
//
// #$id will get a new

#+end_export
#+begin_src js :tangle yes :exports none
var diagram_grid_movement = new Diagram('diagram-grid-movement')
.add_track()
.add_line_draw()
.add_endpoints();
diagram_grid_movement.find_line = function() {
this.points = walk_grid(this.endpoints[0], this.endpoints[1]);
};
diagram_grid_movement.redraw();
#+end_src
The strategy here is to think about the /grid edges/ being crossed, both vertical and horizontal. At every step we either cross a vertical edge (horizontal step) or cross a horizontal edge (vertical step).
#+begin_src js :tangle yes
function walk_grid(p0, p1) {
var dx = p1.x-p0.x, dy = p1.y-p0.y;
var nx = Math.abs(dx), ny = Math.abs(dy);
var sign_x = dx > 0? 1 : -1, sign_y = dy > 0? 1 : -1;
var p = new Point(p0.x, p0.y);
var points = [new Point(p.x, p.y)];
for (var ix = 0, iy = 0; ix < nx || iy < ny;) {
if ((0.5+ix) / nx < (0.5+iy) / ny) {
// next step is horizontal
p.x += sign_x;
ix++;
} else {
// next step is vertical
p.y += sign_y;
iy++;
}
points.push(new Point(p.x, p.y));
}
return points;
}
#+end_src
It's more work to make it symmetric. Also, sometimes you'll want more control over whether you pick a horizontal step or a vertical step, especially if the choice is close, and there's a wall in one direction but not the other.
** Supercover lines
:PROPERTIES:
:CUSTOM_ID: supercover
:END:
"Supercover" lines catch all the grid squares that a line passes through. I believe (but am not sure) that it is somewhere in between regular line drawing and grid movement line drawing. Unlike grid movement line drawing, we can take a diagonal step /only/ if the line passes exactly through the corner.
This looks just like the grid movement line drawing, except when the line goes through a grid corner.
#+begin_export html

#+end_export
#+begin_src js :tangle yes :exports none
var diagram_supercover = new Diagram('diagram-supercover')
.add_track()
.add_line_draw()
.add_endpoints();
diagram_supercover.find_line = function() {
this.points = supercover_line(this.endpoints[0], this.endpoints[1]);
};
diagram_supercover.redraw();
#+end_src
Let's modify the grid movement line drawing code for this:
#+begin_src js :tangle yes
function supercover_line(p0, p1) {
var dx = p1.x-p0.x, dy = p1.y-p0.y;
var nx = Math.abs(dx), ny = Math.abs(dy);
var sign_x = dx > 0? 1 : -1, sign_y = dy > 0? 1 : -1;
var p = new Point(p0.x, p0.y);
var points = [new Point(p.x, p.y)];
for (var ix = 0, iy = 0; ix < nx || iy < ny;) {
if ((0.5+ix) / nx == (0.5+iy) / ny) {
// next step is diagonal
p.x += sign_x;
p.y += sign_y;
ix++;
iy++;
} else if ((0.5+ix) / nx < (0.5+iy) / ny) {
// next step is horizontal
p.x += sign_x;
ix++;
} else {
// next step is vertical
p.y += sign_y;
iy++;
}
points.push(new Point(p.x, p.y));
}
return points;
}
#+end_src
Implementation note: it's usually a bad idea to compare two floating point numbers for equality, as I do here. However, since =ix=, =nx=, =iy=, =ny= are all integers, we can ensure this works properly by cross-multiplying and rewriting the test with integer arithmetic.
#+begin_src js
if ((1+2*ix) * ny == (1+2*iy) * nx) { ... }
#+end_src
It still feels somewhat fragile to me, and I'm guessing there are better algorithms out there.
** Line of sight
If you allow diagonal steps, some algorithms will step through walls:
#+begin_export html
#+end_export
In this case, you can either take the diagonal step if /either/ the horizontal or vertical step is clear, or you can disallow the diagonal step unless /both/ the horizontal and vertical steps are clear.
* More reading
:PROPERTIES:
:CUSTOM_ID: more
:END:
There's lots written about line drawing but I haven't researched it extensively. When drawing graphical lines, I use the graphics library. It's only on grids that I needed to find some other algorithms.
- If you're interpolating 3d rotations, look at the [[http://en.wikipedia.org/wiki/Slerp][slerp]] variant.
- If you want non-linear interpolation, take look at [[http://en.wikipedia.org/wiki/Smoothstep][smoothstep]] and [[http://inloop.github.io/interpolator/][others]], especially for animation.
- Roguebasin has [[http://www.roguebasin.com/index.php?title%3DComparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds][an article]] about various qualities you might want on a grid if calculating field of view or line of sight.
- [[http://www.cse.yorku.ca/~amana/research/grid.pdf][This paper]] gives an extension of the step-by-step line drawing algorithm for 3D coordinates.
- [[http://en.wikipedia.org/wiki/Xiaolin_Wu%2527s_line_algorithm][Wu's algorithm]] for anti-aliasing might be useful for determining how much of an object is on one grid cell or another; I haven't tried this.
- [[https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams-algorithm/][This article]] looks at DDA line drawing with fixed point arithmetic. It's from 2009 though and CPUs have changed since then. Also look at [[http://www.edepot.com/algorithm.html][Extremely Fast Line Algorithm]].
- I find Bresenham's algorithm to be much longer than I'd like, but if you'd like to compare, take a look at [[http://www.phatcode.net/res/224/files/html/ch35/35-03.html][Michael Abrash's implementation]] and [[http://www.phatcode.net/res/224/files/html/ch35/35-01.html][explanation]].
#+begin_export html