drolbr/Overpass-API — pull request #167 by mmd-osm (2014-12-27 22:12:12+00:00)
Title: Perf: Use bounding boxes as first step to speed up around statement

Recently, someone posted a question on help.openstreetmap.org regarding the following very long running query:

```C
[timeout:3600];
rel[name="Ille-et-Vilaine"][boundary=administrative];
rel(around:10000)['admin_level'='8'];out geom meta;
```

The following screenshot gives a first impression on the runtime issue in terms of objects to be checked. Our reference for comparison is a large bbox around Rennes, which already includes a 10km buffer. All the other smaller bboxes are in fact some boundary=administrative, where each way segment / node needs to be checked against the way segments/nodes in the large bbox. For the sake of clarity both segments/nodes are not shown on the screenshot.

![bbox](https://cloud.githubusercontent.com/assets/5842757/5562408/a93fc03c-8e19-11e4-9d30-497514cf9cd2.png)

Performance for the around statement was already in focus about about two years ago (see e.g. #25). One of the possible optimizations we already discussed in the past was the introduction of an additional bbox check to quickly discard non-intersecting ways.

This PR now includes a first version for a bbox-based pruning of irrelevant segments. I see this as a starting point for further discussion and improvements. Speed-ups are quite nice so far. However, functional correctness comes first:

* I still have some doubts how the dateline should be properly handled.
* Also, I was a bit confused about the earth radius used in various places in around.cc. Wikipedia cites 6371009m as average. That differs a few km from the value currenty in use: 6366197.72367m.
* Another open point is the calculating the minimum bounding box for a point + radius (calc_distance_bbox). In your approach (add_coord), you calculate east/west for the north/south border, while calc_distance_bbox uses the center point. I don't know if this difference is due to some (for me unknown requirement) for calc_ranges.
* Relation-based bbox checking: initially, minimum bounding boxes for relations were planned, but that would have introduced too many changes.