Say this few time and I hope you get my meaning.
When I first implemented OSM support as a sqlite database, I invested lots of time to write the Perl script that parse the XML and loads it to a sqlite database file and to make the plugin fetching this information in quick way. That was very exiting and challenging feature to implement. But, my excitement can't be passed to the end user if they need to go over the steps I did in order to make it work fir them, end users prefer that things will just work or they will need to do minimal steps or none ;-)
Since my plugin is free and all the scripts and documentations I provided are free, I was able to provide some examples while the rest I left at the hands of the end users (fair is fair).
Until few weeks back ...
I wanted to fly a random medevac mission in a non OSM database environment. I was already aware that there was a site that allowed to fetch OSM data in XML format by the name "overpass" but I did not had then the "httplib" nor "cURL" libraries to do the "https" work for the plugin.
Long story short, I decided to fiddle with the idea to fetch "osm web" information instead of the "osm database" the plugin supports today.
The silver lining in all my OSM attempts was always around optimizations
Sites like overpass should be appreciated since they offer something for free, but the technology should not be abused by selflessness or carelessness, the site does cap the amount of data you can fetch in a day but it is quite generous for a free resource site.
My first attempt
In the plugin case, a medevac mission has few rules that limits its area of effect:
- Radius of mission between 5 and 50nm.
- Should fetch "highway" osm information.
In the image above I picked KSEA area since it was highly populated but at the same time had water bodies and rural areas around it (rural in the sense of more trees less population), good for tests but the area itself is a hefty 100nm in diameter.
Overpass needs two coordinates: Bottom Left and top Right while the plugin draws a circle as an area of effect.
So... our rectangle need to look something as follows:
Red line represents what we thought to fetch.
Dark Pinkish radius is what the plugin actual see as the area of effect
and the Light bluish color is what Overpass will return - 100nm x 100nm of filtered information.
My second attempt
This realization was somewhat disappointing since the amount of compute time of the bluish rectangle was too much, for populated areas it could take long minutes to just fetch one node at the end. Further more, we fetch information that we will never use since it is too near to the starting location.
This led me to the first optimization idea I thought of - zones:
I can divide the area into zones while excluding the center box that represents the minimum flight distance between the plane and the target.
In itself that is not a bad idea, we need to pick the boxes that left around it and are in the correct distance and pick one node from them.
My third attempt
But, after thinking this through that was also wasteful, we still need to fetch all the data around the central zone and then pick a random node....
Instead of doing so, why not go with a better approach, the 1x1nm honeycomb optimization (I just invented the name it probably has a better name in the real world):
- Divide the area into small 1x1nm boxes.
- Filter out all boxes that their center is not in the range the simmer defined.
- Pick a random box from the valid ones.
- Fetch data from overpass for that area.
- If we do not find any legal "way" node, we search for other ways in same box (we sample 50% of <way> elements).
If none is valid or found, like in the case of water bodies, we drop that area from the list and randomly pick a new area box and start all over from step 4. - If we were able to random pick a <way> node and a <node> reference from it, we can then flag the search as success.
We have a target.
This idea by itself is quite simple and most of the work is done on the client itself while fetching the data from overpass is minimized.
This approach decreased the amount of time in heavy populated areas from ~50min to prepare a random mission based on Overpass to only ~25seconds.
I could probably optimized this some more if I would have divided the areas to even smaller areas, but I think there is a good balance in this case, and if in the future we will have bigger search areas the performance will be constant (more or less).
The feature itself is already in the coming v3.0.254.4 but I'm working to integrate the same for the custom template designers.
Until next time
Blue Sky
Saar