PCPlus 284: Solve computational geometry problems

For some reason, for August 2009’s article, I decided to take a bite out of computational geometry; what can only be described as a ruddy large subject. I mean, it’s huge. And it’s mathematical, to boot. I must have been delusional. Anyway, I touched on three fairly simple and well-known algorithms, well-known because they date from the very early days of computer science.

The first is the hoary chestnut: determining whether a point is inside a given polygon or not. This could be used to determine if a mouse click was inside a complex polygon on the screen (a click in a rectangle, like a button, say, is really easy to determine, provided the rectangle is oriented along the axes). The traditional answer is to draw a line off to infinity form the point, and then count the number of sides it intersects: odd, the point is inside; even the point is outside. This simple algorithm unfortunately leads to other problems, including how to tell if two lines drawn on the plane intersect or not, so I described a more modern version where you draw a horizontal line through the point and then cycle round the vertices of the polygon, checking to see if the sides thus described have their start/end points either side of the horizontal line. To do this, you just need to check the y coordinates. A little bit of logic later (an even number of intersections implies “inside”) and you have the answer.

The second is the convex hull of a set of points using the traditional method and a newer, faster one called Graham’s Scan (albeit from 1972).

The third is the “closest pair of points” problem. You’re given a set of points on the plane and you have to discover the pair that is closest together of all possible pairs. I discuss the brute-force method (a O(n²) solution) and then a more elegant and faster divide-and-conquer algorithm (essentially O(n.log n)).

This article first appeared in issue 284, August 2009.

You can download the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

  Loading links to posts on similar topics...