Solve Computational Geometry Problems

Geometry is a millennia-old mathematical discipline, so you’d think that writing programs that deal with geometric concepts and problems would be a simple proposition. In fact, it’s exactly the opposite. Devising algorithms to solve geometric problems is a fascinating branch of computer science, and we’ll only briefly touch on its beauty and complexity here.

Formal geometry originated with the ancient Greeks. On computers, serious geometry only took root once we got displays that could show off graphical objects. The importance of the discipline has since been reinforced by the need for games that display lifelike scenes and the popularity of modern navigational aids.

In essence, gaming graphics are all about creating images on the computer screen and devising a system for interacting with those images. The objects can be very simple – points, lines and polygons – or convey realistic images involving light sources, textures, 3D effects and other primitives used in high-end games.

For simple 2D graphics, such as in a drawing program like Adobe Illustrator, we’re concerned with some fairly simple problems: Can I determine which shape is being clicked on by the mouse? How do I fill this polygon with a background colour? Do these lines intersect? And so on. If we’re building up an image of a scene for an action game, though, we’re usually more concerned with such geometric problems as what objects are in front of other objects (after all, if an object is fully obscured by another, we don’t have to spend the time drawing the hidden object). We also need to worry about accurate collision detection between objects, especially in fast moving games.

Another field of computational geometry is satellite navigation. Sat-nav devices have some very complex geometric problems to solve: Where are you? How can I work out where that is on an internal map? How will I display the portion of the map centred on your position? There are many interesting algorithms involved in geographical applications like this. As you can see, geometry plays an important part in modern computer applications. Let’s take a look at a few simpler issues to get a flavour of the complexities involved.

In or out?

The first thing I’ll discuss is the problem of determining whether a point is inside or outside of a polygon, which is the key to the underlying problem of determining where a mouse click occurred over an image. It’s a 2D problem, so we can describe points as a pair of coordinates: x and y. A polygon is an array of points describing the vertices (the corners) of the polygon. The sides of the polygon are the lines drawn between successive vertices in the array. For the purposes of this example, we can assume that the polygon is closed (that is, an edge is also drawn from the final point in the array to the first).

Given all that, and a separate point, how do we tell whether the point is inside the polygon? When we see the shape as an image (see above) it’s really easy to say that point A is inside it and point B outside. But when we consider the shape as an array of points, how is the calculation possible? One method is to trace a line from the point off into ‘infinity’ and count the number of sides of the polygon it crosses (see below). If the number of sides is odd, the point must have been inside the polygon; if even, outside.

Although this algorithm would work (and though there are some gotchas to do with whether the traced line intersects a vertex exactly), it’s made somewhat more complicated by having to devise a separate algorithm to determine whether two lines intersect, and another one to determine whether a line is to the left or right of a point.

A simpler algorithm works as follows (see above). Start at the first vertex (where the previous vertex is the final vertex). For each side, defined by the current vertex and the previous one, check whether the side intersects the horizontal line through the given point. Since the horizontal line is purely defined by the y-coordinate of the point, this boils down to checking whether one vertex is above the line and the other below it (that is, the y-coordinates of the two vertices are respectively less than and greater than the point’s y-coordinate). If we find such a side, we can work out the point of intersection (for which we only need to work out the x-coordinate). This is standard elementary geometry: we need to work out the equation of the line that forms the side in the form y=mx+c, and then calculate the x value, given the y value. The resulting point will either be left or right of the given point, which we can discover just by comparing x-coordinates.

Now we can count the number of intersection points to the left and right of our point. No matter what, the total number of intersections of the polygon with this horizontal line will be even. If the number of intersections on the left and right are both odd, then the given point will be inside the polygon. If both are even, then the point is outside the polygon. Problems will occur if one or more intersection points hit a vertex exactly. In this case, the simple algorithm would fall apart since both sides joining at the vertex could be said to intersect the horizontal line, throwing off our counts. The answer is to make the assumption that vertices that lie exactly on the horizontal reference line should be counted as being above it.

To be exact

Another interesting algorithm is that of the convex hull. This calculates the smallest polygon that exactly surrounds a set of points (see below), which constitutes the convex hull. We’ll take a look at the 2D variant, although there are also algorithms for solving the problem in three or more dimensions.

