line.md

   1 # Line
   2
   3 Line is one of the most basic geometric shapes, it is straight, continuous, [infinitely](infinity.md) long and infinitely thin. A finite continuous part of a line is called **line segment**, though in practice we sometimes call line segments also just *lines*. In flat, non-curved geometries shortest path between any two points always lies on a line.
   4
   5 Line is a one [dimensional](dimension.md) shape, i.e. any of its points can be directly identified by a single number -- the signed distance from a certain point on the line. But of course a line itself may exist in more than one dimensional spaces (just as a two dimensional sheet of paper can exist in our three dimensional space etc.).
   6
   7 { In my favorite book [Flatland](flatland.md) line segments, being the most primitive shape, represent [women](woman.md). ~drummyfish }
   8
   9 ```
  10    /               |     \            .'
  11   /   ________     |      \         .'
  12  /                 |       \      .'
  13 /                  |        \   .'
  14 ```
  15
  16 *some lines, in case you haven't seen one yet*
  17
  18 ## Representing Lines With Equations
  19
  20 Mathematically lines can be defined by [equations](equation.md) with space coordinates (see [analytic geometry](analytic_geometry.md)) -- this is pretty important for example for [programming](programming.md) as many times we need to compute intersections with lines; for example [ray casting](ray_casting.md) is a method of 3D rendering that "shoots lines from camera" and looks at which objects the lines intersect. Line equations can have different "formats", the two most important are:
  21
  22 - **point-slope**: This equation only works in 2D space (in 3D this kind of equation will not describe a line but rather a [plane](plane.md)) and only for lines that aren't completely vertical (lines close to vertical may also pose problems in computers with limited precision numbers). The advantage is that we have a single, pretty simple equation. The equation is of form *y = k * x + q* where *x* and *y* are space coordinates, *k* is the [slope](slope.md) of the line and *q* is an offset. See examples below for more details.
  23 - **parametric**: This is a system of *N* equations, where *N* is the number of dimensions of the space the line is in. This way can describe any line in any dimensional space -- obviously the advantage here is that we can can use this form in any situation. The equations are of form *Xn = Pn + t * Dn* where *Xn* is *n*th coordinate (*x*, *y*, *z*, ...), *Pn* is *n*th coordinate of some point *P* that lies on the line, *Dn* is *n*th coordinate of the line's direction [vector](vector.md) and *t* is a variable parameter (plugging in different numbers for *t* will yield different points that lie on the line). DON'T PANIC if you don't understand this, see the examples below :)
  24
  25 As an equation for line segment we simply limit the equation for an infinite line, for example with the parametric equations we limit the possible values of *t* by an interval that corresponds to the two boundary points.
  26
  27 **Example**: let's try to find equations of a line in 2D that goes through points *A = [1,2]* and *B = [4,3]*.
  28
  29 Point-slope equation is of form *y = k * x + q*. We want to find numbers *k* (slope) and *q* (offset). Slope says the line's direction (as dy/dx, just as in [derivative](derivative.md) of a function) and can be computed from points *A* and *B* as *k = (By - Ay) / (Bx - Ax) = (3 - 2) / (4 - 1) = 1/3* (notice that this won't work for a vertical line as we'd be dividing by zero). Number *q* is an "offset" (different values will give a line with same direction but shifted differently), we can simply compute it by plugging in known values into the equation and working out *q*. We already know *k* and for *x* and *y* we can substitute coordinates of one of the points that lie on the line, for example *A*, i.e. *q = y - k * x = Ay - k * Ax = 2 - 1/3 * 1 = 5/3*. Now we can write the final equation of the line:
  30
  31 *y = 1/3 * x + 5/3*
  32
  33 This equation lets us compute any point on the line, for example if we plug in *x = 3*, we get *y = 1/3 * 3 + 5/3 = 8/3*, i.e. point *[3,8/3]* that lies on the line. We can verify that plugging in *x = 1* and *x = 4* gives us *[1,2]* (*A*) and *[4,3]* (*B*).
  34
  35 Now let's derive the parametric equations of the line. It will be of form:
  36
  37 *x = Px + t * Dx*
  38
  39 *y = Py + t * Dy*
  40
  41 Here *P* is a point that lies on the line, i.e. we may again use e.g. the point *A*, so *Px = Ax = 1* and *Py = Ay = 2*. *D* is the direction [vector](vector.md) of the line, we can compute it as *B - A*, i.e. *Dx = Bx - Ax = 3* and *Dy = By - Ay = 1*. So the final parametric equations are:
  42
  43 *x = 1 + t * 3*
  44
  45 *y = 2 + t * 1*
  46
  47 Now for whatever *t* we plug into these equations we get the *[x,y]* coordinates of a point that lies on the line; for example for *t = 0* we get *x = 1 + 0 * 3 = 1* and *y = 2 + 0 * 1 = 2*, i.e. the point *A* itself. As an exercise you may try substituting other values of *t*, plotting the points and verifying they lie on a line.
  48
  49 ## Formulas
  50
  51 Here let be formulas for computing various things related to lines and line segments.
  52
  53 First let's take a look at lines in 2D. Consider two dimensional plane. Let *L* be a line (or line segment) going from point *L1 = [L1x,L1y]* to point *L2 = [L2x,L2y]*. Let *dx = L2x - L1x* and *dy = L2y - L1y*. Let *K* be another line (or line segment). Let *P = [Px,Py]* be a point.
  54
  55 - **line segment [length](length.md)**: Use [Pythagorean theorem](pythagorean_theorem.md): *length(L) = sqrt(dx^2 + dy^2)*. The same goes for a line in 3D.
  56 - **determine which side of line L point P lies on**: A simple way is to use the simple formula for [triangle](triangle.md) winding, i.e. determine if triangle *[L1,L2,P]* goes clockwise or counterclockwise. This can also determine if the point lies exactly on the line (i.e. lies on neither side).
  57 - **shortest distance of point P from line L**: TODO
  58 - **intersection of lines (or line segments) L and K**: Represent the lines with their equations (see above), preferably parametric (allows any angle), put both points equal and solve the system of equations (watch out for the cases with no or many solutions). For line segments you also additionally have to check whether the intersection you find lies within BOTH line segments (with parametric representations this is easily done by checking if both parameters you get as a solution lie in the range 0 to 1).
  59 - **angle between lines L and K**: OK firstly notice there are always two angles between two infinite lines, you find one by getting direction vectors of both lines (which you already have with parametric line equations; otherwise just find two points on the line and the vector between them is the direction vector), [normalizing](normalization.md) them and computing their [dot product](dot_product.md) -- this gives you the [cosine](cos.md) of the angle, which if you plug into [acos](acos.md) function you get the actual angle. This angle will only ever be between 0 and 180 degrees; the other angle is simply 180 minus the one you computed. You can also compute the angle by computing the angle of each line with the *x* axis from theirs slopes (angle = atan(dy / dx), but watch out for division by zero).
  60 - **distance of lines P and L**: This only makes sense if the lines are parallel, otherwise they intersect and have distance 0. TODO: continue
  61 - **project point P orthogonally to line L**: TODO
  62 - TODO: more
  63
  64 TODO: 3D lines
  65
  66 ## Line Drawing Algorithms
  67
  68 Drawing lines with computers is a subject of [computer graphics](graphics.md). On specific devices such as [vector monitors](vector_monitor.md) this may be a trivial task, however as most display devices nowadays work with [raster graphics](raster_graphics.md) ([pixel](pixel.md)s!), let's from now on focus only on such devices. It is worth spending some time on [optimizing](optimization.md) your line drawing function as it constitutes a very basic operation -- consider that you will for example be using it for [wireframe](wireframe.md) rendering of a large 3D scene which will require drawing tens of thousands lines each frame -- having a fast line drawing function here can significantly improve your [FPS](fps.md).
  69
  70 There are many [algorithms](algorithm.md) for line [rasterization](rasterization.md). They differ in attributes such as:
  71
  72 - complexity of implementation
  73 - speed/efficiency (some algorithms avoid the use of [floating point](float.md) which requires special [hardware](hardware.md))
  74 - support of [antialiasing](antialiasing.md) ("smooth" vs "pixelated" lines)
  75 - [subpixel](subpixel.md) precision (whether start and end point of the line has to lie exactly on integer pixel coordinates; subpixel precision makes for smoother animation)
  76 - support for different width lines (and additionally e.g. the shape of line segment ends etc.)
  77 - ...
  78
  79 ```
  80                                                  .
  81              XXX               XX             .aXa
  82            XX                XX             lXa.
  83          XX                XX            .lXl
  84       XXX               XXX            .aal
  85     XX                XX             lXa.
  86   XX               XXX            .aXl
  87 XX               XX               a.
  88
  89       pixel         subpixel     subpixel accuracy
  90      accuracy       accuracy      + antialiasing
  91 ```
  92
  93 One of the most basic line rasterization algorithms is the [DDA](dda.md) (Digital differential analyzer), however it is usually better to use at least the [Bresenham's line algorithm](bresenham.md) which is still simple and considerably improves on DDA by not requiring multiplication or division (slow operations) and by only using integers (no [floating point](float.md)).
  94
  95 If you just super quickly need to draw something resembling lines for debugging purposes or anything, you may just draw a few points between the two endpoints (idea: make a recursive function that takes point *A* and *B*, average them to get a middle point *M*, draws all three points and then recursively call itself on *A* and *M* and then on *M* and *B*, until the points are close enough -- with integers only the line will probably be warped as we get accumulating rounding errors in the middle point). You may just do something super dirty like [interpolate](interpolation.md) 1000 points between the endpoints with using floating point and draw them all. Just don't use this in anything serious I guess :)
  96
  97 Let's now take a more serious closer look at line drawing and how the above mentioned algorithms work: consider we want to draw a line between pixels *A = [ax,ay]* and *B = [bx,by]*. Let's also define *dx = bx - ax* and *dy = by - ay*.
  98
  99 The [naive](naive.md) approach that comes to newcomer's mind is usually this: iterate *x* from *ax* to *bx* and at each step draw the pixel *[x, ay + dy * (x - ax) / dx]*. This has many problems: obviously we are using many slow operations here such as multiplication and division, but most importantly we will in many cases end up with holes in the line we draw. Consider e.g. a line from *[0,0]* to *[2,10]* -- we will only draw 3 pixels (for *x = 0, 1 and 2*), but the whole line is actually 10 pixels high in vertical direction, so we at the very least need those 10 pixels. What's more, consider *dx = 0*, our algorithm will crash on division by zero. This just falls apart very quickly.
 100
 101 The most common way to deal with this shit is to always convert the line to some simple subcase (by somehow juggling, swapping and flipping the coordinates), usually a line going from left to right under a degree between -45 and 45 degrees (i.e. *abs(dx) >= abs(dy)*). With such a line we now may do what we couldn't before, i.e. just iterate *x* by 1 and at each step compute the corresponding *y*. Once we have these coordinates we somehow convert them back to the space of the original line and draw them.
 102
 103 Furthermore algorithms improve this on the basis of observation that really while stepping along the *x* line we don't have to compute *y* from scratch, we are just deciding whether *y* stays the same as in previous step or whether it moves by 1 pixel, so drawing a line now boils down to making one yes/no decision at each step. It turns out this decision can be made using only simple integer operations.
 104
 105 Bresenham's algorithm is based on the following idea: our line has a certain slope *s = dy / dx*; this slope for the common case (described above) will be between -1 and 1. At each step we move 1 pixel horizontally (*x*) and *s* (some fractional part) pixels vertically. We keep accumulating this vertical shift (often called an *error*) and once it jumps over 1, we jump in the vertical (*y*) direction and so on. E.g. if our line is 10 pixels wide (*dx*) and 3 pixels tall (*dy*), our slope is *s = 3/10*; now we start drawing pixels and our error is *3/10*, then *6/10*, the *9/10* and then *12/10*, jumping over 1, which tells us we have to shift vertically (after this we subtract 1 from the current error so we will continue with *2/10*). Now to get rid of fractions (floats) we may simply multiply everything by *dx*; in our case by 10, so we keep adding error *3/10 * 10 = 3* and instead of comparing the error to 1, we compare it to *1 * 10 = 10*.
 106
 107 All in all, here is a comfy line drawing function based on the above described principle, i.e. needing no floating point,  multiplication or division:
 108
 109 ```
 110 void drawLine(int ax, int ay, int bx, int by)
 111 {
 112   int *x = &ax, *y = &ay,
 113     stepX = -1 + 2 * (ax <= bx),
 114     stepY = -1 + 2 * (ay <= by);
 115
 116   int dx = stepX == 1 ? (bx - ax) : (ax - bx);
 117   int dy = stepY == 1 ? (by - ay) : (ay - by);
 118
 119   if (dy > dx)
 120   { // swap everything
 121     y = &ax; x = &ay;
 122     stepX ^= stepY; stepY ^= stepX; stepX ^= stepY;
 123     dx ^= dy; dy ^= dx; dx ^= dy;
 124   }
 125
 126   int steps = dx + 1;
 127   bx = dx / 2; // use bx as error accumulator
 128
 129   while (steps)
 130   {
 131     drawPixel(ax,ay);
 132
 133     steps--;
 134     *x += stepX;
 135     bx += dy;
 136
 137     if (bx >= dx)
 138     {
 139       bx -= dx;
 140       *y += stepY;
 141     }
 142   }
 143 }
 144 ```
 145
 146 To add [antialiasing](antialiasing.md) here you wouldn't just draw one pixel at each step but two, right next to each other, between which you'd distribute the intensity in the ratio given by current error.
 147
 148 ## See Also
 149
 150 - [curve](curve.md)
 151 - [vector](vector.md)
 152 - [plane](plane.md)