> Date: Sun, 8 Jan 2012 22:17:25 +0100
> From: wmgcnfg@web.de
> To: mkgmap-dev@lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] Bug in LocationHook?
>
> > 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
> > mkgmap-dev@lists.mkgmap.org.uk
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev@lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev