Editing Line drawing algorithm (section)

== Related Problems ==
Lines may not only be drawn 8-connected, but also 4-connected, meaning that only horizontal and vertical steps are allowed, while diagonal steps are prohibited. Given a raster of square pixels, this leads to every square containing a part of the line being colored. A generalization of 4-connected line drawing methods to three dimensions is used when dealing with [[voxel]] grids, for example in optimized [[Ray tracing (graphics)|ray tracing]], where it can determine the voxels that a given ray crosses.

Line drawing algorithms distribute diagonal steps approximately evenly. Thus, line drawing algorithms may also be used to evenly distribute points with integer coordinates in a given interval.<ref>Chengfu Yao, Jon G. Rokne: ''An integral linear interpolation approach to the design of incremental line algorithms.'' Journal of Computational and Applied Mathematics 102, 1 (February 1999): 3–19, {{ISSN|0377-0427}}</ref> 
Possible applications of this method include [[linear interpolation]] or [[downsampling]] in [[signal processing]]. There are also parallels to the [[Euclidean algorithm]], as well as [[Farey sequence|Farey sequences]] and a number of related mathematical constructs.<ref>Mitchell A. Harris, Edward M. Reingold: ''Line drawing, leap years, and Euclid.'' ACM Computing Surveys 36, 1 (March 2004): 68–80, {{ISSN|0360-0300}} ({{webarchive|url=http://emr.cs.iit.edu/~reingold/bresenham.pdf |date = 16 December 2006|wayback=20061216194847 |text=PDF, 270 kB }})</ref>