# Thread: Programming Challenge 12 : Computational Geometry

1. ## Programming Challenge 12 : Computational Geometry

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 :

Code:
```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) :
Code:
```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 )

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.
Last edited by Bichromat; May 23rd, 2008 at 08:03 PM. Reason: added some precisions

2. ## Re: Programming Challenge 12 : Computational Geometry

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.

3. ## Re: Programming Challenge 12 : Computational Geometry

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.

4. Dark Roasted Ubuntu
Join Date
Jun 2006
Beans
943

## Re: Programming Challenge 12 : Computational Geometry

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

5. ## Re: Programming Challenge 12 : Computational Geometry

Hell: Geometry...!

I'm absolutely lost in this.

Ugh.

7. ## Re: Programming Challenge 12 : Computational Geometry

Originally Posted by nvteighen
Hell: Geometry...!

I'm absolutely lost in this.
Me too. I have no clue what hulls are. :-\

8. Dark Roasted Ubuntu
Join Date
Jun 2006
Beans
943

9. ## Re: Programming Challenge 12 : Computational Geometry

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

10. Dark Roasted Ubuntu
Join Date
Jun 2006
Beans
943

## Re: Programming Challenge 12 : Computational Geometry

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:
Last edited by Lster; August 28th, 2008 at 09:37 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•