## Thursday, January 14, 2016

### Parallel convex hull algorithm #2

So supposing you have points on the plane with known coordinates...:
First find the centroid (marked in red) and the four points with extreme values of x and y coordinates...
Any point inside the triangles formed can be removed...
Now the recursive step is to find from the centroid  lines dividing each triangle into two pieces such that the point the line ends on is the farthest from the centroid within that section like so:

Now form triangles and remove points again...
In this case we were already done with thte last lines added forming the convex hull...
But the process may need to be iterated until all remaining points are on the polygon...

It may be useful to use polar coordinates centered at the centroid then the points can be sorted by theta and easily split into sections and the furthest point would be the point with the largest r value in each section...I think it should then be fairly straightforward to extend it to 3 dimensions using spherical coordinates instead...