Boost.Geometry GSoC 2021 Competency Test

The following code is an implementation of Randomized incremental algorithm for 3D convex hull calculation. I have implemented Randomized incremental algorithm without any reference implementation, although the idea of the implementation is given in section 4.5 of the book - Computational Geometry in C by Joseph O'Rourke. The book can be downloaded from here. The data structure used to represent a polyhedron is the Winged-Edge Data Structure as described in section 4.4.1 in the book mentioned above. Though some of the attributes have been omitted for the sake of simplicity.

convex_hull_3D.hpp

main.cpp

Output

Time for Convex Hull of 100 random points: 143 ms
Time for Convex Hull of 500 random points: 1222 ms
Time for Convex Hull of 1000 random points: 4916 ms

Result

As it is evident from the results the algorithm is quadratic for now. It has a complexity of O(n²) instead of expected O(nlogn).
The reason behind this increase in complexity is because of the less efficient data structure used for representing geometry objects instead of a spatial index. The use of spatial index would enhance the complexity of the implementation to O(nlogn). If selected for GSoC 2021, I would use spatial index for implementation the convex hull algorithm.