[mkgmap-dev] [Patch v3] LocationHook with new Quadtree

Fri Jan 13 21:47:34 GMT 2012

Hi WanMil,

okay, that's what it does and I think that's why it's much faster. The merge requires a few more intersect+substract calls, but it saves many area.contains() calls. Probably this should be added to the javadoc.

Ciao,
Gerd

> Date: Fri, 13 Jan 2012 22:19:08 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] [Patch v3] LocationHook with new Quadtree
> 
> Ok, I think I didn't understand your concept:
> The basis principle of the tree is that there are non intersecting areas 
> only so that only one area can be found for one point. And each area 
> contains all tags of all intersecting boundaries.
> I thought merging would be a performance thing only.
> 
> The advantage of this is that you only need one match to get all.
> If we implement cutting ways by boundaries there is the disadvantage 
> that we don't know in the LocationHook which tags are relevant and 
> therefore ways might be splitted too much.
> 
> WanMil
> 
> > Hi WanMil,
> >
> > of course it is faster, but how do you solve the problem that the
> > information is incomplete?
> > Maybe I did not make that clear:
> > Without the merge step, you have to travel through the nodeElems until
> > information from all areas in combined. If you don't do this, you have the
> > same result as in trunk when you remove an element from the list after it
> > was first processed.
> >
> > Ciao,
> > Gerd
> >
> >
> >
> >
> > WanMil wrote
> >>
> >> Mmmh, I tested with an without merge using 66 tiles.
> >>
> >> LocationHook time with merge:    72,7s
> >> LocationHook time without merge: 55,6s
> >>
> >> The times are very different. So I assumed that the GC slowed down the
> >> merge variant so I compared the timings of each tile. One tile was 8s
> >> slower with the merge variant. So maybe the GC slowed it down.
> >>
> >> But most of the tiles were quicker with the non merge variant. Some are
> >> quicker with merging and some are rather equal.
> >>
> >> Maybe timings can be improved by changing the depth and the nodeNum
> >> constraint in the split method but merging does not seem to be an
> >> overall improvement.
> >>
> >> WanMil
> >>
> >>
> >>> Hi WanMil,
> >>>
> >>> yes, it improves performance because the merge is done only once, and
> >>> without the merge it would be needed to do more or less the same action
> >>> for
> >>> each single search. I see no better way to handle the problem with those
> >>> level=7 areas.
> >>>
> >>> Ciao,
> >>> Gerd
> >>>
> >>>
> >>> WanMil wrote
> >>>>
> >>>>>    >   >   >
> >>>>>    >   >   >   * I don't understand why you need a merge() method. Could
> >>>>> you
> >>>>> explain
> >>>>>    >   >   >   what you are doing in this method and why it's required?
> >>>>>    >   >   The get method() of the tree returns the data for the first
> >>>>> area
> >>>>> that
> >>>>>    >   >   contains the coord.
> >>>>>    >   >   This area should contain all tags of the area itself plus those
> >>>>> from
> >>>>>    >   >   areas intersecting it.
> >>>>>    >   >   Maybe this is not correct?
> >>>>>    >
> >>>>>    >   Sounds wrong. If Area a1 is intersected by a2 only in 10% of its
> >>>>> area
> >>>>>    >   then an element located in the 90% that does not intersect would
> >>>>> be
> >>>>>    >   tagged with a1 and a2?
> >>>>>    >
> >>>>> The merge() first creates a new nodeElem with the intersection, it
> >>>>> merges the tags into this
> >>>>> and subtracts the intersection from the others, so only the 10% part
> >>>>> gets more tags.
> >>>>> Thinking again about this I might not need both subtract() calls since
> >>>>> I
> >>>>> move the intersection part
> >>>>> before the others .
> >>>>>
> >>>>
> >>>> I doubt that merge improves the performance. It breaks two areas into
> >>>> three probably with intersecting bounding boxes. So I would expect that
> >>>> you don't save much contains checks.
> >>>> But don't mind about my doubts: Did you measure a noticeable performance
> >>>> difference?
> >>>>
> >>>> WanMil
> >>>> _______________________________________________
> >>>> mkgmap-dev mailing list
> >>>> mkgmap-dev at .org
> >>>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >>>>
> >>>
> >>>
> >>> --
> >>> View this message in context:
> >>> http://gis.638310.n2.nabble.com/Patch-v3-LocationHook-with-new-Quadtree-tp7181669p7184965.html
> >>> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> >>> _______________________________________________
> >>> mkgmap-dev mailing list
> >>> mkgmap-dev at .org
> >>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >>
> >> _______________________________________________
> >> mkgmap-dev mailing list
> >> mkgmap-dev at .org
> >> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >>
> >
> >
> > --
> > View this message in context: http://gis.638310.n2.nabble.com/Patch-v3-LocationHook-with-new-Quadtree-tp7181669p7185332.html
> > Sent from the Mkgmap Development mailing list archive at Nabble.com.
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev at lists.mkgmap.org.uk
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> 
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120113/92dae13e/attachment.html 