Point location library

Does anyone know, is there any Julia library for the Point Location problem? My search gave nothing, only this GEOS functions, but it looks like they are not exposed in LibGEOS.jl package.

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.

1 Like

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.

1 Like