[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):

 In strks example we get 43520 * 3153 combinations to test. For all those
 combinations we have to test both point to point and point to segment.

 So I guess it is possible that our computers isn't faster than this. If
 using 7 seconds for the distance caclulation it means about 19000
 combinations per millisecond. 19000 point to point and 19000 point to
 segment (well I guess it is two less point to segment combination).

 But there might be things to do about it also with brute force. I mean if
 we can decrease with 1 microsecond per combination it will give a huge
 effect.


 When doing it the brute force way, I think it is 2 places to look for
 optimization.

 1) Both for point/point and point/segment tests we end up with a sqrt
 calculation. When I worked on those things long time ago I tested to not
 do that sqrt calc and only do it on the resulting closest points. But I
 ran into many strange memory problems. I didn't investigate to the ens,
 but I guess it results in handling very big numbers which double precision
 can't handle. I mean 10000 km results in handling the number 10 raised by
 14. But if that is solvable (by me just doing something wrong back then) I
 guess that could make a noticable difference to avoid 38000 sqrt
 calculations per millisecond.

 2) at line 2075 in measures.c is a calculation with a lot of addition,
 substraction, multiplication and division. That line is executed for each
 point/segment test.
 There is more below in the same function, but that is only executed when
 the projected point on the segment is actually on the segment. More common
 is that the projected point is outside the segment, and the function goes
 directly to compare the endpoint of the segment with the point.

--
Ticket URL: <https://trac.osgeo.org/postgis/ticket/3587#comment:19>
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.