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

 No, you don't want to build an strtree of the edges, as that will take
 quite a bit of computational time itself. The trick to trees is to use the
 natural autocorrelation of the edges to group the leaves into internal
 nodes. That way no sorting or individual insertion is required, you just
 roll up the ordered set of edges into a tree in O(N) time, then you
 recurse back down the tree to find the answer in O(log(N)) time, so in
 theory the whole thing is never more than O(N) + O(log(N)) = O(N). Now,
 why Intersects() is still quite fast remains a mystery.

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