Computational geometry

Introduction and Scope

Definition

Computational geometry, as one can easily guess from the name, is the branch of computer science encompassing geometrical problems and how their solutions may be implemented (efficiently, one would hope) on a computer.

Scope

Essentially all of the computational geometry you will encounter in high-school level competitions, even competitions such as the IOI, is plane Euclidean geometry, the noble subject on which Euclid wrote his Elements and a favorite of mathematical competitions. You would be hard-pressed to find contests containing geometry problems in three dimensions or higher. You also do not need to worry about non-Euclidean geometries in which the angles of a triangle don't quite add to 180 degrees, and that sort of thing. In short, the type of geometry that shows up in computer science contests is the type of geometry to which you have been exposed, countless times, in mathematics class, perhaps without being told that other geometries exist. So in all that follows, the universe is two-dimensional, parallel lines never meet, the area of a circle with radius $r$ is $\pi r^2$, and so on.

Points

Introduction

Many would claim that the point is the fundamental unit of geometry. Lines, circles, and polygons are all merely (infinite) collections of points and in fact we will initially consider them as such in order to derive several important results. A point is an exact location in space. Operations on points are very easy to perform computationally, simply because points themselves are such simple objects.

Representation: Cartesian coordinates

In our case, "space" is actually a plane, two-dimensional. That means that we need two real numbers to describe any point in our space. Most of the time, we will be using the Cartesian (rectangular) coordinate system. In fact, when points are given in the input of a programming problem, they are almost always given in Cartesian coordinates. The Cartesian coordinate system is easy to understand and every pair of real numbers corresponds to exactly one point in the plane (and vice versa), making it an ideal choice for computational geometry.
Thus, a point will be represented in the computer's memory by an ordered pair of real numbers. Due to the nature of geometry, it is usually inappropriate to use integers, as points generally do not fit neatly into the integer lattice! Even if the input consists only of points with integer coordinates, calculations with these coordinates will often yield points with non-integral coordinates, which can often cause counter-intuitive behavior that will have you scratching your head! For example, in C++, when one integer is divided by another, the result is always truncated to fit into an integer, and this is usually not desirable.

Determining whether two points coincide

Using the useful property of the Cartesian coordinate system discussed above, we can determine whether or not two given points coincide. Denote the two points by $P$ and $Q$, with coordinates $(x_1,y_1)$ and $(x_2,y_2)$, respectively, and then:

$\displaystyle P = Q \longleftrightarrow x1 = x2 \wedge y1 = y2$

Read: The statement that $P$ and $Q$ are the same point is equivalent to the statement that their corresponding coordinates are equal. That is, $P$ and $Q$ having both the same x-coordinates and also the same y-coordinates is both sufficient and necessary for the two to be the same point.

The distance between two points

To find the distance between two points, we use the Euclidean formula. Given two points $P = (x_1,y_1)$ and $Q = (x_2,y_2)$, the distance between them is given by:

$\operatorname{dist}(P,Q) = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$

(Note that when we write $P = (x_1,y_1)$, we mean that $P$ is a point with x-coordinate $x_1$ and y-coordinate $y_1$.)

The midpoint of the line segment joining two points

Given two points, how may we find the midpoint of the line segment joining two points? (Intuitively, it is the point that is "right in the middle" of two given points. One might think that we require some knowledge about line segments in order to answer this, but it is for precisely the reason that, in a certain sense, no such knowledge is required to understand the answer, that this operation is found in the Points section. So, given two points $P = (x_1,y_1)$ and $Q = (x_2,y_2)$, this midpoint is given by

$\operatorname{midpoint}(P,Q) = \left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}\right)$

Lines

What is a line?

In axiomatic geometry, some terms such as point and line are left undefined, because an infinite regression of definitions is clearly absurd. In the algebraic approach we are taking, the line is defined in terms of the points which lie on it; that will be discussed in the following section. It will just be pointed out here that the word line is being used in the modern mathematical sense. Lines are straight; the terms line and straight line shall have identical meaning. Lines extend indefinitely in both directions, unlike rays and line segments.

The equation of a line

In computational geometry, we have to treat all aspects of geometry algebraically. Computers are excellent at dealing with numbers but have no mechanism for dealing with geometrical constructions; rather we must reduce them to algebra if we wish to accomplish anything.
In Ontario high schools, the equation of a line is taught in the ninth grade. For example, the line which passes through the points (0,1) and (1,0) has the equation $x + y = 1$. Precisely, this means that for a given point $(x,y)$, the statement $x + y = 1$ is equivalent to, or sufficient and necessary for, the point to be on the line.
The form of the equation of the line which is first introduced is generally the $y = mx + b$, in which $m$ is the slope of the line and $b$ is the y-intercept. For example, the line discussed above has the equation $y = -x + 1$, that is, $m = -1$ and $b = 1$. By substituting different values for $m$ and $b$, we can obtain various (different) lines. But there's a problem here: if your line is vertical, then it is not possible to choose values of $m$ and $b$ for the line. (Try it!) This is because the y-coordinate is no longer a function of the x-coordinate.
Thus, when dealing with lines computationally, it seems we would need to have a special case: check if the line is vertical; if so, then do something, otherwise do something else. This is a time-consuming and error-prone way of coding.

Standard Form of the equation of a line

Even though the slope-intercept form cannot describe a vertical line, there is an equation that describes a vertical line. For example, the line passing through (3,1) and (3,8) is $x = 3$. In fact, almost any line can be described by an equation of the form $x = my + b$. (Try it if you don't believe me. I have merely switched around $x$ and $y$ from the slope-intercept form.) Except... horizontal lines. So we have two forms of the equation of a line: one which fails on vertical lines and one which fails on horizontal lines. Can we combine them to give an equation of the line which is valid for any line?
As it turns out, it is indeed possible.
That equation, the standard form of the equation of the line is:

$\displaystyle Ax + By + C = 0$

By substituting appropriate values of $A$, $B$, and $C$, one can describe any line with this equation. And by storing values of $A$, $B$, and $C$, one can represent a line in the computer's memory. Here are some pairs of points and possible equations for each:

$\begin{array}{llll} (0,1)&\mathrm{and}&(1,0) : & x + y - 1 = 0 \\ (3,1)&\mathrm{and}&(3,8) : & x - 3 = 0 \\ (2,5)&\mathrm{and}&(4,5) : & y - 5 = 0 \\ (6,6)&\mathrm{and}&(4,9) : & 3x + 2y - 30 = 0 \\ \end{array}$

As you can see, it handles vertical and horizontal lines properly, as well as lines which are neither.
Note that the standard form is not unique: for example, the equation of the first line could have just as well been $-x - y + 1 = 0$ or perhaps $5x + 5y - 5 = 0$. Any given line has infinitely many representations in the standard form. However, each standard form representation describes at most one line.
If $A$ and $B$ are both zero, the standard form describes no line at all.

Slope and intercepts of the line in standard form

By isolating $y$ from the standard form, we obtain the slope and y-intercept form for line $l$ ($Ax + By + C$) when $B \neq 0$ (that is, when the line is not vertical):

$\displaystyle \operatorname{slope}(l) = -\frac{A}{B}$

The y-intercept is obtained by letting $x = 0$ and then:

$\displaystyle \operatorname{y-intercept}(l) = -\frac{C}{B}$

Similarly, the x-intercept is given by:

$\displaystyle \operatorname{x-intercept}(l) = -\frac{C}{A}$

In order for the x-intercept to exist, the line must not be horizontal, that is, $A \neq 0$.

Determining if a point is on a line

Using the definition of the equation of a line, it becomes evident that to determine whether or not a point lies on a line, we simply substitute its coordinates into the equation of the line, and check if the LHS is, indeed, equal to zero. This allows us to determine, for example, that $(12,-3)$ is on the last line given in the table above, whereas $(14,-7)$ is not on that line.

Construction of the line through two given points

A good question is: how do we determine that fourth equation above, the equation of the line through (6,6) and (4,9)? It's not immediately obvious from the two points given, whereas the other three are pretty easy.
For the slope-y-intercept form $y = mx + b$, you first determined the slope $m$, and then solved for $b$. A similar procedure can be used for standard form. We state here, without proof, the following pseudocode for determining the coefficients $A$, $B$, $C$ of the equation of the line through points $(x_1, y_1)$ and $(x_2, y_2)$ in standard form:

$\begin{array}{rl} 1. & A \gets y_1 - y_2 \\ 2. & B \gets x_2 - x_1 \\ 3. & C \gets -A x_1 - B y_1 \\ \end{array}$

Parallel and coincident lines

In the slope and y-intercept form, two lines are either parallel or coincident if they have the same slope. So given two lines $l_1$ ($A_1 x + B_1 y + C_1 = 0$) and $l_2$ ($A_2 x + B_2 y + C_2 = 0$), we obtain, for $B_1,B_2 \neq 0$:

$\displaystyle -\frac{A_1}{B_1} = -\frac{A_2}{B_2}$

Cross-multiplying gives a result that is valid even if either or both lines are vertical, that is, it is valid for any pair of lines in standard form:

$\displaystyle \operatorname{parallel\_or\_coincident}(l_1,l_2) \longleftrightarrow A_1 B_2 = A_2 B_1$

Now, in the slope-y-intercept form, two lines coincide if their slopes and y-intercepts both coincide. In a manner similar to that of the previous section, we obtain:

$\displaystyle B_1 C_2 = B_2 C_1$

or, if x-intercepts are used instead:

$\displaystyle A_1 C_2 = A_2 C_1$

Two lines coincide if $A_1 B_2 = A_2 B_1$ and either of the two equations above holds. (As a matter of fact, if the two lines are coincident, they will both hold, but only one of them needs to be checked.) If $A_1 B_2 = A_2 B_1$ but the lines are not coincident, they are parallel.

Finding the point of intersection of two lines

If two lines are coincident, every point on either line is an intersection point. If they are parallel, then no intersection points exist. We consider the general case in which neither is true.
In general, two lines intersect at a single point. That is, the intersection point is the single point that lies on both lines. Since it lies on both lines, it must satisfy the equations of both lines simultaneously. So to find the intersection point of $l_1$ $(A_1 x + B_1 y + C_1 = 0)$ and $l_2$ $(A_2 x + B_2 y + C_2 = 0)$, we seek the ordered pair $(x,y)$ which satisfies:

$\begin{array}{rcl} A_1 x + B_1 y + C_1 &=& 0 \\ A_2 x + B_2 y + C_2 &=& 0 \end{array}$

This is a system of two linear equations in two unknowns and is solved by Gaussian elimination. Multiply the first by $A_2$ and the second by $A_1$, giving:

$\begin{array}{rcl} A_1 A_2 x + A_2 B_1 y + A_2 C_1 &=& 0 \\ A_1 A_2 x + A_1 B_2 y + A_1 C_2 &=& 0 \end{array}$

Subtracting the former from the latter gives, with cancellation of the $x$ term:

$\begin{array}{rcl} (A_1 B_2 - A_2 B_1)y + (A_1 C_2 - A_2 C_1) &=& 0 \\ (A_1 B_2 - A_2 B_1)y &=& A_2 C_1 - A_1 C_2 \\ y &=& \frac{A_2 C_1 - A_1 C_2}{A_1 B_2 - A_2 B_1} \end{array}$

Instead of redoing this to obtain the value of $x$, we take advantage of symmetry and simply swap all the $A$'s with the $B$'s. (If you don't believe that this works, do the derivation the long way.)

$\displaystyle x = \frac{B_2 C_1 - B_1 C_2}{B_1 A_2 - B_2 A_1}$

or:

$\displaystyle x = \frac{B_1 C_2 - B_2 C_1}{A_1 B_2 - A_2 B_1}$

Notice the quantity $A_1 B_2 - A_2 B_1$, and how it forms the denominator of the expressions for both $x$ and $y$. When solving for the intersection point on the computer, you only need to calculate this quantity once. (This quantity, called a determinant, will resurface later on.) Here is pseudocode for finding the intersection point:

$\begin{array}{rl} 1. & det \gets A_1 B_2 - A_2 B_1 \\ 2. & \mathrm{if}\ det = 0 : \\ 3. & \ \ \ \ \ \mathrm{fail} \\ 4. & \mathrm{else} : \\ 5. & \ \ \ \ \ x \gets (B_1 C_2 - B_2 C_1)/det \\ 6. & \ \ \ \ \ y \gets (A_2 C_1 - A_1 C_2)/det \end{array}$

When $det = 0$, the lines are either parallel or coincident. We now see algebraically that the division by zero prevents us from finding a unique intersection point for such pairs of lines.