A Collection of Code Snippets in as Many Programming Languages as Possible

This project is maintained by TheRenegadeCoder

Welcome to the Convex Hull page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

- Jeremy Grifski
- Ron Zuckerman

Suppose you have a set of points in the plane. The **convex hull** of this set is the smallest
convex polygon that contains all the points.

A good way to visualize the problem is this: Imagine each point is a nail sticking out of the plane, and you stretch a rubber band around them and let it go. The band will contract and assume a shape that encloses the nails. This shape is the convex hull.

Note that all vertices of the convex hull are points in the original set. So the convex hull is really a subset of points from the original set, and there may be points that lie inside the polygon but are not vertices of the convex hull.

Write a program that receives two command line arguments: strings in the form `x1, x2, x3 ...`

and
`y1, y2, y3 ...`

respectively, where `(xi, yi)`

are the coordinates of the i-th point of the set.

Your program should be able to parse these lists into some internal representation in your choice language (ideally an array). From there, the program should compute the convex hull of the set of points, and output a list in the form

```
(x1, y1)
(x2, y2)
...
```

where `(xj, yj)`

are the coordinates of the j-th vertex of the convex hull.

There are many algorithms to solve this problem. You may implement any of them. Check this great document by Jeff Erickson for more details about the problem and the different algorithms to solve it.

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Convex Hull. In order to keep things simple, we split up the testing as follows:

- Convex Hull Valid Tests
- Convex Hull Invalid Tests

Description | Input X | Input Y | Output |
---|---|---|---|

Sample Input: Triangle | "100, 180, 240" | "220, 120, 20" | "(100, 220)" "(240, 20)" "(180, 120)" |

Sample Input: Pentagon | "100, 140, 320, 480, 280" | "240, 60, 40, 200, 300" | "(100, 240)" "(140, 60)" "(320, 40)" "(480, 200)" "(280, 300)" |

Sample Input: Cluster | "260, 280, 300, 320, 600, 360, 20, 240" | "160, 100, 180, 140, 160, 320, 200, 0" | "(20, 200)" "(240, 0)" "(600, 160)" "(360, 320)" |

Description | Input X | Input Y |
---|---|---|

No Input | ||

Missing Y | "100, 180, 240" | |

Invalid Shape | "100, 180" | "240, 300" |

Different Cardinality | "100, 180, 240" | "240, 60, 40, 200, 300" |

Invalid Integers | "100, 1A0, 240" | "220, 120, 20" |

All of these tests should output the following:

```
Usage: please provide at least 3 x and y coordinates as separate lists (e.g. "100, 440, 210")
```

- Convex Hull in Algol68
- Convex Hull in Beef
- Convex Hull in Commodore Basic
- Convex Hull in Euphoria
- Convex Hull in Java
- Convex Hull in Javascript
- Convex Hull in Mathematica
- Convex Hull in Php
- Convex Hull in Python
- Convex Hull in Rust