[mkgmap-dev] [locator] Simplifying the check line in polygon

Mon May 16 14:12:42 BST 2011

This sounds like a performance problem I had matching all Garmin tiles 
to country polygons. Some country definitions from Cloudmade contain 
more then 1000 polygons and there are almost 2000 tiles covering the 
world so you can imagine that this takes quite some processing time.

This is solved this by first generating a simple bounding box for all 
the country polygons. Then each tile is first pre-filtered by matching 
against the bbox (most will fall outside the bbox so this is where the 
computational speedup is made). Tiles that pass this pre-filtering are 
then matched against the real polygons.

Matching against polygons and bboxes is done using a the inside/outside 
functions of a 2D library (similar to what Jon Burgess is linking).

Speedup using such a technique is (in my case) _at least_ a factor 10.

This '1-box' tile matching algorithm has one caveat: it doesn't provide 
any speedup when you're matching against a bbox that crosses the 
-180/+180 degrees line, because all tiles will match the pre-filtering. 
When such a condition is detected the algorithm is changed to a '2-box' 
variant. This variant is a bit slower because it uses one bbox for <180 
degrees and one bbox for >-180 degrees, assuming that no boundary will 
cover the full 380 degrees.

Applying this to your problem:
- First create a simple bbox for each polygon
- Pre-filter lines/polygons against the simple bbox
- If passed the pre-filter then exact-filter lines/polygons against the 
polygon.

My code is in PHP which I can provide if you're interested in seeing an 
example, but the idea should be clear right?