Feature request #9521
Introduce support for "prepared" geometries
| 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
History
#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.