Jarl K. Holta
Various algorithms
I thought I'd share some work, as described I dabble a fair bit in Computational geometry and I have implemented numerous custom algorithms for well known problems, often problems that are not as well defined, but also those which are.
Here's a snapshot of some algorithms I've made over the years.
Skeletonization
Efficient algorithm for skeletonization - does not guarantee connected skeleton but usually produces one.
https://gist.github.com/slackydev/316cc8f862b33108222aab8f1cc0da72 https://github.com/Villavu/Simba/blob/3276def9ba9c306360001400d796c6c2d7998ea9/Source/simba.vartype_pointarray.pas#L2456
Clustering
Efficient spatial 2d clustering algorithm for separating groups of points by distance.
This algorithm has been used for various computer vision tasks, and performs well, and has been optimized more by others in separate implementations.
Just for fun I've made a very simple recursive O(n^2) variant: https://gist.github.com/slackydev/fcfd4bf27f3eb3c90c465cc8fe6e8952
Which can actually be implemented using a KD-tree (here in Pascal), even though it uses a KD-tree, this variant also grows roughly quadratic in worst case which happens when most or all points are a single group: https://gist.github.com/slackydev/1e4c6131ae78f7a50cab9ecd745c2030
MinAreaCircle
Solving the problem of generating a minimum circumference circle covering any set of points in O(n log n) time while being a simple algorithm to implement.
ConcaveHull
Two approximating algorithms for generating a fitting concave polygon from a set of points. Both images are generated at default parameters.
https://gist.github.com/slackydev/5e6ac4b07cbec895baf4e7eb0faeff13
ConvexityDefects
Image shows convexity defects based on concavehull algorithm shown above, wrapped with convexhull.
https://gist.github.com/slackydev/fe5626292a8d0fedd88444f578d12803