I am compiling a small library that consumes data from a geographic information system (GIS) and allows you to quickly find points, nearby point functions, and line of sight queries. Most of this data will consist of large areal objects with a huge number of vertices.
A variant of the R tree may work, although I wonder how they are executed at a point in the queries. I also suspect that searches will destroy most of the performance boost.
A square tree with children with a variable size is the next thing that comes to mind. This would allow linking between different levels of the child, and possibly speed up the line of requests to the site.
Kd also comes to mind, but again, the site’s query string may be problematic.
So the question is, what algorithm would you recommend?
source
share