[GEOS] #1007: GEOSNearestPoints_r for prepared geometries

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

[GEOS] #1007: GEOSNearestPoints_r for prepared geometries

geos-2
#1007: GEOSNearestPoints_r for prepared geometries
-------------------------+--------------------------
 Reporter:  ndawson      |      Owner:  geos-devel@…
     Type:  enhancement  |     Status:  new
 Priority:  minor        |  Milestone:
Component:  Default      |    Version:
 Severity:  Unassigned   |   Keywords:
-------------------------+--------------------------
 The GEOSNearestPoints_r function should benefit heavily from prepared
 geometries -- consider adding a GEOSPreparedNearestPoints_r call which
 allows this.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1007>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1007: GEOSNearestPoints_r for prepared geometries

geos-2
#1007: GEOSNearestPoints_r for prepared geometries
-------------------------+---------------------------
 Reporter:  ndawson      |       Owner:  geos-devel@…
     Type:  enhancement  |      Status:  new
 Priority:  minor        |   Milestone:
Component:  Default      |     Version:
 Severity:  Unassigned   |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by dbaston):

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

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1007#comment:1>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1007: GEOSNearestPoints_r for prepared geometries

geos-2
In reply to this post by geos-2
#1007: GEOSNearestPoints_r for prepared geometries
-------------------------+---------------------------
 Reporter:  ndawson      |       Owner:  geos-devel@…
     Type:  enhancement  |      Status:  new
 Priority:  minor        |   Milestone:
Component:  Default      |     Version:
 Severity:  Unassigned   |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by 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?

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1007#comment:2>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1007: GEOSNearestPoints_r for prepared geometries

geos-2
In reply to this post by geos-2
#1007: GEOSNearestPoints_r for prepared geometries
-------------------------+---------------------------
 Reporter:  ndawson      |       Owner:  geos-devel@…
     Type:  enhancement  |      Status:  new
 Priority:  minor        |   Milestone:
Component:  Default      |     Version:
 Severity:  Unassigned   |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by 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.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1007#comment:3>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1007: GEOSNearestPoints_r for prepared geometries

geos-2
In reply to this post by geos-2
#1007: GEOSNearestPoints_r for prepared geometries
-------------------------+---------------------------
 Reporter:  ndawson      |       Owner:  geos-devel@…
     Type:  enhancement  |      Status:  new
 Priority:  minor        |   Milestone:
Component:  Default      |     Version:
 Severity:  Unassigned   |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by 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).

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1007#comment:4>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1007: GEOSNearestPoints_r for prepared geometries

geos-2
In reply to this post by geos-2
#1007: GEOSNearestPoints_r for prepared geometries
-------------------------+---------------------------
 Reporter:  ndawson      |       Owner:  geos-devel@…
     Type:  enhancement  |      Status:  new
 Priority:  minor        |   Milestone:
Component:  Default      |     Version:
 Severity:  Unassigned   |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by mdavis):

 Replying to [comment:3 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.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1007#comment:5>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1007: GEOSNearestPoints_r for prepared geometries

geos-2
In reply to this post by geos-2
#1007: GEOSNearestPoints_r for prepared geometries
-------------------------+---------------------------
 Reporter:  ndawson      |       Owner:  geos-devel@…
     Type:  enhancement  |      Status:  new
 Priority:  minor        |   Milestone:
Component:  Default      |     Version:
 Severity:  Unassigned   |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by mdavis):

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

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1007#comment:6>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1007: GEOSNearestPoints_r for prepared geometries

geos-2
In reply to this post by geos-2
#1007: GEOSNearestPoints_r for prepared geometries
-------------------------+---------------------------
 Reporter:  ndawson      |       Owner:  geos-devel@…
     Type:  enhancement  |      Status:  new
 Priority:  minor        |   Milestone:
Component:  Default      |     Version:
 Severity:  Unassigned   |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by 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).

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1007#comment:7>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1007: GEOSNearestPoints_r for prepared geometries

geos-2
In reply to this post by geos-2
#1007: GEOSNearestPoints_r for prepared geometries
-------------------------+-----------------------
 Reporter:  ndawson      |       Owner:  strk
     Type:  enhancement  |      Status:  assigned
 Priority:  minor        |   Milestone:
Component:  Default      |     Version:
 Severity:  Unassigned   |  Resolution:
 Keywords:               |
-------------------------+-----------------------
Changes (by strk):

 * status:  new => assigned
 * owner:  geos-devel@… => strk


Comment:

 I'm adding GEOSPreparedNearestPoints, PR will follow.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1007#comment:8>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel