Feature request #9521

Introduce support for "prepared" geometries

Added by Martin Dobias about 6 years ago. Updated almost 4 years ago.

Status:Closed
Priority:Normal
Assignee:-
Category:Vectors
Pull Request or Patch supplied:No Resolution:fixed/implemented
Easy fix?:No Copied to github as #:18111

Description

Since GEOS 3.1 there is support for some geometry operations on so called prepared geometries which can greatly improve performance:
http://trac.osgeo.org/geos/wiki/PreparedGeometry

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

History

#1 Updated by Larry Shaffer about 6 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 6 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 4 years ago

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

#4 Updated by Martin Dobias almost 4 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