Feature request #9521

Introduce support for "prepared" geometries

Added by Martin Dobias about 10 years ago. Updated almost 8 years ago.

Pull Request or Patch supplied:No Resolution:fixed/implemented
Easy fix?:No Copied to github as #:18111


Since GEOS 3.1 there is support for some geometry operations on so called prepared geometries which can greatly improve performance:

We could have a new class QgsPreparedGeometry in QGIS core library that would encapsulate the GEOS operations - various fTools algorithms could benefit from that. For example, points in polygon algorithm which may take really long time otherwise (see #5162)

Related issues

Related to QGIS Application - Bug report #9655: Strange behavior of labeling for multipolygons, due to ge... Closed 2014-02-25


#1 Updated by Larry Shaffer about 10 years ago

Hi Martin,

Do you think such prepared geometry could be used in PAL lib to make the overlap-check algorithm more efficient?

#2 Updated by Martin Dobias about 10 years ago

Hi Larry - the algorithm in PAL that checks overlaps in PAL works with label candidate rectangles (possibly rotated), it is relatively simple computation to check whether rectangles intersect (16x dot product). I am not sure if prepared geometries would improve that (they are very good for complex geometries). Probably a more valid optimization would be to stop counting overlaps after reaching a certain amount - and penalize the candidate with a fixed cost. In dense areas PAL may compute millions of overlaps without having much use for that.

Also, the overlap-check algorithm is just one part of the pre-processing for labeling - I recall there were also other pieces of code where sub-optimal geometry algorithms were involved...

#3 Updated by Alexander Bruy almost 8 years ago

Maybe I'm wrong, but now we have methods in API to get prepared geometry

#4 Updated by Martin Dobias almost 8 years ago

  • Resolution set to fixed/implemented
  • Status changed from Open to Closed

Indeed, it has been introduced in the geometry refactoring work.

Also available in: Atom PDF