Programming Challenge 12 : Computational Geometry

[Bichromat]

In a nutshell
Find convex hulls of sets of points, areas and intersections.

Complete description
You are given two sets of points (in 2D). Let's call them the red and the blue points. You need to:

• find the convex hull of each set (red hull, blue hull) and the hull of all the points (let's call it the green hull).
• compute their areas
• find the points contained in both the blue and the red hull
• compute the area of their convex hull (the yellow hull)
• compute the area of the intersection of the blue and the red hull

See the attachments to have a better idea of what you're asked to do.

Of course, you cannot use external tools to do the work for you.

Input
The sets (up to 5000 points) will be read from a file (input.dat). It's better if your code accepts a filename as a command line argument. The points are given as a list of (x, y) coordinates. The two sets (red then blue) are separated by a blank line. Here is an example :

0.3 5.5
8.7 4.3
6.0 7.4
3.6 3.9
2.8 0.7
7.3 1.3

8.5 5.6
3.2 6.1
10.6 0.6
8.4 2.5
2.3 2.3
6.1 -2.5

Output
Output the areas directly on the screen or in a file 'output.dat', specifying which is which (red, blue, green, yellow, intersection).

Example output (corresponds to the example input) :

Red: 36.39
Blue: 45.95
Green: 59.02
Yellow: 19.46
Intersection: 25.37648

Judging
The entries will be judged on several criteria:

• accuracy of the areas
• beauty and understandability of the code
• aptitude to react correctly to strange input
• efficiency of the algorithms

Bonus points
Bonus points will be awarded to people who provide graphical output of the hulls (you are allowed to use an external graphical library). Other suggestions : extend the concept in 3D (graphical output definitely needed. for slightly mad coders), turn your code into a quine (for totally insane programmers )

Deadline
Submit your code before May 29, 16:00 (GMT).
If you submit a new version of a previously posted entry, please indicate in your first post that a new version is available.

[AaronMT]

This is interesting and looks fun. I'm going to attempt this one using either C or C++ without the visual aspect. There is a standard algorithm, The Graham Scan Ronald Graham's 1972 paper proposed a convex hull construction algorithm that ran in O(n·lgn) time.

[Zeotronic]

I have half a mind to do this... my project is going to force me to write most of the code required anyways... including the graphical portion.

[Lster]

I'll be entering this one as I now have the time. Woohoo!

[nvteighen]

Hell: Geometry...!

I'm absolutely lost in this.

[Luke has no name]

Ugh.

[Verminox]

Hell: Geometry...!

I'm absolutely lost in this.

Me too. I have no clue what hulls are. :-\

[Lster]

See this:

http://en.wikipedia.org/wiki/Convex_hull

[Bichromat]

Wikipedia should give you all you need to know to find the convex hulls. You will also need to find how to compute areas, and a few other things. Don't worry too much about efficiency, I think all algorithms are able to deal with 5000 points in a reasonable time.

If you're stuck somewhere, don't hesitate to ask for clues

[Lster]

I'm enjoying this one immensely - good challenge!

I've still got to implement multiple sets, set merging and intersection area (of hulls).

Here's a development snapshot: