[QGIS-Developer] timzonefinder vs point in polygon

Matthias Kuhn matthias at opengis.ch
Tue Feb 9 09:32:15 PST 2021 

Hi Calvin,

If you are looking for speed I would consider putting things into memory.
I have seen that timezonefinder has an in_memory option which makes it even
faster.
On QGIS side you can also load features into a memory layer and add a
spatial index to that.

Hope that helps to squeeze the last bit of performance out of this
Matthias

On Tue, Feb 9, 2021 at 5:52 PM C Hamilton <adenaculture at gmail.com> wrote:

> It is highly likely that you have a much faster machine than mine so I can
> only look at comparative times between timezonefinder and the PyQGIS code
> included below. You will notice that I take a snapshot of the time before
> and after I iterate through the 10,000 points using both timezonefinder as
> a look up and the code Nyall proposed. That is how I am getting the times.
> What I am really trying to determine is the fastest way to look up a point
> using either timezonefinder or PyQGIS code. Perhaps what I have with PyQGIS
> code is fast enough, but I am not satisfied if it is not close to the speed
> of timezonefinder.
>
> Ultimately, I am trying to determine whether I should continue to use
> timezonefinder as the method to look up time zones in my
> datetimetools plugin or should I have the gpkg time zone polygon layer as a
> part of the plugin and do lookups using it. Right now I am just doing
> single point lookups and it is probably fast enough, but I don't like that
> it is slower than timezonefinder. I am likely to expand datetimetools
> plugin to have a processing algorithm to do a lookup on a whole layer and
> in that case the PyQGIS method is better.
>
> Those are my thoughts and if there is a faster method using the gpkg time
> zone polygon to do the lookup, let me know.  One thing I just tried was
> using the shapefile from
> https://github.com/evansiroky/timezone-boundary-builder. It appears it is
> not spatially indexed and was taking too long. I resaved it as a shapefile
> and made sure it had a spatial index, but the gpkg conversion of the
> shapefile is even faster to access.
>
> Calvin
>
> On Tue, Feb 9, 2021 at 11:19 AM <mail at groenebij.nl> wrote:
>
>> Hi Calvin,
>>
>>
>>
>> Thanks for sending me this from the Developers list. I am not a part of
>> the Developer list, so I did not see the Join attribute by location tip
>> from Andrea.
>>
>>
>>
>> Anyway, what do you mean with not getting fast result with single point
>> lookups?
>>
>> When I select a single point from the 10000 point layer and run the same
>> algorithm (check the selected features only option in the dialogue box),
>> the result takes 0.05 seconds (12 seconds for all 10000). At least that is
>> what is says in the log tab of the algorithm. And it sure looks quick.
>>
>>
>>
>> Jeroen
>>
>>
>>
>>
>>
>> *Van:* C Hamilton <adenaculture at gmail.com>
>> *Verzonden:* dinsdag 9 februari 2021 16:25
>> *Aan:* Nyall Dawson <nyall.dawson at gmail.com>
>> *CC:* Andrea Giudiceandrea <andreaerdna at libero.it>; qgis-developer <
>> qgis-developer at lists.osgeo.org>; Groene Bij <mail at groenebij.nl>
>> *Onderwerp:* Re: [QGIS-Developer] timzonefinder vs point in polygon
>>
>>
>>
>> Nyall,
>>
>>
>>
>> Using "Join attributes by location" on a large set of points is fast, but
>> if you are doing single point lookups it bothers me that I am not getting
>> that fast of results in comparison to timezonefinder. The 10,000 points is
>> intended to test the speed of many single point lookups. If I were going to
>> actually do 10,000 point lookups I would use the Join attributes by
>> location, but here are my results of single point lookups using
>> timezonefinder vs. your method. Note that the assumption is that they can
>> be anywhere in the EPSG:4326 bounding box. I am not trying to constrain
>> them to the QGIS canvas.
>>
>>
>>
>> timezonefinder: 44 seconds
>>
>> Your method: 144 seconds
>>
>>
>>
>> Here is my code for each:
>>
>>
>>
>> *timezonefinder*
>>
>> from timezonefinder import TimezoneFinder
>> import time
>> tf = TimezoneFinder()
>>
>> l = iface.activeLayer()
>> features = l.getFeatures()
>>
>> start_time = time.time()
>> for f in features:
>>     pt = f.geometry().asPoint()
>>     name = tf.certain_timezone_at(lng=pt.x(), lat=pt.y())
>> print('Time {}'.format(time.time() - start_time))
>>
>>
>>
>> *Your method*:
>>
>> import time
>> tzlayer = QgsVectorLayer("W:\\My
>> Documents\\GitHub\\timezone_speed_lookup_test\\timezones.gpkg",
>> "timezones", "ogr")
>>
>> l = iface.activeLayer()
>> features = l.getFeatures()
>>
>> start_time = time.time()
>> for f in features:
>>     pt = f.geometry().asPoint()
>>     rect = QgsRectangle( pt.x()-0.0000000001, pt.y()-0.000000001,
>> pt.x(),pt.y())
>>     request = QgsFeatureRequest().setFilterRect(rect)
>>     zones_intersecting_bounding_box = tzlayer.getFeatures(request)
>>     for tz_feature in zones_intersecting_bounding_box:
>>         if tz_feature.geometry().intersects(rect):
>>             name = tz_feature[1]
>>             break
>>
>> print('Time {}'.format(time.time() - start_time))
>>
>>
>>
>>
>>
>> I'd suggest using similar logic to what join attributes by location
>> does internally. In pseudocode:
>>
>> search_point = ...
>> search_bbox = QgsRectangle( search_point.x() - some tolerance,
>> search_point.y() - some_tolerance, ... )
>> request = QgsFeatureRequest().setFilterRect(search_bbox)
>> zones_intersecting_bounding_box = tz_layer.getFeatures(request)
>> for time_zone_feature in zones_intersecting_bounding_box:
>>     if time_zone_feature.intersects(search_point):
>>         # found a hit!
>>         break
>>
>> This will take advantage of whatever spatial index you have on the
>> time zone layer (e.g. the internal shapefile/gpkg/... index)
>>
>> There's quite a number of extra optimisations which could be done here
>> if the speed isn't sufficient for mouse movements, e.g. you could
>> fetch all the zone features in the canvas extent and "prepare" their
>> geometries for ultra fast point in polygon tests, and then invalidate
>> this cache and rebuild on each canvas extent change. But I'd only do
>> that kind of thing if needed...
>>
>> Nyall
>>
>>
>>
>>
>>
>> >
>> > Calvin
>> >
>> > On Fri, Feb 5, 2021 at 6:30 PM Nyall Dawson <nyall.dawson at gmail.com>
>> wrote:
>> >>
>> >> On Sat, 6 Feb 2021 at 07:54, Andrea Giudiceandrea <
>> andreaerdna at libero.it> wrote:
>> >> >
>> >> > C Hamilton wrote
>> >> > > Using the algorithm Vector->Geoprocessing Tools->Intersection: 4
>> minutes,
>> >> > > 4
>> >> > > seconds
>> >> >
>> >> > Hi Calvin,
>> >> > maybe it could be better to use the "Join attributes by location"
>> algorithm.
>> >> > It only takes few seconds to preform the join.
>> >>
>> >> Confirmed - for me it only takes ~2 seconds, and that's on an
>> >> non-optimised debug build! There may be a few % more performance boost
>> >> on the proper QGIS release builds.
>> >>
>> >> "Join attributes by location" has a bunch of extra logic to optimise
>> >> the method that the join is performed, which really pays off in this
>> >> particular situation (matching points to polygons, where number of
>> >> points >> number of polygons).
>> >>
>> >> Nyall
>> >>
>> >>
>> >>
>> >> >
>> >> > Regards.
>> >> >
>> >> > Andrea
>> >> >
>> >> >
>> >> >
>> >> > --
>> >> > Sent from:
>> http://osgeo-org.1560.x6.nabble.com/QGIS-Developer-f4099106.html
>> >> > _______________________________________________
>> >> > QGIS-Developer mailing list
>> >> > QGIS-Developer at lists.osgeo.org
>> >> > List info: https://lists.osgeo.org/mailman/listinfo/qgis-developer
>> >> > Unsubscribe: https://lists.osgeo.org/mailman/listinfo/qgis-developer
>> >> _______________________________________________
>> >> QGIS-Developer mailing list
>> >> QGIS-Developer at lists.osgeo.org
>> >> List info: https://lists.osgeo.org/mailman/listinfo/qgis-developer
>> >> Unsubscribe: https://lists.osgeo.org/mailman/listinfo/qgis-developer
>>
>> _______________________________________________
> QGIS-Developer mailing list
> QGIS-Developer at lists.osgeo.org
> List info: https://lists.osgeo.org/mailman/listinfo/qgis-developer
> Unsubscribe: https://lists.osgeo.org/mailman/listinfo/qgis-developer
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/qgis-developer/attachments/20210209/cbe8021e/attachment-0001.html>

More information about the QGIS-Developer mailing list