The simplest algorithm, known as the incremental convex hull algorithm, uses the point-in-polygon method we just discussed. The first thing to realize is that the vertices of the convex hull are all going to be points in the set we’re trying to surround. Other points in that set will be inside the convex hull and will not participate in the polygon. The shape of our initial convex hull is simple enough to work out. Choose the four points that are highest, lowest, rightmost and leftmost (that is, that have the maximum and minimum x and y coordinates). Those four points are bound to be part of the final convex hull. Now we need to calculate the remaining points. The essence of the algorithm is to step through the points in the set and see if we have to grow the current convex hull to encompass it. In other words, using the current convex hull, we have to determine whether the next point in our series lies inside or outside the convex hull. If outside, we grow the convex hull to include that point as a new vertex (and possibly remove other points if they fall within the new convex hull).

Graham’s Scan

However simple this algorithm may be, it’s really slow. A much better algorithm is Graham’s Scan, named after Ronald Graham who first described it in 1972 (see below). We start off by finding the lowest point in the set. As described above, this must be a vertex of the polygon. If there are two or more such points, choose the leftmost. We’ll add vertices to the convex hull by moving anti-clockwise around the set of points, determining whether the next point needs to be part of the convex hull or not. In order to do this, we need to pre-sort the set of points according to the angle they subtend with the initial point and the x-axis. If you think about it, this angle will always be in the range of zero to 180 degrees. Any sorting algorithm will do, but most obviously, something like a quicksort will provide the best efficiency.

Since calculating the angle is computationally intensive, we can make do with something easier to calculate that ‘represents’ the angle. The best alternative is the cotangent, since all we have to do is calculate the difference in y divided by the difference in x. Unlike the actual angle, the cotangent will decrease in value over the points, so reverse-sorting the points will work just fine.

Now that we can process the remaining points in order of decreasing cotangent (or increasing angle), we pick them off. The first such point must be on the convex hull, so we include it as a vertex. For each point after that, we look at it in reference to the two previous vertices (or, if you like, the previous edge). If the new point means we turned left from the previous side, then that new point is to be considered a vertex of the convex hull (this is shown in the diagram by point C after looking at the side AB). If, on the other hand, we turned right to reach the point, the last point we thought was a vertex was not a vertex after all, so we discard it from the list of vertices (shown by point D after looking at the side BC). We can now look at the new point with the previous two vertices. If it’s still a right turn, we discard the previous vertex again, and continue in this manner until we identify a left turn. At that point, we can add the new point as a vertex of the convex hull. We continue like this until we’ve processed all the points.

As a final look at geometric algorithms, let’s look at the closest pair of points problem. Once again we have a set of points, but this time we have to find the pair of points nearest together. This problem has a very simple brute-force solution: calculate all the distances between the points and choose the smallest. The efficiency of this algorithm, though, is proportional to the square of the number of points – in other words, it’s not very good. A better approach would be to use a ‘divide-and-conquer’ type algorithm. Let’s try it.

Divide and conquer

First of all, we need to sort all the points into x-coordinate order. Once that’s done, we can divide the points into two halves using a vertical line (that is, choose a value of x such that half the points are to the left and half to the right). We then solve the closest pair problem in both halves using the brute force method. This will produce two closest pairs, one for each half, from which we can choose the smaller of the two.

Unfortunately, this doesn’t give the correct answer just yet: there may be a pair of points that lie across the dividing line and which are actually closer together than the minimum we just calculated. Solving this might look like an awful lot of work, negating the usefulness of the divide-and-conquer strategy we just employed. But in reality, the amount of work is fairly small. Suppose that we’ve calculated an interim smallest distance of D from our two halves. All we need to do is look at the points that are within a distance D from our dividing line (that is, the x-coordinate is +/- D from the line) and calculate the distances between the points on the left and those on the right. Furthermore, we can be even stricter than that: we can ignore all points that are further away than a distance D along the y-axis as well, which further reduces the amount of computation of distances. The final answer will be the smaller one of the minimum value we’d already calculated and the cross-dividing-line minimum.

To wrap up, we’ve seen three fairly simple geometry problems and their solutions. It may look as if the algorithms are more complicated than might have been expected from looking at the images. This is true of most computational geometry: even simple-looking problems often require complex solutions. This makes the discipline one of the most important and interesting areas of computing theory.