Hi WanMil,
I've coded a quadtree that allows to store the boundary areas. Now I always
see better throughput, but memory requirement is a bit higher.
I think the way is correct, but I'll need some time for testing and fine
tuning.
Ciao,
Gerd
WanMil wrote
>
>> 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?
>
> I think the problem does not exist in the current quad tree because the
> areas are splitted into subareas. This also reduces the number of points
> and makes it quicker and easier to test. You could get the number of
> points from the boundary and decide if an area should be splitted into
> subareas. It would also be possible to save the splitted subareas as
> precompiled bounds. If your grid always have the same dimension this
> might improve the handling.
>
> You might also remove the merge step. For most tiles more than one
> precompiled file is loaded. The bounds are merged afterwards. This step
> sounds superfluous as the LocationHook only checks if one point of a way
> is in the boundary and not for all points. Therefore it is not necessary
> to have the boundary area as one complete area object.
>
> WanMil
>
>>
>> Ciao,
>> Gerd
>>
>>
>>
>> _______________________________________________
>> mkgmap-dev mailing list
>> [email protected]
>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> [email protected]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
--
View this message in context:
http://gis.638310.n2.nabble.com/Bug-in-LocationHook-tp7157897p7167271.html
Sent from the Mkgmap Development mailing list archive at Nabble.com.
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
