[postgis-tickets] [PostGIS] #3587: lwgeom_mindistance2d slows down topology loading

[PostGIS]

#3587: lwgeom_mindistance2d slows down topology loading
-----------------------+---------------------------
  Reporter:  strk      |      Owner:  strk
      Type:  defect    |     Status:  new
  Priority:  medium    |  Milestone:  PostGIS 2.2.3
 Component:  topology  |    Version:  2.2.x
Resolution:            |   Keywords:  performance
-----------------------+---------------------------

Comment (by nicklas):

 small correction @pramsey, the faster way of doing it is all about single
 geometries. But I couldn't fins a way of using it when geometries is too
 close.

 Interesting also that when I tried it on your geoemtries @strk, it really
 showed that it doesn't do a goog work when such a long geometry as a is
 close to the smaller one.

 I tried by translating the geometry away from the bounding box to make the
 faster algorithm kick in. When I move it just outsinde the bounding box,
 the timing was even worse than the brute force version. But when I move it
 further away it start to kick ass.

 without moving anything on my box:

 {{{
 slowdist=# select st_distance(a, b) from slowdist;
    st_distance
 -----------------
  254918.45088224
 (1 row)

 Time: 7134.470 ms

 }}}


 Just outside the bbox (worst case inside the "circle" of the long line):
 {{{
 slowdist=# select st_distance(a, st_translate(b,-290000,0)) from slowdist;
    st_distance
 ------------------
  432666.185703918
 (1 row)


 Time: 9459.979 ms
 }}}

 But if I move the geometries more apart so geometry a is more in one
 direction from b (happens easier with geoemtries that is not so long as a)
 then we see the difference:


 {{{
 slowdist=# select st_distance(a, st_translate(b,-29000000,0)) from
 slowdist;
    st_distance
 ------------------
  28728819.1262113
 (1 row)

 Time: 23.064 ms
 }}}


 I haven't seen before cases when the "faster" way is slower than brute
 force, but I guess this is a little extreme case.

 If we insted move geometry b just above the bounding box of a we get nicer
 results at once:

 {{{
 slowdist=# select st_distance(a, st_translate(b,0,1950000)) from slowdist;
    st_distance
 ------------------
  79242.5337417284
 (1 row)

 Time: 250.828 ms
 }}}

 This doesn't help the case.

 But if @pramsey means that geos have also distance algorithms with the
 performance of ST_Intersects, I guess we should switch to them at once.

 If geos (jts) is that good also at distance calculations I think that is
 something Martin has implemented in the last years. I remember Martin
 reviewing my work and mentioned that he had thought in the same direction
 but not tested it. He also confirmed that it will not work on too close
 geometeries.

--
Ticket URL: <https://trac.osgeo.org/postgis/ticket/3587#comment:18>
PostGIS <http://trac.osgeo.org/postgis/>
The PostGIS Trac is used for bug, enhancement & task tracking, a user and developer wiki, and a view into the subversion code repository of PostGIS project.