When you think of algebra, you probably think of problems that require “solving for x.” For instance, you probably spent quite a bit of time in algebra class learning to solve equations like 3x2 + 2x + 4 = 0; that is, figuring out what value or values of x make the equation true.
Linear algebra, being a branch of algebra, has the same kinds of computational questions. The difference is that what you want to solve for may be a vector or matrix rather than a number. If you take a traditional linear algebra course, you might cover a lot of algorithms to solve these kinds of problems. But because you have Python at your disposal, you only need to know how to recognize the problem you’re facing and choose the right library to find the answer for you.
I’m going to cover the most important class of linear algebra problems you’ll see in the wild: systems of linear equations. These problems boil down to finding points where lines, planes, or their higher dimensional analogies intersect. One example is the infamous high school math problem involving two trains leaving Boston and New York at different times and speeds. But because I don’t assume railroad operation interests you, I’ll use a more entertaining example.
In this chapter, we build a simple remake of the classic Asteroids arcade game (figure 7.1). In this game, the player controls a triangle representing a spaceship and fires a laser at polygons floating around it, which represent asteroids. The player must destroy the asteroids to prevent them from hitting and destroying the spaceship.
One of the key mechanics in this game is deciding whether the laser hits an asteroid. This requires us to figure out whether the line defining the laser beam intersects with the line segments outlining the asteroids. If these lines intersect, the asteroid is destroyed. We’ll set up the game first, and then we’ll see how to solve the underlying linear algebra problem.
After we implement our game, I’ll show you how this 2D example generalizes to 3D or any number of dimensions. The latter half of this chapter covers a bit more theory, but it will round out your linear algebra education. We’ll have covered many of the major concepts you’d find in a college-level linear algebra class, albeit in less depth. After completing this chapter, you should be well prepared to crack open a denser textbook on linear algebra and fill in the details. But for now, let’s focus on building our game.
In this chapter, I focus on a simplified version of the asteroid game where the ship and asteroids are static. In the source code, you’ll see that I already made the asteroids move, and we’ll cover how to make them move according to the laws of physics in part
2 of this book. To get started, we model the entities of the game−the spaceship, the laser, and the asteroids−and show how to render them onscreen.
In this section, we display the spaceship and the asteroids as polygons in the game. As before, we model these as collections of vectors. For instance, we can represent an eight-sided asteroid by eight vectors (indicated by arrows in figure 7.2), and we can connect them to draw its outline.
The asteroid or spaceship translates or rotates as it travels through space, but its shape remains the same. Therefore, we store the vectors representing this shape separately from the x − and y-coordinates of its center, which can change over time. We also store an angle, indicating the rotation of the object at the current moment. The PolygonModel
class represents a game entity (the ship or an asteroid) that keeps its shape but can translate or rotate. It’s initialized with a set of vector points that define the outline of the asteroid, and by default, its center x − and y-coordinates and its angle of rotation are set to zero:
class PolygonModel(): def __init__(self,points): self.points = points self.rotation_angle = 0 self.x = 0 self.y = 0
When the spaceship or asteroid moves, we need to apply the translation by self .x,self.y
and the rotation by self.rotation_angle
to find out its actual location. As an exercise, you can give PolygonModel
a method to compute the actual, transformed vectors outlining it.
The spaceship and asteroids are specific cases of PolygonModel
that initialize automatically with their respective shapes. For instance, the ship has a fixed triangular shape, given by three points:
class Ship(PolygonModel): def __init__(self): super().__init__([(0.5,0), (−0.25,0.25), (−0.25,-0.25)])
For the asteroid, we initialize it with somewhere between 5 and 9 vectors at equally spaced angles and random lengths between 0.5 and 1.0. This randomness gives the asteroids some character:
class Asteroid(PolygonModel): def __init__(self): sides = randint(5,9) ❶ vs = [vectors.to_cartesian((uniform(0.5,1.0), 2*pi*i/sides)) for i in range(0,sides)] ❷ super().__init__(vs)
❶ An asteroid has a random number of sides between 5 and 9.
❷ Lengths are randomly selected between 0.5 and 1.0, and the angles are multiples of 2π/n, where n is the number of sides.
With these objects defined, we can turn our attention to instantiating them and rendering them onscreen.
For the initial state of the game, we need a ship and several asteroids. The ship can begin at the center of the screen, but the asteroids should be randomly spread out over the screen. We can show an area of the plane ranging from −10 to 10 in the x and y directions like this:
ship = Ship() asteroid_count = 10 asteroids = [Asteroid() for _ in range(0,asteroid_count)] ❶ for ast in asteroids: ❷ ast.x = randint(−9,9) ast.y = randint(−9,9)
❶ Creates a list of a specified number of Asteroid objects, in this case, 10
❷ Sets the position of each object to a random point with coordinates between −10 and 10 so it shows up onscreen
I use a 400×400 pixel screen, which requires transforming the x − and y-coordinates before rendering them. Using PyGame’s built-in 2D graphics instead of OpenGL, the top left pixel on the screen has the coordinate (0, 0) and the bottom right has the coordinate (400, 400). These coordinates are not only bigger, they’re also translated and upside down, so we need to write a to_pixels
function (illustrated in figure 7.3) that does the transformation from our coordinate system to PyGame’s pixels.
With the to_pixels
function implemented, we can write a function to draw a polygon defined by points to the PyGame screen. First, we take the transformed points (translated and rotated) that define the polygon and convert them to pixels. Then we draw them with a PyGame function:
GREEN = (0, 255, 0)
def draw_poly(screen, polygon_model, color=GREEN):
pixel_points = [to_pixels(x,y) for x,y in polygon_model.transformed()]
pygame.draw.aalines(screen, color, True, pixel_points, 10) ❶
❶ Draws lines connecting given points to a specified PyGame object. The True parameter connects the first and last points to create a closed polygon.
You can see the whole game loop in the source code, but it basically calls draw_poly
for the ship and each asteroid every time a frame is rendered. The result is our simple triangular spaceship surrounded by an asteroid field in a PyGame window (figure 7.4).
Now it’s time for the most important part: giving our ship a way to defend itself! The player should be able to aim the ship using the left and right arrow keys and then shoot a laser by pressing the spacebar. The laser beam should come out of the tip of the spaceship and extend to the edge of the screen.
In the 2D world we’ve invented, the laser beam should be a line segment starting at the transformed tip of the spaceship and extending in whatever direction the ship is pointed. We can make sure it reaches the end of the screen by making it sufficiently long. Because the laser’s line segment is associated with the state of the Ship
object, we can make a method on the Ship
class to compute it:
class Ship(PolygonModel): ... def laser_segment(self): dist = 20. * sqrt(2) ❶ x,y = self.transformed()[0] ❷ return ((x,y), (x + dist * cos(self.rotation_angle), y + dist*sin(self.rotation_angle))) ❸
❶ Uses the Pythagorean theorem to find the longest segment that fits onscreen
❷ Gets the value of the first of the definition points (the tip of the ship)
❸ Uses trigonometry to find an endpoint for the laser if it extends dist units from the tip (x,y) at a self.rotation_angle (figure 7.5)
In the source code, you can see how to make PyGame respond to keystrokes and draw the laser as a line segment only if the spacebar is pressed. Finally, if the player fires the laser and hits an asteroid, we want to know something happened. In every iteration of the game loop, we want to check each asteroid to see if it is currently hit by the laser. We do this with a does_intersect(segment)
method on the PolygonModel
class, which computes whether the input segment intersects any segment of the given PolygonModel
. The final code includes some lines like the following:
laser = ship.laser_segment() ❶ keys = pygame.key.get_pressed() ❷ if keys[pygame.K_SPACE]: draw_segment(*laser) for asteroid in asteroids: if asteroid.does_intersect(laser): ❸ asteroids.remove(asteroid)
❶ Calculates the line segment representing the laser beam based on the ship’s current position and orientation
❷ Detects which keys are pressed. If the spacebar is pressed, renders the laser beam to the screen with a helper function draw_segment (similar to draw_poly).
❸ For every asteroid, checks whether the laser line segment intersects it. If so, destroys the given asteroid by removing it from the list of asteroids.
The work that remains is implementing the does_intersect(segment)
method. In the next section, we cover the math to do so.
class PolygonModel(): ... def transformed(self): rotated = [vectors.rotate2d(self.rotation_angle, v) for v in self.points] return [vectors.add((self.x,self.y),v) for v in rotated] |
width, height = 400, 400 def to_pixels(x,y): return (width/2 + width * x/ 20, height/2 − height * y / 20) |
The problem at hand is to decide whether the laser beam hits the asteroid. To do this, we’ll look at each line segment defining the asteroid and decide whether it intersects with the segment defining the laser beam. There are a few algorithms we could use, but we’ll solve this as a system of linear equations in two variables. Geometrically, this means looking at the lines defined by an edge of the asteroid and the laser beam and seeing where they intersect (figure 7.6).
Once we know the location of the intersection, we can see whether it lies within the bounds of both segments. If so, the segments collide and the asteroid is hit. We first review equations for lines in the plane, then cover how to find where pairs of lines intersect. Finally, we write the code for the does_intersect
method for our game.
In the previous chapter, we saw that 1D subspaces of the 2D plane are lines. These subspaces consist of all of the scalar multiples t · v for a single chosen vector v. Because one such scalar multiple is 0 · v, these lines always pass through the origin, so t · v is not quite a general formula for any line we encounter.
If we start with a line through the origin and translate it by another vector u, we can get any possible line. The points on this line have the form u + t · v for some scalar t. For instance, take v = (2, −1). Points of the form t · (2, −1) lie on a line through the
origin. But if we translate by a second vector, u = (2, 3), the points are now (2, 3) + t · (2, −1), which constitute a line that doesn’t pass through the origin (figure 7.7).
Any line can be described as the points u + t · v for some selection of vectors u and v and all possible scalar multiples t. This is probably not the general formula for a line you’re used to. Instead of writing y as a function of x, we’ve given both the x − and y-coordinates of points on the line as functions of another parameter t. Sometimes, you’ll see the line written r(t) = u + t · v to indicate that this line is a vector valued function r of the scalar parameter t. The input t decides how many units of v you go from the starting point u to get the output r(t).
The advantage of this kind of formula for a line is that it’s dead simple to find if you have two points on the line. If your points are u and w, then you can use u as the translation vector, and w − u as the vector that is scaled (figure 7.8).
The formula r(t) = u + t · v also has its downside. As you’ll see in the exercises, there are multiple ways to write the same line in this form. The extra parameter t also makes it harder to solve equations because there is one extra unknown variable. Let’s look at some alternative formulas with other advantages.
If you recall any formula for a line from high school, it is probably y = m · x + b. This formula is useful because it gives you a y-coordinate explicitly as a function of the x-coordinate. In this form, it’s easy to graph a line; you go through a bunch of x values, compute the corresponding y values, and put dots at the resulting (x, y) points. But this formula also has some limitations. Most importantly, you can’t represent a vertical line like r(t) = (3, 0) + t · (0, 1). This is the line consisting of vectors where x = 3.
We’ll continue to use the parametric formula r(t) = u + t · v because it avoids this problem, but it would be great to have a formula with no extra parameter t that can represent any line. The one we use is ax + by = c. As an example, the line we’re looking at in the last few images can be written as x + 2y = 8 (figure 7.9). It is the set of (x, y) points in the plane satisfying that equation.
The form ax + by = c has no extra parameters and can represent any line. Even a vertical line can be written in this form; for instance, x = 3 is the same as 1 · x + 0 · y = 3. Any equation representing a line is called a linear equation and this, in particular, is called the standard form for a linear equation. We prefer to use it in this chapter because it makes it easy to organize our computations.
The formula x + 2y = 8 is the equation for a line containing one of the segments on the example asteroid. Next, we’ll look at another one (figure 7.10) and then try to systematize finding the standard form for linear equations. Brace yourself for a bit of algebra! I’ll explain each of the steps carefully, but it may be a bit dry to read. You’ll have a better time if you follow along on your own with a pencil and paper.
The vector (1, 5) − (2, 3) is (−1, 2), which is parallel to the line. Because (2, 3) lies on the line, a parametric equation for the line is r(t) = (2, 3) + t · (−1, 2). Knowing that all points on the line have the form (2, 3) + t · (−1, 2) for some t, how can we rewrite this condition to be a standard form equation? We need to do some algebra and, particularly, get rid of t. Because (x, y) = (2, 3) + t · (−1, 2), we really have two equations to start with:
y = 3 + 2t
We can manipulate both of them to get two new equations that have the same value (2t):
y − 3 = 2t
Because both of the expressions on the left-hand sides equal 2t, they equal each other:
4 - 2x = y - 3
We’ve now gotten rid of t ! Finally, pulling the x and y terms to one side, we get the standard form equation:
2x + y = 7
This process isn’t too hard, but we need to be more precise about how to do it if we want to convert it to code. Let’s try to solve the general problem: given two points (x1, y1) and (x2, y2), what is the equation of the line that passes through them (see figure 7.11)?
Using the parametric formula, the points on the line have the following form:
(x, y) = (x1, y1) + t · (x2 - x1, y2 - y1)
There are a lot of x and y variables here, but remember that x1, x2, y1, and y2 are all constants for the purpose of this discussion. We assume we have two points with known coordinates, and we could have called them (a, b) and (c, d) just as easily. The variables are x and y(with no subscripts), which stand for coordinates of any point on the line. As before, we can break this equation into two pieces:
y = y1 + t · (y2 − y1)
We can move x1 and y1 to the left-hand side of their respective equations:
y − y1 = t · (y2 − y1)
Our next goal is to make the right-hand side of both equations look the same, so we can set the left-hand sides equal to each other. Multiplying both sides of the first equation by (y2 − y1) and both sides of the second equation by (x2 − x1) gives us
(y2 − y1) · (x − x1) = t · (x2 − x1) · (y2 − y1)
(x2 − x1) · (y − y1) = t · (x2 − x1) · (y2 − y1)
Because the right-hand sides are identical, we know that the first and second equations’ left-hand sides equal each other too. That lets us create a new equation with no t in it:
(y2 − y1) · (x − x1) = (x2 − x1) · (y − y1)
Remember, we want an equation of the form ax + by = c, so we need to get x and y on the same side and the constants on the other side. The first thing we can do is expand both sides:
(y2 − y1) · x − (y2 − y1) · x = (x2 − x1) · y − (x2 − x1) · y1
Then we can move the constants to the left and the variables to the right:
(y2 − y1) · x − (x2 − x1) · y = (y2 − y1) · x1 − (x2 − x1) · y1
Expanding the right side, we see some of the terms cancel out:
(y2 − y1) · x − (x2 − x1) · y = y2x1 − y1x1 − x2y1 + x1y1 = x1y2 − x2y1
We’ve done it! This is the linear equation in standard form ax + by = c, where a = (y2 − y1), b = −(x2 − x1), or in other words, (x1 − x2), and c = (x1 y2 − x2 y1). Let’s check this with the previous example we did, using the two points (x1, y1) = (2, 3) and (x2, y2) = (1, 5). In this case,
c = x1y2 − x2y1 = 2 · 5 − 3 · 1 = 7
As expected, this means the standard form equation is 2x + y = 7. This formula seems trustworthy! As one final application, let’s find the standard form equation for the line defined by the laser. It looks like it passes through (2, 2) and (4, 4) as I drew it before (figure 7.12).
In our asteroid game, we have exact start and end points for the laser line segment, but these numbers are nice for an example. Plugging into the formula, we find
b = −(x2 − x1) = −(4 − 2) = −2
c = x1y2 − x2y1 = 2 · 4 − 2 · 4 = 0
This means the line is 2y − 2x = 0, which is equivalent to saying x − y = 0 (or simply x = y). To decide whether the laser hits the asteroid, we’ll have to find where the line x − y = 0 intersects the line x + 2y = 8, the line 2x + y = 7, or any of the other lines bounding the asteroid.
Let’s focus on an intersection we can see: the laser clearly hits the closest edge of the asteroid, whose line has equation x + 2y = 8 (figure 7.13).
After quite a bit of build-up, we’ve met our first real system of linear equations. It’s customary to write systems of linear equations in a grid like the following, so that the variables x and y line up:
Thinking back to chapter 5, we can organize these two equations into a single matrix equation. One way to do this is to write a linear combination of column vectors, where x and y are coefficients:
Another way is to consolidate this even further and write it as a matrix multiplication. The linear combination of (1,−1) and (−1,−2) with coefficients x and y is the same as a matrix product:
When we write it this way, the task of solving the system of linear equations looks like solving for a vector in a matrix multiplication problem. If we call the 2-by−2 matrix a, the problem becomes what vector (x, y) is multiplied by the matrix a to yield (0, 8)? In other words, we know that an output of the linear transformation a is (0, 8) and we want to know what input yields it (figure 7.14).
These different notations show new ways to look at the same problem. Solving a system of linear equations is equivalent to finding a linear combination of some vectors that produces another given vector. It’s also equivalent to finding an input vector to a linear transformation that produces a given output. Thus, we're about to see how to solve all of these problems at once.
Finding the intersection of x − y = 0 and x + 2y = 8 is the same as finding the vector (x, y) that satisfies the matrix multiplication equation:
This is only a notational difference, but framing the problem in this form allows us to use pre-built tools to solve it. Specifically, Python’s NumPy library has a linear algebra module and a function that solves this kind of equation. Here’s an example:
>>> import numpy as np >>> matrix = np.array(((1,−1),(1,2))) ❶ >>> output = np.array((0,8)) ❷ >>> np.linalg.solve(matrix,output) ❸ array([2.66666667, 2.66666667]) ❹
❶ Packages the matrix as a NumPy array object
❷ Packages the output vector as a NumPy array (although it needn’t be reshaped to a column vector)
❸ The numpy.linalg.solve function takes a matrix and an output vector and finds the input vector that produces it.
❹ The result is (x, y) = (2.66..., 2.66...).
NumPy has told us that the x- and y-coordinates of the intersection are approximately 22/3or 8/3 each, which looks about right geometrically. Eyeballing the diagram, it looks like both coordinates of the intersection point should be between 2 and 3. We can check to see that this point lies on both lines by plugging it in to both equations:
1x − 1y = 1 ⋅ (2.66666667) − 1 ⋅ (2.66666667) = 0
1x + 2y = 1 ⋅ (2.66666667) + 2 ⋅ (2.66666667) = 8.00000001
These results are close enough to (0, 8) and, indeed, make an exact solution. This solution vector, roughly (8/3, 8/3) is also the vector that satisfies the matrix equation 7.1.
As figure 7.15 shows, we can picture (8/3, 8/3) as the vector we pass into the linear transformation machine defined by the matrix that gives us the desired output vector.
We can think of the Python function numpy.linalg.solve
as a differently shaped machine that takes in matrices and output vectors, and returns the “solution” vectors for the linear equation they represent (figure 7.16).
This is perhaps the most important computational task in linear algebra; starting with a matrix a, and a vector w, and finding the vector v such that a v = w. Such a vector gives the solution to a system of linear equations represented by a and w. We’re lucky to have a Python function that can do this for us so we don’t have to worry about the tedious algebra required to do it by hand. We can now use this function to find out when our laser hits asteroids.
The missing piece of our game was an implementation for the does_intersect
method on the PolygonModel
class. For any instance of this class, which represents a polygon-shaped object living in our 2D game world, this method should return True
if an input line segment intersects any line segment of the polygon.
For this, we need a few helper functions. First, we need to convert the given line segments from pairs of endpoint vectors to linear equations in standard form. At the end of the section, I give you an exercise to implement the function standard_form
, which takes two input vectors and returns a tuple (a, b, c) where ax + by = c is the line on which the segment lies.
Next, given two segments, each represented by its pair of endpoint vectors, we want to find out where their lines intersect. If u 1 and u 2 are endpoints of the first segment, and v 1 and v 2 are endpoints of the second, we need to first find the standard form equations and then pass them to NumPy to solve. For example,
def intersection(u1,u2,v1,v2): a1, b1, c1 = standard_form(u1,u2) a2, b2, c2 = standard_form(v1,v2) m = np.array(((a1,b1),(a2,b2))) c = np.array((c1,c2)) return np.linalg.solve(m,c)
The output is the point where the two lines on which the segments lie intersect. But this point might not lie on either of the segments as shown in figure 7.17.
To detect whether the two segments intersect, we need to check that the intersection point of their lines lies between the two pairs of endpoints. We can check that using distances. In figure 7.17, the intersection point is further from point v2 than point v1. Likewise, it’s further from u1 than u2. This indicates that the point is on neither segment. With four total distance checks, we can confirm whether the intersection point of the lines (x, y) is an intersection point of the segments as well:
def do_segments_intersect(s1,s2): u1,u2 = s1 v1,v2 = s2 d1, d2 = distance(*s1), distance(*s2) ❶ x,y = intersection(u1,u2,v1,v2) ❷ return (distance(u1, (x,y)) <= d1 and ❸ distance(u2, (x,y)) <= d1 and distance(v1, (x,y)) <= d2 and distance(v2, (x,y)) <= d2)
❶ Stores the lengths of the first and second segments as d1 and d2, respectively
❷ Finds the intersection point (x, y) of the lines on which the segments lie
❸ Does four checks to ensure the intersection point lies between the four endpoints of the line segments, confirming the segments intersect
Finally, we can write the does_intersect
method by checking whether do _segments_intersect
returns True
for the input segment and any of the edges of the (transformed) polygon:
class PolygonModel():
...
def does_intersect(self, other_segment):
for segment in self.segments():
if do_segments_intersect(other_segment,segment):
return True ❶
return False
❶ If any of the segments of the polygon intersect other_segment, the method returns True.
In the exercises that follow, you can confirm that this actually works by building an asteroid with known coordinate points and a laser beam with a known start and end point. With does_intersect
implemented as in the source code, you should be able to rotate the spaceship to aim at asteroids and destroy them.
Let me leave you with one final admonition: not every system of linear equations in 2D can be solved! It’s rare in an application like the asteroid game, but some pairs of linear equations in 2D don’t have unique solutions or even solutions at all. If we pass NumPy a system of linear equations with no solution, we get an exception, so we need to handle this case.
When a pair of lines in 2D are not parallel, they intersect somewhere. Even the two lines in figure 7.18 that are nearly parallel (but not quite) intersect somewhere off in the distance.
Where we run into trouble is when the lines are parallel, meaning the lines never intersect (or they’re the same line!) as shown in figure 7.19.
In the first case, there are zero intersection points, while in the second, there are infinitely many intersection points−every point on the line is an intersection point. Both of these cases are problematic computationally because our code demands a single, unique result. If we try to solve either of these systems with NumPy, for instance, the system consisting of 2x + y = 6 and 4x + 2y = 8, we get an exception:
>>> import numpy as np >>> m = np.array(((2,1),(4,2))) >>> v = np.array((6,4)) >>> np.linalg.solve(m,v) Traceback (most recent call last): File "<stdin>", line 1, in <module> ... numpy.linalg.linalg.LinAlgError: Singular matrix
NumPy points to the matrix as the source of the error. The matrix
is called a singular matrix, meaning there is no unique solution to the linear system. A system of linear equations is defined by a matrix and a vector, but the matrix on its own is enough to tell us whether the lines are parallel and whether the system has a unique solution. For any non-zero w we pick, there won’t be a unique v that solves the system.
We’ll philosophize more about singular matrices later, but for now you can see that the rows (2, 1) and (4, 2) and the columns (2, 4) and (1, 2) are both parallel and, therefore, linearly dependent. This is the key clue that tells us the lines are parallel and that the system does not have a unique solution. Solvability of linear systems is one of the central concepts in linear algebra; it closely relates to the notions of linear independence and dimension. We discuss that in the last two sections of this chapter.
For the purpose of our asteroid game, we can make the simplifying assumption that any parallel line segments don’t intersect. Given that we’re building the game with random floats, it’s highly unlikely that any two segments are exactly parallel. Even if the laser lined up exactly with the edge of an asteroid, this would be a glancing hit and the player doesn’t deserve to have the asteroid destroyed. We can modify do_segments_intersect
to catch the exception and return the default result of False
:
def do_segments_intersect(s1,s2): u1,u2 = s1 v1,v2 = s2 l1, l2 = distance(*s1), distance(*s2) try: x,y = intersection(u1,u2,v1,v2) return (distance(u1, (x,y)) <= l1 and distance(u2, (x,y)) <= l1 and distance(v1, (x,y)) <= l2 and distance(v2, (x,y)) <= l2) except np.linalg.linalg.LinAlgError: return False
def standard_form(v1, v2): x1, y1 = v1 x2, y2 = v2 a = y2 − y1 b = x1 − x2 c = x1 * y2 − y1 * x2 return a,b,c |
def segment_checks(s1,s2): u1,u2 = s1 v1,v2 = s2 l1, l2 = distance(*s1), distance(*s2) x,y = intersection(u1,u2,v1,v2) return [ distance(u1, (x,y)) <= l1, distance(u2, (x,y)) <= l1, distance(v1, (x,y)) <= l2, distance(v2, (x,y)) <= l2 ] >>> segment_checks(((−3,0),(−1,0)),((0,−1),(0,1)))
[False, True, True, True]
>>> segment_checks(((1,0),(3,0)),((0,−1),(0,1)))
[True, False, True, True]
>>> segment_checks(((−1,0),(1,0)),((0,−3),(0,−1)))
[True, True, False, True]
>>> segment_checks(((−1,0),(1,0)),((0,1),(0,3)))
[True, True, True, False]
|
>>> from asteroids import PolygonModel >>> asteroid = PolygonModel([(2,7), (1,5), (2,3), (4,2), (6,2), (7,4), (6,6), (4,6)]) >>> asteroid.does_intersect([(0,0),(7,7)]) True >>> asteroid.does_intersect([(0,0),(0,7)]) False |
class PolygonModel(): ... def segments(self): point_count = len(self.points) points = self.transformed() return [(points[i], points[(i+1)%point_count]) for i in range(0,point_count)] def does_collide(self, other_poly): for other_segment in other_poly.segments(): if self.does_intersect(other_segment): return True return False >>> square1 = PolygonModel([(0,0), (3,0), (3,3), (0,3)]) >>> square2 = PolygonModel([(1,1), (4,1), (4,4), (1,4)]) >>> square1.does_collide(square2) True >>> square3 = PolygonModel([(−3,−3),(−2,−3),(−2,−2),(−3,−2)]) >>> square1.does_collide(square3) False |
Now that we’ve built a functional (albeit minimal) game, let’s broaden our perspective. We can represent a wide variety of problems as systems of linear equations, not just arcade games. Linear equations in the wild often have more than two “unknown” variables, x and y. Such equations describe collections of points in more than two dimensions. In more than three dimensions, it’s hard to picture much of anything, but the 3D case can be a useful mental model. Planes in 3D end up being the analogy of lines in 2D, and they are also represented by linear equations.
To see why lines and planes are analogous, it’s useful to think of lines in terms of dot products. As you saw in a previous exercise, or may have noticed yourself, the equation ax + by = c is the set of points (x, y) in the 2D plane where the dot product with a fixed vector (a, b) is equal to a fixed number c. That is, the equation ax + by = c is equivalent to the equation (a, b) · (x, y) = c. In case you didn’t figure out how to interpret this geometrically in the exercise, let’s go through it here.
If we have a point and a (non-zero) vector in 2D, there’s a unique line that is perpendicular to the vector and also passes through the point as shown in figure 7.20.
If we call the given point (x0, y0) and the given vector (a, b), we can write a criterion for a point (x, y) to lie on the line. Specifically, if (x, y) lies on the line, then (x − x0, y − y0) is parallel to the line and perpendicular to (a, b) as shown in figure 7.21.
Because two perpendicular vectors have a zero dot product, that’s equivalent to the algebraic statement:
The quantity on the right-hand side of this equation is a constant, so we can rename it c, giving us the general form equation for a line: ax + by = c. This is a handy geometric interpretation of the formula ax + by = c, and one that we can generalize to 3D.
Given a point and a vector in 3D, there is a unique plane perpendicular to the vector and passing through that point. If the vector is (a, b, c) and the point is (x0, y0, z0), we can conclude that if a vector (x, y, z) lies in the plane, then (x − x0, y -y0, z − z0) is perpendicular to (a, b, c). Figure 7.22 shows this logic.
Every point on the plane gives us such a perpendicular vector to (a, b, c), and every vector perpendicular to (a, b, c) leads us to a point in the plane. We can express this perpendicularity as a dot product of the two vectors, so the equation satisfied by every point (x, y, z) in the plane is
(a, b, c) · (x − x0, y − y0, z − z0) = 0
ax + by + cz = ax0 + by0 + cz0
And because the right-hand side of the equation is a constant, we can conclude that every plane in 3D has an equation of the form ax + by + cz = d. In 3D, the computational problem is to decide where the planes intersect or which values of (x, y, z) simultaneously satisfy multiple linear equations like this.
A pair of non-parallel lines in the plane intersects at exactly one point. Is that single intersection point true for planes as well? If we draw a pair of intersecting planes, we can see that it’s possible for non-parallel planes to intersect at many points. In fact, figure 7.23 shows there is a whole line, consisting of an infinite number of points where two non-parallel planes intersect.
If you add a third plane that is not parallel to this intersection line, you can find a unique intersection point. Figure 7.24 shows that each pair among the three planes intersects along a line and the lines share a single point.
Finding this point algebraically requires finding a common solution to three linear equations in three variables, each representing one of the planes and having the form ax + by + cz = d. Such a system of three linear equations would have the form:
Each plane is determined by four numbers: ai, bi, ci, and di, where i = 1, 2, or 3 and is the index of the plane we’re looking at. Subscripts like this are useful for systems of linear equations where there can be a lot of variables that need to be named. These twelve numbers in total are enough to find the point (x, y, z) where the planes intersect, if there is one. To solve the system, we can convert the system into a matrix equation:
Let’s try an example. Say our three planes are given by the following equations:
You can see how to plot these planes in Matplotlib in the source code for this book. Figure 7.25 shows the result.
It’s not easy to see, but somewhere in there, the three planes intersect. To find that intersection point, we need the values of x, y, and z that simultaneously satisfy all three linear equations. Once again, we can convert the system to matrix form and use NumPy to solve it. The matrix equation equivalent to this linear system is
Converting the matrix and vector to NumPy arrays in Python, we can quickly find the solution vector:
>>> matrix = np.array(((1,1,−1),(0,2,−1),(1,0,1))) >>> vector = np.array((−1,3,2)) >>> np.linalg.solve(matrix,vector) array([−1., 3., 3.])
This tells us that (−1, 3, 3) is the (x, y, z) point where all three planes intersect and the point that simultaneously satisfies all three linear equations.
While this result was easy to compute with NumPy, you can see it’s already a bit harder to visualize systems of linear equations in 3D. Beyond 3D, it’s difficult (if not impossible) to visualize linear systems, but solving them is mechanically the same. The analogy to a line or a plane in any number of dimensions is called a hyperplane, and the problem boils down to finding the points where multiple hyperplanes intersect.
To be precise, a hyperplane in n dimensions is a solution to a linear equation in n unknown variables. A line is a 1D hyperplane living in 2D, and a plane is a 2D hyperplane living in 3D. As you might guess, a linear equation in standard form in 4D has the following form:
The set of solutions (w, x, y, z) form a region that is a 3D hyperplane living in 4D space. We need to be careful when we use the adjective 3D because it isn’t necessarily a 3D vector subspace of ℝ4. This is analogous to the 2D case: the lines passing through the origin in 2D are vector subspaces of ℝ2, but other lines are not. Vector space or not, the 3D hyperplane is 3D in the sense that there are three linearly independent directions you could travel in the solution set, like there are two linearly independent directions you can travel on any plane. I’ve included a mini-project at the end of this section to help you check your understanding of this.
When we write linear equations in even higher numbers of dimensions, we’re in danger of running out of letters to represent coordinates and coefficients. To solve this, we’ll use letters with subscript indices. For instance, in 4D, we could write a linear equation in standard form as:
a1 x1 + a2 x2 + a3 x3 + a4 x4 = b
Here, the coefficients are a1, a2, a3, and a4, and the 4D vector has the coordinates (x1, x2, x3, x4). We could just as easily write a linear equation in 10 dimensions:
a1 x1 + a2 x2 + a3 x3 + a4 x4 + a5 x5 + a6 x6 + a7 x7 + a8 x8 + a9 x9 + a10 x10 = b
When the pattern of terms we’re summing is clear, we sometimes use an ellipsis (...) to save space. You may see equations like the previous one written a1 x1 + a2 x2 + ... + a10 x10 = b. Another compact notation you’ll see involves the summation symbol Σ, which is the Greek letter sigma. If I want to write the sum of terms of the form aixi with the index i ranging from i = 1 to i = 10, and I want to state that the sum is equal to some other number b, I can use the mathematical shorthand:
This equation means the same thing as the earlier one; it is merely a more concise way of writing it. Whatever number of dimensions n we’re working in, the standard form of a linear equation has the same shape:
a1 x1 + a2 x2 + ... + anxn = b
To represent a system of m linear equations in n dimensions, we need even more indices. Our array of constants on the left-hand side of the equals sign can be denoted aij, where the subscript i indicates which equation we’re talking about and the subscript j indicates which coordinate (xj) the constant is multiplied by. For example,
a11 x1 + a12 x2 + ... + a1n xn = b1
a21 x1 + a22 x2 + ... + a2n xn = b2
am1 x1 + am2 x2 + ... + amn xn = bm
You can see that I also used the ellipsis to skip equations three through m −1 in the middle. There are m equations and n constants in each equation, so there are mn constants of the form aij in total. On the right-hand side, there are m constants in total, one per equation: b1, b2, ..., bm.
Regardless of the number of dimensions (the same as the number of unknown variables) and the number of equations, we can represent such a system as a linear equation. The previous system with n unknowns and m equations can be rewritten as shown in figure 7.26.
We saw in both 2D and 3D that it’s possible to write linear equations that don’t have a solution, or at least not a unique one. How will we know if a system of m equations in n unknowns is solvable? In other words, how will we know if m hyperplanes in n -dimensions have a unique intersection point? We’ll discuss this in detail in the last section of this chapter, but there’s one important conclusion we can draw now.
In 2D, a pair of lines can intersect at a single point. They won’t always (for instance, if the lines are parallel), but they can. The algebraic equivalent to this statement is that a system of two linear equations in two variables can have a unique solution.
In 3D, three planes can intersect at a single point. Likewise, this is not always the case, but three is the minimum number of planes (or linear equations) required to specify a point in 3D. With only two planes, you have at least a 1D space of possible solutions, which is the line of intersection. Algebraically, this means you need two linear equations to get a unique solution in 2D and three linear equations to get a unique solution in 3D. In general, you need n linear equations to be able to get a unique solution in n -dimensions.
Here’s an example when working in 4D with the coordinates (x1, x2, x3, x4), which can seem overly simple but is useful because of how concrete it is. Let’s take our first linear equation to be x4 = 0. The solutions to this linear equation form a 3D hyperplane, consisting of vectors of the form (x1, x2, x3, 0). This is clearly a 3D space of solutions, and it turns out to be a vector subspace of ℝ4 with basis (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0).
A second linear equation could be x2 = 0. The solutions of this equation on its own are also a 3D hyperplane. The intersection of these two 3D hyperplanes is a 2D space, consisting of vectors of the form (x1, 0, x3, 0), which satisfy both equations. If we could picture such a thing, we would see this as a 2D plane living in 4D space. Specifically, it is the plane spanned by (1, 0, 0, 0) and (0, 0, 1, 0).
Adding one more linear equation, x1 = 0, which defines its own hyperplane, the solutions to all three equations are now a 1D space. The vectors in this 1D space lie on a line in 4D, and have the form (0, 0, x3, 0). This line is exactly the x3 -axis, which is a 1D subspace of ℝ4.
Finally, if we impose a fourth linear equation, x3 = 0, the only possible solution is (0, 0, 0, 0), a zero-dimensional vector space. The statements x4 = 0, x2 = 0, x1 = 0, and x3 = 0 are, in fact, linear equations, but these are so simple they describe the solution exactly: (x1, x2, x3, x4) = (0, 0, 0, 0). Each time we add an equation, we reduced the dimension of the solution space by one, until we got a zero-dimensional space consisting of the single point (0, 0, 0, 0).
Had we chosen different equations, each step would not have been as clear; we would have to test whether each successive hyperplane truly reduces the dimension of the solution space by one. For instance, if we started with
we would have reduced the solution set to a 2D space, but then adding another equation to the mix
there is no effect on the solution space. Because x1 and x2 are already constrained to be zero, the equation x1 + x2 = 0 is automatically satisfied. This third equation, therefore, adds no more specificity to the solution set.
In the first case, four dimensions with three linear equations to satisfy left us with a 4 − 3 = 1 dimensional solution space. But in the second case, three equations described a less specific 2D solution space. If you have n dimensions (n unknown variables) and n linear equations, it’s possible there’s a unique solution−a zero-dimensional solution space−but this is not always the case. More generally, if you’re working in n dimensions, the lowest dimensional solution space you can get with m linear equations is n − m. In that case, we call the system of linear equations independent.
Every basis vector in a space gives us a new independent direction we can move in the space. Independent directions in a space are sometimes called degrees of freedom ; the z direction, for instance, “freed” us from the plane into larger 3D space. By contrast, every independent linear equation we introduce is a constraint; it removes a degree of freedom and restricts the space of solutions to have a smaller number of dimensions. When the number of independent degrees of freedom (dimensions) equals the number of independent constraints (linear equations), there are no longer any degrees of freedom, and we are left with a unique point.
This is a major philosophical point in linear algebra, and one you can explore more in some mini-projects that follow. In the final section of this chapter, we’ll connect the concepts of independent equations and (linearly) independent vectors.
from vectors import * def plane_equation(p1,p2,p3): parallel1 = subtract(p2,p1) parallel2 = subtract(p3,p1) a,b,c = cross(parallel1, parallel2) d = dot((a,b,c), p1) return a,b,c,d >>> plane_equation((1,1,1), (3,0,0), (0,3,0)) (3, 3, 3, 9) |
a11x1 + a12x2 + a13x3 + a14x4 + a15x5 + a16x6 + a17x7 = b1 a21x1 + a22x2 + a23x3 + a24x4 + a25x5 + a26x6 + a27x7 = b2 a31x1 + a32x2 + a33x3 + a34x4 + a35x5 + a36x6 + a37x7 = b3 a41x1 + a42x2 + a43x3 + a44x4 + a45x5 + a46x6 + a47x7 = b4 a51x1 + a52x2 + a53x3 + a54x4 + a55x5 + a56x6 + a57x7 = b5 |
>>> matrix = np.array(((0,0,0,0,1),(0,1,0,0,0),(0,0,0,1,0),(1,0,0,0,0),(1,1,1,0,0)))
>>> vector = np.array((3,1,−1,0,−2))
>>> np.linalg.solve(matrix,vector)
array([ 0., 1., −3., −1., 3.])
|
>>> matrix = np.array(((1,1,−1),(0,2,−1),(1,0,1))) >>> vector = np.array((−1,3,2)) >>> inverse = np.linalg.inv(matrix) >>> inverse array([[ 0.66666667, -0.33333333, 0.33333333], [-0.33333333, 0.66666667, 0.33333333], [-0.66666667, 0.33333333, 0.66666667]]) >>> np.matmul(inverse,matrix) array([[ 1.00000000e+00, 1.11022302e−16, −1.11022302e−16], [ 0.00000000e+00, 1.00000000e+00, 0.00000000e+00], [ 0.00000000e+00, 0.00000000e+00, 1.00000000e+00]]) >>> np.matmul(inverse, vector) array([−1., 3., 3.]) |
The notion of linear independence of vectors is clearly related to the notion of independence of linear equations. The connection comes from the fact that solving a system of linear equations is the equivalent of rewriting vectors in a different basis. Let’s explore what this means in 2D. When we write coordinates for a vector like (4, 3), we are implicitly writing the vector as a linear combination of the standard basis vectors:
In the last chapter, you learned that the standard basis consisting of e1 = (1, 0) and e2 = (0, 1) is not the only basis available. For instance, a pair of vectors like u1 = (1, 1) and u2 = (−1, 1) form a basis for ℝ2. As any 2D vector can be written as a linear combination of e1 and e2, so can any 2D vector be written as a linear combination of this u1 and u2. For some c and d, we can make the following equation true, but it’s not immediately obvious what the values of c and d are:
c · (1, 1) + d · (−1, 1) = (4, 2)
Figure 7.27 shows a visual representation of this.
As a linear combination, this equation is equivalent to a matrix equation, namely:
This, too, is a system of linear equations! In this case, the unknown vector is written (c, d) rather than (x, y), and the linear equations hidden in the matrix equation are c − d = 4 and c + d = 2. There is a 2D space of vectors (c, d) that define different linear combinations of u1 and u2, but only one simultaneously satisfies these two equations.
Any choice of the pair (c, d) defines a different linear combination. As an example, let’s look at an arbitrary value of (c, d), say (c, d) = (3, 1). The vector (3, 1) doesn’t live in the same vector space as u1 and u2 ; it lives in a vector space of (c, d) pairs, each of which describe a different linear combination of u1 and u2. The point (c, d) = (3, 1) describes a specific linear combination in our original 2D space: 3u1 + 1u2 gets us to the point (x, y) = (2, 4) (figure 7.28).
Recall that we’re trying to make (4, 2) as a linear combination of u1 and u2, so this isn’t the linear combination we were looking for. For c u1 + d u2 to equal (4, 2), we need to satisfy c − d = 4 and c + d = 2, as we saw previously.
Let’s draw the system of linear equations in the c, d plane. Visually, we can tell that (3, −1) is a point that satisfies both c + d = 2 and c − d = 4. This gives us the pair of scalars to use in a linear combination to make (4, 2) out of u1 and u2 as shown in figure 7.29.
Now we can write (4, 2) as a linear combination of two different pairs of basis vectors: (4, 2) = 4e1 + 2e2 and (4, 2) = 3u1 − 1u2. Remember, the coordinates (4, 2) are exactly the scalars in the linear combination 4e1 + 2e2. If we had drawn our axes differently, u1 and u2 could just as well have been our standard basis; our vector would be 3u1 − u2 and we would say its coordinates were (3, 1). To emphasize that coordinates are determined by our choice of basis, we can say that the vector has coordinates (4, 2) with respect to the standard basis, but it has coordinates (3, −1) with respect to the basis consisting of u1 and u2.
Finding the coordinates of a vector with respect to a different basis is an example of a computational problem that is really a system of linear equations in disguise. It’s an important example because every system of linear equations can be thought of in this way. Let’s try another example, this time in 3D, to see what I mean.
Let’s start by writing an example of a system of linear equations in 3D and then we’ll work on interpreting it. Instead of a 2-by−2 matrix and a 2D vector, we can start with a 3-by−3 matrix and a 3D vector:
The unknown here is a 3D vector; we need to find three numbers to identify it. Doing the matrix multiplication, we can break this up into three equations:
1 · x − 1 · y + 0 · z = 1
0 · x − 1 · y − 1 · z = 3
1 · x + 0 · y + 2 · z = −7
This is a system of three linear equations with three unknowns, and ax + by + cz = d is the standard form for a linear equation in 3D. In the next section, we look at the geometric interpretation for 3D linear equations. (It turns out they represent planes in 3D as opposed to lines in 2D.)
For now, let’s look at this system as a linear combination with coefficients to be determined. The previous matrix equation is equivalent to the following:
Solving this equation is equivalent to asking the question: What linear combination of (1, 0, 1), (−1, −1, 0), and (0, −1, 2) yields the vector (1, 3, −7)? This is harder to picture than the 2D example, and it is harder to compute the answer by hand as well. Fortunately, we know NumPy can handle systems of linear equations in three unknowns, so we simply pass a 3-by−3 matrix and 3D vector as inputs to the solver like this:
>>> import numpy as np >>> xw = np.array((1,3,−7)) >>> xa = np.array(((1,−1,0),(0,−1,−1),(1,0,2))) >>> np.linalg.solve(a,w) array([ 3., 2., −5.])
The values that solve our linear system are, therefore, x = 3, y = 2, and z = −5. In other words, these are the coefficients that build our desired linear combination. We can say that the vector (1, 3, −7) has coordinates (3, 2, −5) with respect to the basis (1, 0, 1), (−1, −1, 0), (0, −1, 2).
The story is the same in higher dimensions; as long as it is possible to do so, we can write a vector as a linear combination of other vectors by solving a corresponding system of linear equations. But, it’s not always possible to write a linear combination, and not every system of linear equations has a unique solution or even a solution at all. The question of whether a collection of vectors forms a basis is computationally equivalent to the question of whether a system of linear equations has a unique solution.
This profound connection is a good place to bookend part 1 with its focus on linear algebra. There will be plenty of more linear algebra nuggets throughout the book, but they are even more useful when we pair them with the core topic of part 2: calculus.
>>> matrix = np.array(((10,3),(1,2))) >>> vector = np.array((5,5)) >>> np.linalg.solve(matrix,vector) array([-0.29411765, 2.64705882]) |
>>> matrix = np.array(((0, 0, 1, 0), (0, −2, −2, 0), (1, −1, 0, −2), (1, −1, 2, 1)))
>>> vector = np.array((3,0,6,9))
>>> np.linalg.solve(matrix,vector)
array([ 1., −3., 3., −1.])
|
Model objects in a 2D video game can be done as polygonal shapes built out of line segments.
Given two vectors u and v, the points of the form u + tv for any real number t lie on a straight line. In fact, any line can be described with this formula.
Given real numbers a, b, and c, where at least one of a or b is non-zero, the points (x, y) in the plane satisfying ax + by = c lie on a straight line. This is called the standard form for the equation of a line, and any line can be written in this form for some choice of a, b, and c. Equations for lines are called linear equations.
Finding the point where two lines intersect in the plane is equivalent to finding the values (x, y) that simultaneously satisfy two linear equations. A collection of linear equations that we seek to solve simultaneously is called a system of linear equations.
Solving a system of two linear equations is equivalent to finding what vector can be multiplied by a known 2-by−2 matrix to yield a known vector.
NumPy has a built-in function, numpy.linalg.solve
, that takes a matrix and a vector and solves the corresponding system of linear equations automatically, if possible.
Some systems of linear equations cannot be solved. For instance, if two lines are parallel, they can have either no intersection points or infinitely many (which would mean they are the same line). This means there is no (x, y) value that simultaneously satisfies both lines’ equations. A matrix representing such a system is called singular.
Planes in 3D are the analogs of lines in 2D. They are the sets of points (x, y, z) satisfying equations of the form ax + by + cz = d.
Two non-parallel planes in 3D intersect at infinitely many points, and specifically, the set of points they share form a 1D line in 3D. Three planes can have a unique point of intersection that can be found by solving the system of three linear equations representing the planes.
Lines in 2D and planes in 3D are both cases of hyperplanes, sets of points in n -dimensions that are solutions to a single linear equation.
In n -dimensions, you need a system of at least n linear equations to find a unique solution. If you have exactly n linear equations and they have a unique solution, those are called independent equations.
Figuring out how to write a vector as a linear combination of a given set of vectors is computationally equivalent to solving a system of linear equations. If the set of vectors is a basis for the space, this is always possible.
100.26.35.111