add LocationIndexTree.query(BBox) #1485
Conversation
| if (bbox.contains(lat, lon)) | ||
| indexNodeList.add(nodeId); | ||
|
|
||
| // TODO should be done behind the scene? |
There was a problem hiding this comment.
Will make it possible via a SimpleVisitor class or something. Often this iteration has to be done again on the client side e.g. to fetch the edges and so this work would be an unnecessary overhead then.
|
Nice, this closes some open ends for me. Is the current state mergeable, meaning, do we think that the bounding-box query does more or less what it should? Because I'd like to. |
|
Well, this is not fully ready unfortunately. Currently all nodes are returned where the tile intersects with the shape. This is ok for visualisation, but for other use cases we have to filter these nodes and call "shape.contains(node)" as a post processing step. Now the problem is that this could be done cheap like this or in a more expensive manner if we need high precision via "shape.intersects(edge.fetchWayGeometry)". Currently exploring the options on how to do this so that this also works for a Polygon (which basically means using JTS Polygon behind our Polygon class). But we could also bring it into a mergable state faster and I'll create a new issue for the open tasks. |
|
Oh, that's exactly what I need: "May include more nodes than are contained, but never fails to return return a node that is contained". I think that's also how other implementations work. |
Ah, ok. I think there are indeed two use cases. This one, which you need and we need for fast visualization. But also the other to e.g. block certain edges but not too many! Maybe I'll bring this PR in a mergable form for the first use case and explicitly mention this and work later on the second "high precision" use case? |
Yes, please! For me, this doesn't even mean that this is currently unfinished -- filtering the result to the desired level of exclusivity is a second task, and can happen outside of the current method. This one is finished. |
|
And this method can still narrow down what it returns later on without changing its promise. |
This is exactly where I'm unsure because the method |
|
Well, "query" as a method name is vague enough that I think it can't be misunderstood as promising anything specific. ;-) Let's add a Javadoc which explains what this method does and does not (not how it does that), and it'll be fine. |
|
Ok :D Will do this ... let me just do some minor stuff. |
|
I did the following changes (let me know if this was too much):
|
| /** | ||
| * This interface allows to visit every node stored in the leafs of a LocationIndex. | ||
| */ | ||
| abstract class Visitor { |
There was a problem hiding this comment.
Just as a small remark: This Visitor is not very Java-8-friendly (see my call of the new query method in the commit I added - I can't do a lambda there, because the visitor is not a single-method interface but a multi-method abstract class), and also a bit unusual. If I understand it correctly, as a client, I have to override isTileInfo if I want onTile to be called? I think interfaces are most clear when control flows in one direction only: An interface is either for me to call, or for me to implement and be called.
There was a problem hiding this comment.
An interface is either for me to call, or for me to implement and be called.
Okay, that's actually the case here. :-) But the information flows both ways.
There was a problem hiding this comment.
Yes, I tried with a separate QueryOptions class but this was not much prettier. Should I revert it back to this to make it easier with lambda?
There was a problem hiding this comment.
Thanks! I'm doing more Isochrone experiments with this right now... ,-)
This PR adds a new query(BBox) method. Currently we can fetch only nodes from one leaf and so with this querying areas is inefficient. Related to #1127 and #1324.
Furthermore a possibility to visualize the index
and some description for the index is added. The description now makes clear that we have a Quadtree implementation with some special tuning. E.g. for bigger areas one node branches not only into 4 subtrees but can branch into 16. Previously also 64 was possible, but we removed this as this has no advantages in terms of storage, query or creation speed. (Measured it for Germany and world wide)
TODOs:
to make this correct we need to add +1/2 cell on every side of the BBox. The problem is that we do not add the node to both cells due to the bresenham line to cell limitationDoes not seem to be necessary (no problems e.g. in Render vector tiles from graph storage /mvt #1572).Shape)