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

[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.

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: the previous logic is still fully in place, but I've added additional bbox intersection checks to a number of places to avoid expensive calculations. I see this as a starting point for further discussion and improvements/cleanup of the coding in this pull request.

Speedups are quite nice so far: instead of 211.5 minutes, the above mentioned query now only takes 1.75 minutes (120x).

I have a few open points, which deserve some closer look.

• Corner cases: I still have some doubts how the dateline should be properly handled: bbox_query has some logic in place for east < west. This somehow needs to be transferred to my solution. The same probably applies to pole regions.
  => For those corner cases, we're now falling back to the current logic.
• MBR calculation: 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. This makes your bbox a bit larger as needed by the radius according to my understanding. I don't know if this difference is due to some (for me unknown requirement) for calc_ranges.
• Earth radius: This point is a bit independent, but something I noticed: the earth radius assumed in various places in around.cc (6366197.72367m) differs a bit from the average earth radius (6371009m) according to Wikipedia. I'm not quite sure if this difference is intentional?
• Relation-based bbox checking has some more potential, but not implemented: initially, minimum bounding boxes for relations were planned, but that would have introduced too many changes.

Finding Points Within a Distance of a Latitude_Longitude Using Bounding Coordinates.pdf