Filter by geometries by bbox #55

Activity

1. springmeyer commented on Jan 24, 2018

   

   springmeyer

   on Jan 24, 2018

   Last edited by springmeyer

   ContributorAuthor

   More actions

   Per the title, one idea to solve the mapbox::vector_tile::extract_geometry bottleneck is to avoid calling it for geometries outside the radius. To do this you could:

   • Add mapbox::vector_tile::extract_bbox which would accumulate and return a bbox without decoding all vertexes of polygons/lines into sub-arrays (to avoid the memory allocation and deallocation cost of heap allocation of std::vector inside of geometry.hpp)
   • Check for situations where the distance from the bbox to the query point is > radius and return early, skipping decoding geometries and skipping calling closest_point in those cases.

   This would lead to the vtzero handlers getting called twice, so there would be that added cost. But my hope/hunch is that this cost would be small and worth it. Thoughts?
2. mapsam commented on Jan 24, 2018

   

   mapsam

   on Jan 24, 2018

   Contributor

   More actions

   Hey @springmeyer just to confirm, were these run on master or dedupe branch?
3. springmeyer commented on Jan 24, 2018

   

   springmeyer

   on Jan 24, 2018

   ContributorAuthor

   More actions

   @mapsam - dedupe

   👍React with 👍1Reacted by Sam Matthews
4. joto commented on Jan 29, 2018

   

   joto

   on Jan 29, 2018

   More actions

   Two ideas here:

   1. To save some cost from decoding the vtzero geometry twice you can return early. Instead of calculating the bbox in the first go you could, say, detect that some points of the geometry are to the left of the query point and when you find the first point that's to the right of the query point, you can stop there and directly go to the more detailed check. Makes the code more complex though.
   2. If memory allocation is the culprit here, find a way to re-use memory. You are only looking at one feature/geometry at a time, so the same memory can be reused for every geometry. Of course this doesn't work with vector-tile geometries.
5. springmeyer commented on Feb 2, 2018

   

   springmeyer

   on Feb 2, 2018

   ContributorAuthor

   More actions

   Instead of calculating the bbox in the first go you could, say, detect that some points of the geometry are to the left of the query point and when you find the first point that's to the right of the query point, you can stop there and directly go to the more detailed check. Makes the code more complex though.

   @joto - this sounds very interesting. Could you share a little more detail on how this could work? How would we be able to do these point detections without decoding the vtzero geometry twice? Are you saying that we could do these while doing the current decode somehow (perhaps within our geometry handler)? This feels a little bit similar to mapbox/mapnik-vector-tile#146 where, per geometry part/ring we would check if that ring was outside the bbox filter and then avoid adding it to the vector containing all rings.
6. springmeyer commented on Feb 2, 2018

   

   springmeyer

   on Feb 2, 2018

   Last edited by springmeyer

   ContributorAuthor

   More actions

   If memory allocation is the culprit here, find a way to re-use memory. You are only looking at one feature/geometry at a time, so the same memory can be reused for every geometry. Of course this doesn't work with vector-tile geometries.

   Yes, I had this same thought. Currently we don't need to carry through the geometry at all - we simply create each geometry in the loop and then discard. So, unless @mapsam anticipates needing to return the geometry to the user, we could potentially do this and save significant memory allocations. I presume we'd need to, however, templatize all the vector-tile 2.x functions to accept a custom geometry type that overrides the allocator? /cc @flippmoke - ideas on how this could be done?
7. mapsam commented on Feb 2, 2018

   

   mapsam

   on Feb 2, 2018

   Contributor

   More actions

   So, unless @mapsam anticipates needing to return the geometry to the user

   Nope!
8. joto commented on Feb 2, 2018

   

   joto

   on Feb 2, 2018

   More actions

   @springmeyer To do any of this you have to rid yourself of the convenience of the vector-tile functionality and use vtzero directly. This way you have access to the undecoded geometry and can decode it "manually" stopping the moment you find a point that makes it possible that the whole geometry is "near enough" to the query point. Only then you assemble the actual geometry. For points this is all very simple and you don't need vector-tile at all I would think. For more complex geometry the nearness calculation is more difficult to do, I am not sure what the best approach would be there. Maybe mapbox/vector-tile#36 would already help here.
9. artemp commented on Jul 4, 2018

   

   artemp

   on Jul 4, 2018

   Contributor

   More actions

   Might be relevant here : mapbox/vtcomposite#55
10. springmeyer commented on Dec 3, 2018

    

    springmeyer

    on Dec 3, 2018

    ContributorAuthor

    More actions

    More bbox filtering applied in mapbox/vtcomposite#91 to vcomposite