[postgis-devel] [PostGIS] #1806: Extremely slow and CPU-intensive ST_MakeValid (ST_BuildArea) case

[PostGIS]

#1806: Extremely slow and CPU-intensive ST_MakeValid (ST_BuildArea) case
----------------------+-----------------------------------------------------
  Reporter:  strk     |       Owner:  strk         
      Type:  defect   |      Status:  closed       
  Priority:  high     |   Milestone:  PostGIS 2.0.1
 Component:  postgis  |     Version:  2.0.x        
Resolution:  fixed    |    Keywords:               
----------------------+-----------------------------------------------------

Comment(by strk):

 @hugoledoux: thank you very much for the pointer, looking forward to see
 that code get into PostGIS!

 Meanwhile I shall point out that as of r9731 the complexity of
 ST_MakeValid is not quadratic anymore, doing a single overlay during the
 BuildArea phase.

 The current hot-spot for performance impromvements in ST_MakeValid are the
 polygonizer (finding 5561 faces in about ~15 seconds) and a Difference
 call used to find which edges are missing from the output of BuildArea
 (finding no boundary missing in ~12 seconds). Plus there are ~3 seconds
 used to link 5561 polygonized faces to their ancestors (finding which face
 is an hole of which other face, which can be probably improved).

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