Hi WanMil
> I remember that I tried the other strategy. I don't remember how I did
> organize the boundaries. But it was *magnitudes* slower (not just slower
> but magnitudes slower) so that I didn't started to improve my poor
> implementation.
>
I tried it anyway and found some interesting results:
Sometimes it is ~ 20% faster, sometimes it is much slower (maybe 100% ). So, I
think it might be a good alternative if we can avoid the bad cases.
I created a simple grid that stores all boundaries that intersect with each
element (similar to the grid in splitter). This is done quicker than the
creation of the quadtree.
Using the grid, for each Coord I get a list of boundaries to test:
...
Boundary b = currentBoundaries.get(blist.get(i));
if (b.getBbox().contains(co)){
if
(b.getArea().contains(co.getLongitude(),co.getLatitude())){
return b; // return the area that contains the point
}
}
...
the performance problem is in the b.getArea().contains(...)
For some boundaries, this test performs very slowly (> 1ms for one test), and
it seems to be related to the number of points that form the shape of the
boundary.
Some areas are built with < 20 points, others with > 8000.
So, what I need is a quicker contains() or some kind of tree that allows to
avoid it.
Any idea?
Ciao,
Gerd
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
