Consider use of tree-based distance calculation

[dbaston]

PostGIS uses in-memory trees to optimize its geodetic distance calculations (see related ticket). This could easily be exposed in the lwgeom package (see commit) except that it requires inclusion of a non-public header.

If the lwgeom package always uses its included copy of liblwgeom, there doesn't seem to be a problem with using this header, but a quick scan of the automake file leaves me with the impression that this package sometimes uses the system lwgeom instead of the bundled one.

The prototypes could most likely be added to the public liblwgeom.h header, though most users wouldn't see that until the next PostGIS release in ~ 1 year.

FWIW, the performance difference is roughly 50% on a quick point-line test, and obviously increases with the complexity of the input geometries, although this is subject to the caveat described in r-spatial/sf#885.

# master branch
> microbenchmark(st_geod_distance(coast, plants[1:4,]), times=10)
Unit: seconds
                                   expr     min       lq     mean   median       uq      max neval
 st_geod_distance(coast, plants[1:4, ]) 3.79407 3.799992 3.841222 3.805284 3.875724 3.967692    10

# distance-tree branch
> microbenchmark(st_geod_distance(coast, plants[1:4,]), times=10)
Unit: seconds
                                   expr     min       lq     mean   median       uq      max neval
 st_geod_distance(coast, plants[1:4, ]) 1.80738 1.817252 1.895973 1.838641 1.961336 2.118409    10

[edzer]

We could go two ways:

• have configure check, in case of using system libraries, whether the new header is present
• drop using system libraries

I don't have a strong preference; the current situation grew rather sequentially: I used system libraries first, then discovered how to include the library so that lwgeom could go to CRAN, and then I kept both, not sure why.

[dbaston]

It looks like PostGIS is moving in the direction of not providing lwgeom as system library. So dropping use of the system library may be the best way to go. I guess an alternative is to hitch this cart to librttopo, which is a fork of liblwgeom that I believe is used by spatialite and maybe others. I think avoiding system libraries altogether will be easiest. It's not like liblwgeom is challenging to build.