> Date: Fri, 13 Jan 2012 22:19:08 +0100
> From: wmgcnfg@web.de
> To: mkgmap-dev@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@.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@.org
> >>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >>
> >> _______________________________________________
> >> mkgmap-dev mailing list
> >> mkgmap-dev@.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@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