Line is one of the most basic geometric shapes, it is straight, continuous, infinitely 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.
Line is a one dimensional 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.).
{ In my favorite book Flatland line segments, being the most primitive shape, represent women. ~drummyfish }
/ | \ .'
/ ________ | \ .'
/ | \ .'
/ | \ .'
some lines, in case you haven't seen one yet
Mathematically lines can be defined by equations with space coordinates (see analytic geometry) -- this is pretty important for example for programming as many times we need to compute intersections with lines; for example ray casting 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:
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.
Example: let's try to find equations of a line in 2D that goes through points A = [1,2] and B = [4,3].
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 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:
y = 1/3 * x + 5/3
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).
Now let's derive the parametric equations of the line. It will be of form:
x = Px + t * Dx
y = Py + t * Dy
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 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:
x = 1 + t * 3
y = 2 + t * 1
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.
Here let be formulas for computing various things related to lines and line segments.
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.
TODO: 3D lines
Drawing lines with computers is a subject of computer graphics. On specific devices such as vector monitors this may be a trivial task, however as most display devices nowadays work with raster graphics (pixels!), let's from now on focus only on such devices. It is worth spending some time on optimizing your line drawing function as it constitutes a very basic operation -- consider that you will for example be using it for wireframe 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.
There are many algorithms for line rasterization. They differ in attributes such as:
.
XXX XX .aXa
XX XX lXa.
XX XX .lXl
XXX XXX .aal
XX XX lXa.
XX XXX .aXl
XX XX a.
pixel subpixel subpixel accuracy
accuracy accuracy + antialiasing
One of the most basic line rasterization algorithms is the DDA (Digital differential analyzer), however it is usually better to use at least the Bresenham's line algorithm 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).
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 1000 points between the endpoints with using floating point and draw them all. Just don't use this in anything serious I guess :)
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.
The naive 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.
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.
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.
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.
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:
void drawLine(int ax, int ay, int bx, int by)
{
int *x = &ax, *y = &ay,
stepX = -1 + 2 * (ax <= bx),
stepY = -1 + 2 * (ay <= by);
int dx = stepX == 1 ? (bx - ax) : (ax - bx);
int dy = stepY == 1 ? (by - ay) : (ay - by);
if (dy > dx)
{ // swap everything
y = &ax; x = &ay;
stepX ^= stepY; stepY ^= stepX; stepX ^= stepY;
dx ^= dy; dy ^= dx; dx ^= dy;
}
int steps = dx + 1;
bx = dx / 2; // use bx as error accumulator
while (steps)
{
drawPixel(ax,ay);
steps--;
*x += stepX;
bx += dy;
if (bx >= dx)
{
bx -= dx;
*y += stepY;
}
}
}
To add antialiasing 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.
Powered by nothing. All content available under CC0 1.0 (public domain). Send comments and corrections to drummyfish at disroot dot org.