## 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(n2) solution) and then a more elegant and faster divide-and-conquer algorithm (essentially O(n.log n)).

(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.)

Now playing:
Jam - The Modern World
(from Greatest Hits)

#### No Responses

Feel free to add a comment...

##### Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

•  Emphasize with italics: surround word with underscores `_emphasis_`
•  Emphasize strongly: surround word with double-asterisks `**strong**`
•  Link: surround text with square brackets, url with parentheses `[text](url)`
•  Inline code: surround text with backticks ``IEnumerable``
•  Unordered list: start each line with an asterisk, space `* an item`
•  Ordered list: start each line with a digit, period, space `1. an item`
•  Insert code block: start each line with four spaces
•  Insert blockquote: start each line with right-angle-bracket, space `> Now is the time...`