Significant drop in performance when using new pgr_alphashape function

[EPajares]

Describe the bug Dear pgrouting-maintainers,

thanks first of all for your excellent work. I personally love pgrouting and I am using it frequently! I am currently in the process of testing the pgr_alphashape function of the release pgrouting-3.0.0-rc1. When comparing the performance with the legacy function pgr_pointsaspolygon, that I am using in the release pgrouting-2.6.2 there are significant performance issues. I am not sure if this issue classifies as bug but I found no other appropriate category.

To Reproduce

These are the queries that I am running: Old version: SELECT pgr_pointsaspolygon ('SELECT (row_number() over())::integer as id, ST_X(geom)::float x, ST_Y(geom)::float y FROM vertices',0.00003)

New version: SELECT pgr_alphaShape((SELECT ST_COLLECT(geom) FROM vertices));

Expected behavior Despite the fact that probably different alpha-parameters were used internally for the query in the new version compared to the query in the old version, I would not expect this drop in performance.

Sample Data I do have sample data for the table vertices. The data is identical, but there are two files in the folder because they are coming from different PostgreSQL version.

sample_data.zip

Specifications

Old version:

PostgreSQL 11.5
POSTGIS="2.5.1 r17027" 
pgrouting-2.6.2

Docker image: eliaspajares/goat-database:stable

New version:

PostgreSQL 12.2
POSTGIS="3.0.1 ec2a9aa" 
pgrouting-3.0.0-rc1

Docker image: goatcommunity/database:12-3.0.1-2.3.14-2

I would be very thankful for any help on this!

[cvvergara]

FYI: This function should be part of PostGIS / GEOS as its a geometry function. And because of it it was adding an additional requirement for build pgRouting: CGAL

Please review the tests done for the release: https://github.com/pgRouting/pgrouting/tree/master/pgtap/alpha_shape

Try to do similar tests for the 2.6 version. You will notice that, for 2.6 version, results are not good. The geometry building that is generated is not what is expected for the benchmarks. The code on pgRouting around CGAL was not correct on the way to transmit the results. Might be faster, as geometry specialists write CGAL, but unfortunately results are wrong, because of the C/C++/SQL code that is surrounding it.

We are not going back to have CGAL as a dependency.

Performance VS Correctness

The pgr_pointsAsPolygon in 2.6 might be fast but gives incorrect results, besides the fact that the name is totally misleading of what it actually does, because for example some PostGIS functions also convert points into polygons

• ST_ConcaveHull
• ST_ConvexHull

We actually want to move that function to GEOS that is the main PostGIS dependency.

[EPajares]

Thanks a lot for this answer! I understand. I agree that it should be part of PostGIS as it is something spatial. For now I might use ST_ConcaveHull or ST_Buffer.

[sanak]

@EPajares (CC: @cvvergara, @dkastl) Well, I am interesting in this topic (even if GEOS + PostGIS (or Boost Geometry?) side support is preferable). Let me check this issue (after finishing our company's current routing project task).

[dkastl]

CGAL was a dependency that always caused quite some extra effort for adding relatively little fucntionality. But since PostGIS uses CGAL now for a while (not sure about the details though), it probably just needs someone to contribute this function to PostGIS.

[sanak]

@dkastl Oh, yes. Moving the functionality to SFCGAL may be also good idea. Here is past my thought. https://lists.osgeo.org/pipermail/pgrouting-dev/2015-April/001525.html

[dkastl]

Oh, I didn't even remember this was a topic already in 2015 ;-) Maybe @robe2 knows better if this would be possible/acceptable by PostGIS.

[EPajares]

@sanak Awesome that this is also interesting for you. Due to very little time I cannot work on it myself but I could do testing if desired.

[sanak]

@EPajares Okay, no problem. From glance of your community's system movie, the performance seems to be actually quite important factor. :) https://www.open-accessibility.org/videos

[EPajares]

Hehehe yeah it is as we use it for live calculations :)

[robe2]

Just a heads up. In PostGIS 3.3.0 ST_ConcaveHull is being done to use GEOS functionality. This new version will be exposed for those running GEOS 3.11+ (not out yet). postgis_sfcgal now also includes an AlphaShape.

Doc examples: (there is still some work going in in geos for polygons (and hopefully eventually linestrings), but the point support is pretty good from the bit I have tested. ST_ConcaveHull

The postgis_sfcgal ST_AlphaShape and ST_OptimalAlphaShape are based on the same CGAL logic as I think earlier pgRouting was.

If you happened to have a windows desktop or server, you can test our Windows CI bot builds (which contains not yet released GEOS, PostGIS, PostGIS_SFCGAL)

Download https://postgis.net/windows_downloads/ in the Experimental section

[sanak]

@robe2 Okay, thanks for the useful information!

[cvvergara]

There is now postgis alpha shape https://postgis.net/docs/manual-dev/ST_AlphaShape.html