by Julian M Bucknall

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*^{2}) 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.)

Now playing:

Jam - **The Modern World**

(from *Greatest Hits*)

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.

`_emphasis_`

`**strong**`

`[text](url)`

``IEnumerable``

`* an item`

`1. an item`

`> Now is the time...`

## Preview of response