Hi Wanmil I don't propose spending too much time working on efficiency. First of all: a boundary is a boundary. All elements inside should exactly match the 'real world' boundary in order to avoid highways to be found in the next city. Second: there's still some quality problems in the locator (like streets which only can be found by selecting all streets first, streets which can't be found selecting the city and then the corresponding street). Third: what I did was having a modern computer (I5-750 processor), and having the computer processing the map generation whilst doing other things like eg drinking a beer/watching a football game etc. Cheers, Johan On Sun, 15 May 2011 14:31:40 +0200, WanMil wrote:

Hi all,

I am thinking about how to reduce the processing time of the locator branch. One time consuming task is the check if a point, a line or a polygon lies inbetween, cuts or lies outside another polygon.

Processing time for this check is directly related to the number of nodes that define the polygon. So I have the idea to simplify the boundary polygons. By cutting some complex parts of the polygon the number of points should be lowered although most of the elements lying completely inside the polygons should still lying completely inside. The elements that cut the simplified edges must be rechecked with the original polygon.

Does anyone know a suitable algorithm for that? Any other ideas concerning this problem?

WanMil

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?