GEOSNearestPoints_r for prepared geometries

[ndawson]

The GEOSNearestPoints_r function should benefit heavily from prepared geometries -- consider adding a GEOSPreparedNearestPoints_r call which allows this.

[dbaston]

Nyall, do you have a test scenario in mind? GEOSDistanceIndexed may be of help, too.

[ndawson]

I'm hitting this one during the qgis label placement engine candidate costing code. Qgis first generates a ton of potential candidate label positions (basically via a grid over the polygon), and then ranks them by calculating the distance of the label to the boundary of the polygon. (So labels further from boundaries are preferred). This involves hundreds of calls to GEOSNearestPoints for a single polygon.

I can't find any documentation regarding GEOSDistanceIndexed (anywhere!). Does it maintain an index between calls? Is there any downside of using this over GEOSNearestPoints?

[dbaston]

I can't find any documentation regarding GEOSDistanceIndexed (anywhere!).

Hmm, maybe that's why I've never seen it used in the wild...

Does it maintain an index between calls? Is there any downside of using this over GEOSNearestPoints?

No, and I agree that prepared geometries might be a good vehicle for maintaining that index.

I haven't done testing to see what the break-even point is for an indexed vs brute-force distance calculation. The indexed calculation might be slower for very small geometries. I think you'd also have to use GEOSBoundary(polygon) as the input to GEOSDistanceIndexed, so you'd be paying for a copy.

[mdavis]

An indexed distance algorithm is definitely the way to go here. I did a prototype implementation of a fast polygon labelling algorithm [here](​https://github.com/dr-jts/jts-ports/tree/master/src/main/java/org/geotools/polylabelfast) (AKA Maximum Inner Circle). Using indexed distance sped it up hugely. Hopefully QGIS is using a similar approach (iterative refinement of the grid).

[mdavis]

Replying to dbaston:

No, and I agree that prepared geometries might be a good vehicle for maintaining that index.

Agreed, the indexed distance should be provided under prepared geometry.

[mdavis]

When the MaximunInnerCircle algorithm lands in JTS (or before...) perhaps the "polygon label point" function could be provide entirely by GEOS?

[ndawson]

perhaps the "polygon label point" function could be provide entirely by GEOS?

Is this the same as the "pole of inaccessibility"? If so, then I'd say that would be very welcome in GEOS. However, it couldn't be used in the QGIS labeling engine because we need to generate many candidates, not just a single one. In fact, a wide geographic spread and coverage of the polygon by the candidates is what we most require (As it gives the labeling problem solver more options to work with vs a cluster of candidates centered around one point).

The current QGIS algorithm is quite rudimentary, as it just halves the grid cell size each iteration until a sufficient number of candidates located inside the polygon have been generated. It's on my todo list to refine this, likely via a modification of the polylabel algorithm so that the grid cells further from the boundary are the most likely to be refined when more candidates are required (i.e. complete coverage of the whole polygon on the first iteration, then successive iterations give more candidates towards the middle of the polygon).

[strk]

I'm adding GEOSPreparedNearestPoints, PR will follow.

[strk]

The "Prepared" prefix seems to be too generic to me. If I only want to prepare a geometry for distance computation... why should I also get it prepared for predicates ? And vice-versa. Should we expose IndexedFacetDistance operation explicitly, in the C-API, instead of hooking to PreparedGeometry ?

[strk]

While exposing the function I found a crasher bug that needs be fixed first: #1065

[strk]

With #1065 fixed, here's a work in progress for GEOSPreparedNearestPoints_r: ​https://git.osgeo.org/gitea/geos/geos/pulls/107

[strk]

Nyall: is there a QGIS ticket for the speed up of labeling, relating to this ticket ?

[mdavis]

Replying to strk:

The "Prepared" prefix seems to be too generic to me. If I only want to prepare a geometry for distance computation... why should I also get it prepared for predicates ? And vice-versa. Should we expose IndexedFacetDistance operation explicitly, in the C-API, instead of hooking to PreparedGeometry ?

Reasons for sticking with Prepared:

• It's an established pattern
• There is already a PreparedGeometry object available to use. Otherwise a new state object will be needed for the index

As long as the PreparedGeometry internal indexes are created on first use, there is no cost to having multiple of them in a single object, right? And if the user is worried about lifetime of the indexes, they can just create a PreparedGeometry for each kind of query they have.

[Sandro Santilli <strk@…>]

In ba34ee2/git:

Add GEOSPreparedNearestPoints in C-API

Implement for LineString input

Closes #1007

[ndawson]

Nyall: is there a QGIS ticket for the speed up of labeling, relating to this ticket ?

1

Not specifically. There was a bunch of generic "labeling is too slow" ones, but I closed most of these some time ago and asked the submitters to send in specific reports with more detail. None have done so to date :D

[strk]

Here's a pull request for QGIS: ​https://github.com/qgis/QGIS/pull/39766 - if you recall which tickets were opened for "label is too slow" you may point them at the PR with a call-for-test