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

Mon Jan 16 21:35:22 GMT 2012

Hi WanMil,

> Date: Mon, 16 Jan 2012 22:16:21 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] [Patch v3] LocationHook with new Quadtree
> 
> Hi Gerd,
> 
> >  > 3. I expect that most streets do not end exactly at a city border but
> >  > lots will end some meters after it. Cutting them will increase the
> >  > number of objects much and we will have a lot of short streets. So maybe
> >  > an overlapping threshold is required for the decision not to split a
> > line.
> >
> > Okay, since I am not yet familiar with the part of the program that uses
> > the location info,
> > I'll leave that for now.
> 
> I don't want you hold off from changing that and playing around a bit. I 
> only want to list up things that come into my mind that have to be 
> solved so you can be aware of that :-)

Don't worry, I'll keep on searching for optimizations. When  I say I leave it for now that means
that I let my brain do its work without forcing it. Sometimes I wake up with an idea, and than 
I start coding.

> >
> >  >
> >  > > The remaining differences should be errors caused by the "insideness"
> >  > > problem of contains().
> >  >
> >  > Problems with the bounding box of the quadtree should be solved by
> >  > adding +1 to maxlat/maxlong of the java area object.
> >
> > Hmm, does that mean you want to shift the whole area or only selected
> > points? Which ones?
> > I thought about using the Area.transform() method to blow up the area a
> > little bit, but did not yet find
> > something useful. I think searching the shifted point is easy to
> > implement and this double (or multiple)
> > search will not happen very often.
> 
> I think it's much easier:
> In the constructor of BoundaryQuadTree.Node use the following line:
>   this.bbox = new Rectangle(bbox.getMinLong(), bbox.getMinLat(),
> 	bbox.getMaxLong() - bbox.getMinLong() + 1, bbox.getMaxLat()
> 	- bbox.getMinLat() + 1);
> 
> So just increase the width and height of the (java.awt.geom.Area) 
> bounding box by 1. That should do it(?).
I don't think so. The area keeps it's own internal bbox in field cachedBounds, 
and that is tested first when contains() is called .
Anyway, while searching for the discrepancies with and without using the lies_in 
info I found a problem with rounding errors that can result in endless loops. I've 
added a check for this, but it slows down processing a little bit.
Also, some of the postal_code boundaries are intersecting (probably errors in OSM, 
but the algorithm went amok when it happened). 

I have compared the remaining differences and found them only for ways that are 
crossing boundaries, and for those both results looked good to me.

I'll post a new patch tomorrow.

ciao,
Gerd

> 
> WanMil
> 
> 
> >
> > Ciao,
> > Gerd
> >
> _______________________________________________
> 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/20120116/9996896f/attachment.html 