1

I have a simple SQL statement for computing the Hausdorff distance between two polygons of the form:

SELECT ST_HausdorffDistance(geom1, geom2);

, which is taking a long time (for a pair of polygons with a little over 1000 vertices each). The full query (in WKT: https://pastebin.com/ndyxE0aD) takes almost 5 seconds on a computer with Intel i9 CPU (PostgreSQL 11/PostGIS 2.5 on GEOS 3.7.2).

I needed to do this computation many times to compute Hausdorff distances between all features from two polygon tables, each with about 100 features. (The pasted example are the first records in each table). The query took 3.5 hours for such a small dataset. Similar queries on much larger road tables (with 500 to 1000 features in each table) took less than a minute.

I was wondering why the ST_HausdorffDistance computation is slow on the polygon data?

Is it because of an implementation issue or bug of PostGIS or the GEOS function behind it? Or is there something wrong with the polygon data I use?

Has anyone had similar issues with the polygon Hausdorff distance?

-- Update --

I only used time command from shell to test the times. As pointed out in the comments, the actual CPU time isn't bad at all.

For one run, the real user and sys time are 4.6, 0.05, 0.01 seconds respectively. For a larger run involving two datasets of similar polygons (but with data directly read from database, not from ST_GeomFromEWKT), it's 138m8s, 0.2 s, 0.05 s, respectively. So the CPU time is indeed small.

The GEOS package is compiled from source:

CXXFLAGS=-std=c++17 ./configure --prefix /opt/geos --enable-python
make && sudo make uninstall && sudo rm -rf /opt/geos && sudo make install  

My new question is:

Why is the real time (wall time) so long compared to CPU time? (I have a SSD.) and how to configure PostgreSQL to reduce the wall time?

10
  • only guessing, but: each vertice has to be checked against all vertices of the compared geometry (nearest neighbor like), and that is a dense multipolygon. so I reckon it's the nature of the algorithm, really. could you limit the actual measure to a proximity threshold?
    – geozelot
    May 10 '19 at 21:38
  • @ThingumaBob Thanks for your input. What puzzled me is that the polygons took so much longer than polylines for the same kinds of query, almost making me think that there is a bug in geos. I do need the Hausdorff distance rather than an approximate distance measure.
    – tinlyx
    May 11 '19 at 2:24
  • In general the runtime depends on whether the polygons are convex or concave. If convex, then it can be done in O(n+m) time, if concave then it is O(n*m); Unless I have misunderstood it, the GEOS implementation runtime is closer to the worst case, it, all sets of points are compared to each other and the maximum of the mininum is returned. It is actually a fairly straightforward algorithm and I am pretty sure there is no bug, however, given that it cannot be assumed that polygons are convex, you are left with a quadratic rather than a linear runtime- May 12 '19 at 15:17
  • I found this article quite interesting, researchgate.net/publication/…, which proposed using early breaking and random sampling to approach and approaches O(m). However, you would have to implement it yourself :D. May 12 '19 at 15:25
  • 1
    I came across this Paul Ramsey blog post the other day that talks about the cost of unzipping TOASTed geometries, effectively any large than 512 points. This might explain some of your speed issues. I believe the original question, as regards a bug in GEOS, has been answered in the negative. May 12 '19 at 20:51
0

Credit to @JohnPowell's comments.

The speed issue seems to be caused by "the cost of unzipping TOASTed geometries, effectively anything larger than 512 points." (described here), and not a PostGIS bug.

The tested polyline in my question had over 1000 vertices. To verify, I tested computing Hausdorff distance after simplifying them with ST_Simplify( ., 5). Before the simplification:

$ time psql < test_polygon_.sql
 st_hausdorffdistance 
----------------------
 9.90291831797311e-05
(1 row)


real    0m4.529s
user    0m0.056s
sys 0m0.000s

After simplification (tolerance 5 m, #vertices reduced to 125):

$ time psql < test_polygon_simplify.sql
 st_hausdorffdistance 
----------------------
                    0
(1 row)


real    0m0.190s
user    0m0.032s
sys 0m0.016s

The wall time is reduced sharply from 4.5 seconds to 0.2. Seems to support the theory on TOAST-related cost over 500 vertices.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.