If there is no Julia package, maybe someone can direct me to good implementation in other languages (other than GEOS)? Because in such a case I want to try to implement it on my own and would like to compare it with the current “golden standard”.
This is a few months late, as I just joined. I don’t know of any existing packages in Julia, but I comment because I had to solve this myself as well. Depending on your exact needs, you may or may not need a “gold standard”. It also depends on what data structure you are using. Maybe my experience is of some help.
I wrote a Delaunay Triangulation routine back in 1995 in Fortran (believe it or not). I needed to build a triangular mesh from 3 meter DEM data over a large area, circle of radius 40 km. Back then, that much data wouldn’t even fit in memory, so I also had to devise some sort of thinning algorithm (decimation, I called it) to reduce the density of points as you go further out from the centre.
If you are at all serious about writing your own code for this, I highly recommend Donald Knuth’s text called “The Standard Graphbase - A Platform for Combinatorial Computing”, 1994. The code is probably still available. I don’t know if anyone has build wrappers for it. His code is in C, but he used his CWEB system of literate programming, so you have to get a bit familiar with the CWeave and Tangle programs to compile the code. Yet another interesting system with which Knuth was way ahead of his time.
Oh, I wrote my own implementation long time ago GitHub - Arkoniak/TimeZoneLookup.jl I havn’t registered it yet, since it requires proper documentation and I was too lazy to do it. It is based on trapezoidal search and super fast, if I remember correctly, it was like 100ns per request.