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.

PC Plus logoThe 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)).

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

Album cover for Greatest HitsNow playing:
Jam - The Modern World
(from Greatest Hits)

Loading similar posts...   Loading links to posts on similar topics...

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...
Preview of response