The repository contains algorithm based on binary search tree using, which have average case time complexity O(N*log(H)) where N is the size of the input set of points and H is the number of vertices found to be on the convex hull. The algorithm calculates the approximate center and stores all convex hull points in balanced binary search tree by the angle from it. Implementation of the new algorithm is written in C++ and tested against well-known algorithms. Our approach works better on low percentage of points in hull which is common case in convex hull calculation.
convex_hull_bst is lincesed under the MIT. Full details in LICENSE.md.
This algorithm is better than the most popular Graham Scan on low percentage of points. You can see results of testing our algorithm against Graham Scan on this chart:
In this table you can see the ratio of the working time of the new algorithm to the Graham Scan:
