[PATCH V2] boundary preparer with quadtree

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

[PATCH V2] boundary preparer with quadtree

Gerd Petermann
Hi,

attached is the patch that works on linux systems, no functional change to v1.

boundary_prep_quadtree_v2.patch

Gerd
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

WanMil
Hi Gerd,

I need some time to look through your patch. But after a first short
look through I wonder if you tried to handle the balancing act between
keeping the old bnd format and saving your quadtree in an apropriate way.

Using the boundary lister I think have seen that you save each boundary
but no merged boundary? I see you are saving admin_level=2 and
additionally admin_level=4 and admin_level=6 etc. I expected that one of
your improvements is that you are doing the complete merge step during
preparation so that you save one area (or boundary) with all infos of
admin_level=2,4 and 6.

Your new mkgmap:boundaryid format mixes multiple information in one tag.
I think it is better to use the mkgmap:boundaryid for the id only and
one or more additional tags for your quadtree information.

That's just my first impression. I think your idea is exactly right to
move the merge step to the preparer. I am not 100% sure if it is
necessary to save the quadtree node infos. But I am sure you have
compared the performance :-)

WanMil

> Hi,
>
> attached is the patch that works on linux systems, no functional change to
> v1.
>
> http://gis.19327.n5.nabble.com/file/n5459686/boundary_prep_quadtree_v2.patch
> boundary_prep_quadtree_v2.patch
>
> Gerd
>
> --
> View this message in context: http://gis.19327.n5.nabble.com/PATCH-V2-boundary-preparer-with-quadtree-tp5459686p5459686.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

Gerd Petermann
Hi WanMil,

my goal was to save the information in a way that filling the quadtree can be done with
a minimum of complex operations like Area.subtract() or intersect().
The BoundaryQuadTree.merge() information is stored in the mkgmap:intersects_with tag.
Each boundary saved a treepath is trimmed to its place in the quadtree, level2 boundaries
are probably only saved with their tags and the bounding box. I used this way to enable
the locator to chose the right when used in LocationHook.
One drawback of this method is that we have many small parts of boundaries, which is bad
for tools like BoundaryLister or BoundaryFile2Gpx, but best for LocationHook.
I am not sure if it is better to convert each of the tools to handle the quadtree format as well or
to add an adaptor which tries to rebuild the original boundary list.
I guess the adaptor is the better choice.
The other drawback is that the bnd file contains a lot more redundant information. All tags of a level-8 boundary
that overlaps multiple quadtree nodes are saved many times, maybe with different mkgmap:intersects_with tags,
and for sure with different area info.
If you don't mind creating a completely new bnd format, I would not save this redundant info, instead I would
save the common tags once, and then all areas, and only the tags for ref-only boundaries.

Ciao,
Gerd




> Date: Mon, 6 Feb 2012 23:11:27 +0100

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] [PATCH V2] boundary preparer with quadtree
>
> Hi Gerd,
>
> I need some time to look through your patch. But after a first short
> look through I wonder if you tried to handle the balancing act between
> keeping the old bnd format and saving your quadtree in an apropriate way.
>
> Using the boundary lister I think have seen that you save each boundary
> but no merged boundary? I see you are saving admin_level=2 and
> additionally admin_level=4 and admin_level=6 etc. I expected that one of
> your improvements is that you are doing the complete merge step during
> preparation so that you save one area (or boundary) with all infos of
> admin_level=2,4 and 6.
>
> Your new mkgmap:boundaryid format mixes multiple information in one tag.
> I think it is better to use the mkgmap:boundaryid for the id only and
> one or more additional tags for your quadtree information.
>
> That's just my first impression. I think your idea is exactly right to
> move the merge step to the preparer. I am not 100% sure if it is
> necessary to save the quadtree node infos. But I am sure you have
> compared the performance :-)
>
> WanMil
>
> > Hi,
> >
> > attached is the patch that works on linux systems, no functional change to
> > v1.
> >
> > http://gis.19327.n5.nabble.com/file/n5459686/boundary_prep_quadtree_v2.patch
> > boundary_prep_quadtree_v2.patch
> >
> > Gerd
> >
> > --
> > View this message in context: http://gis.19327.n5.nabble.com/PATCH-V2-boundary-preparer-with-quadtree-tp5459686p5459686.html
> > Sent from the Mkgmap Development mailing list archive at Nabble.com.
> > _______________________________________________
> > mkgmap-dev mailing list
> > [hidden email]
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

WanMil
Gerd,

I asked to keep the bnd file format before you decided to put quadtree
info into the precompiled bounds. Now the situation has changed and I
agree that it is better to change the format. Otherwise too many tricks
must be used which make it much more complicated to understand what happens.

So feel free to change the format :-)
If possible please also think about Klaus wish to use one zip file
instead of lots of single files. I know there is a problem that the ZIP
file classes of Java are not thread safe. But for reading it should be
possible to use a ThreadLocal ZIP file reader (just an idea....).

The old tools must not be kept but some changed or new tools that helps
to get infos about the precompiled bounds should exist after the format
change. Some ideas what might be of interest:
* Which boundaries are used at a given location?
* Listing of a boundary file
* Merging all areas of a given admin_level over all bnd files. I can
send you a tool for the old bnd format which creates GPX files with the
coverage of admin_levels. This was quite necessary to check which
countries were broken.
* ...

WanMil

> Hi WanMil,
>
> my goal was to save the information in a way that filling the quadtree
> can be done with
> a minimum of complex operations like Area.subtract() or intersect().
> The BoundaryQuadTree.merge() information is stored in the
> mkgmap:intersects_with tag.
> Each boundary saved a treepath is trimmed to its place in the quadtree,
> level2 boundaries
> are probably only saved with their tags and the bounding box. I used
> this way to enable
> the locator to chose the right when used in LocationHook.
> One drawback of this method is that we have many small parts of
> boundaries, which is bad
> for tools like BoundaryLister or BoundaryFile2Gpx, but best for
> LocationHook.
> I am not sure if it is better to convert each of the tools to handle the
> quadtree format as well or
> to add an adaptor which tries to rebuild the original boundary list.
> I guess the adaptor is the better choice.
> The other drawback is that the bnd file contains a lot more redundant
> information. All tags of a level-8 boundary
> that overlaps multiple quadtree nodes are saved many times, maybe with
> different mkgmap:intersects_with tags,
> and for sure with different area info.
> If you don't mind creating a completely new bnd format, I would not save
> this redundant info, instead I would
> save the common tags once, and then all areas, and only the tags for
> ref-only boundaries.
>
> Ciao,
> Gerd
>
>
>
>
>  > Date: Mon, 6 Feb 2012 23:11:27 +0100
>  > From: [hidden email]
>  > To: [hidden email]
>  > Subject: Re: [mkgmap-dev] [PATCH V2] boundary preparer with quadtree
>  >
>  > Hi Gerd,
>  >
>  > I need some time to look through your patch. But after a first short
>  > look through I wonder if you tried to handle the balancing act between
>  > keeping the old bnd format and saving your quadtree in an apropriate way.
>  >
>  > Using the boundary lister I think have seen that you save each boundary
>  > but no merged boundary? I see you are saving admin_level=2 and
>  > additionally admin_level=4 and admin_level=6 etc. I expected that one of
>  > your improvements is that you are doing the complete merge step during
>  > preparation so that you save one area (or boundary) with all infos of
>  > admin_level=2,4 and 6.
>  >
>  > Your new mkgmap:boundaryid format mixes multiple information in one tag.
>  > I think it is better to use the mkgmap:boundaryid for the id only and
>  > one or more additional tags for your quadtree information.
>  >
>  > That's just my first impression. I think your idea is exactly right to
>  > move the merge step to the preparer. I am not 100% sure if it is
>  > necessary to save the quadtree node infos. But I am sure you have
>  > compared the performance :-)
>  >
>  > WanMil
>  >
>  > > Hi,
>  > >
>  > > attached is the patch that works on linux systems, no functional
> change to
>  > > v1.
>  > >
>  > >
> http://gis.19327.n5.nabble.com/file/n5459686/boundary_prep_quadtree_v2.patch
>  > > boundary_prep_quadtree_v2.patch
>  > >
>  > > Gerd
>  > >
>  > > --
>  > > View this message in context:
> http://gis.19327.n5.nabble.com/PATCH-V2-boundary-preparer-with-quadtree-tp5459686p5459686.html
>  > > Sent from the Mkgmap Development mailing list archive at Nabble.com.
>  > > _______________________________________________
>  > > mkgmap-dev mailing list
>  > > [hidden email]
>  > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>  >
>  > _______________________________________________
>  > mkgmap-dev mailing list
>  > [hidden email]
>  > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

Gerd Petermann
Hi WanMil,



> Date: Tue, 7 Feb 2012 21:39:35 +0100

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] [PATCH V2] boundary preparer with quadtree
>
> Gerd,
>
> I asked to keep the bnd file format before you decided to put quadtree
> info into the precompiled bounds. Now the situation has changed and I
> agree that it is better to change the format. Otherwise too many tricks
> must be used which make it much more complicated to understand what happens.
>
> So feel free to change the format :-)

okay, I will try to find a new format that fits better for the quadtree solutuion.
Would you mind dropping the support for the old format ?

> If possible please also think about Klaus wish to use one zip file
> instead of lots of single files. I know there is a problem that the ZIP
> file classes of Java are not thread safe. But for reading it should be
> possible to use a ThreadLocal ZIP file reader (just an idea....).

Okay, I'll try to code that as well.

>
> The old tools must not be kept but some changed or new tools that helps
> to get infos about the precompiled bounds should exist after the format
> change. Some ideas what might be of interest:
> * Which boundaries are used at a given location?
> * Listing of a boundary file
> * Merging all areas of a given admin_level over all bnd files. I can
> send you a tool for the old bnd format which creates GPX files with the
> coverage of admin_levels. This was quite necessary to check which
> countries were broken.
> * ...
>

Okay, I think this can all be done.
I'll start with the correction of the inner/outer solution, followed by the points mentioned here.

Gerd





> WanMil
>
> > Hi WanMil,
> >
> > my goal was to save the information in a way that filling the quadtree
> > can be done with
> > a minimum of complex operations like Area.subtract() or intersect().
> > The BoundaryQuadTree.merge() information is stored in the
> > mkgmap:intersects_with tag.
> > Each boundary saved a treepath is trimmed to its place in the quadtree,
> > level2 boundaries
> > are probably only saved with their tags and the bounding box. I used
> > this way to enable
> > the locator to chose the right when used in LocationHook.
> > One drawback of this method is that we have many small parts of
> > boundaries, which is bad
> > for tools like BoundaryLister or BoundaryFile2Gpx, but best for
> > LocationHook.
> > I am not sure if it is better to convert each of the tools to handle the
> > quadtree format as well or
> > to add an adaptor which tries to rebuild the original boundary list.
> > I guess the adaptor is the better choice.
> > The other drawback is that the bnd file contains a lot more redundant
> > information. All tags of a level-8 boundary
> > that overlaps multiple quadtree nodes are saved many times, maybe with
> > different mkgmap:intersects_with tags,
> > and for sure with different area info.
> > If you don't mind creating a completely new bnd format, I would not save
> > this redundant info, instead I would
> > save the common tags once, and then all areas, and only the tags for
> > ref-only boundaries.
> >
> > Ciao,
> > Gerd
> >
> >
> >
> >
> > > Date: Mon, 6 Feb 2012 23:11:27 +0100
> > > From: [hidden email]
> > > To: [hidden email]
> > > Subject: Re: [mkgmap-dev] [PATCH V2] boundary preparer with quadtree
> > >
> > > Hi Gerd,
> > >
> > > I need some time to look through your patch. But after a first short
> > > look through I wonder if you tried to handle the balancing act between
> > > keeping the old bnd format and saving your quadtree in an apropriate way.
> > >
> > > Using the boundary lister I think have seen that you save each boundary
> > > but no merged boundary? I see you are saving admin_level=2 and
> > > additionally admin_level=4 and admin_level=6 etc. I expected that one of
> > > your improvements is that you are doing the complete merge step during
> > > preparation so that you save one area (or boundary) with all infos of
> > > admin_level=2,4 and 6.
> > >
> > > Your new mkgmap:boundaryid format mixes multiple information in one tag.
> > > I think it is better to use the mkgmap:boundaryid for the id only and
> > > one or more additional tags for your quadtree information.
> > >
> > > That's just my first impression. I think your idea is exactly right to
> > > move the merge step to the preparer. I am not 100% sure if it is
> > > necessary to save the quadtree node infos. But I am sure you have
> > > compared the performance :-)
> > >
> > > WanMil
> > >
> > > > Hi,
> > > >
> > > > attached is the patch that works on linux systems, no functional
> > change to
> > > > v1.
> > > >
> > > >
> > http://gis.19327.n5.nabble.com/file/n5459686/boundary_prep_quadtree_v2.patch
> > > > boundary_prep_quadtree_v2.patch
> > > >
> > > > Gerd
> > > >
> > > > --
> > > > View this message in context:
> > http://gis.19327.n5.nabble.com/PATCH-V2-boundary-preparer-with-quadtree-tp5459686p5459686.html
> > > > Sent from the Mkgmap Development mailing list archive at Nabble.com.
> > > > _______________________________________________
> > > > mkgmap-dev mailing list
> > > > [hidden email]
> > > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > >
> > > _______________________________________________
> > > mkgmap-dev mailing list
> > > [hidden email]
> > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >
> >
> > _______________________________________________
> > mkgmap-dev mailing list
> > [hidden email]
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

WanMil
Hi Gerd,

> Would you mind dropping the support for the old format ?

No!
Would it be a big deal to implement a converter?

WanMil


_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

osm-8
Am 08.02.2012 18:28, schrieb WanMil:
> Hi Gerd,
>
>> Would you mind dropping the support for the old format ?
> No!
> Would it be a big deal to implement a converter?
Where is the benefit of a converter? I think it would be better to tell
the user, that he should download or create new bounds-files.

Henning

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

Thorsten Kukuk
On Wed, Feb 08, aighes wrote:

> Am 08.02.2012 18:28, schrieb WanMil:
> > Hi Gerd,
> >
> >> Would you mind dropping the support for the old format ?
> > No!
> > Would it be a big deal to implement a converter?
> Where is the benefit of a converter? I think it would be better to tell
> the user, that he should download or create new bounds-files.

I agree, a converter for data you could easily generate new
does not make much sense.
I can always generate new boundary files if needed, I'm only
currently out of disk space on my web server and would need
another webspace provider.

  Thorsten

--
Thorsten Kukuk, Project Manager/Release Manager SLES
SUSE LINUX Products GmbH, Maxfeldstr. 5, D-90409 Nuernberg
GF: Jeff Hawn, Jennifer Guild, Felix Imend├Ârffer, HRB 16746 (AG N├╝rnberg)
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

Gerd Petermann
In reply to this post by WanMil
Hi WanMil,


> Date: Wed, 8 Feb 2012 18:28:32 +0100

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] [PATCH V2] boundary preparer with quadtree
>
> Hi Gerd,
>
> > Would you mind dropping the support for the old format ?
>
> No!
> Would it be a big deal to implement a converter?

It is already implemented in the BoundaryPreparer when you execute its main().
Also, I'll keep the code that writes the old format, because it is used before preparer starts.
I just drop analysing the mkgmap:lies_in tags.

Today I've written the code to read & write the new format and to recombine the boundaries.
There are two open problems:
a) Some boundaries with equal admin levels intersect, and
BoundaryQuadtree.merge()  removes the intersection from one of the both.
This can cause different results compared to trunk because the LocationHook in trunk can sort
them in different order. I think one cannot expect correct results for this case, but it makes
testing difficult.

b) The recombined boundaries have a few small holes, probably again the rounding error.
I'll check this tomorrow.

ciao,
Gerd

>
> WanMil
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

WanMil
In reply to this post by osm-8
> Am 08.02.2012 18:28, schrieb WanMil:
>> Hi Gerd,
>>
>>> Would you mind dropping the support for the old format ?
>> No!
>> Would it be a big deal to implement a converter?
> Where is the benefit of a converter? I think it would be better to tell
> the user, that he should download or create new bounds-files.
>
> Henning
>

If you ask me: throw away the old stuff. But I expect that some people
will complain ("I have precompiled bounds with perfect data. I want to
continue using it...")). So if it is *easy* to implement there is
nothing wrong with providing a converter.

Bye the way: On April 1st the licence changes and I expect that there
will be some gaps in the boundaries afterwards.

WanMil

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

WanMil
In reply to this post by Gerd Petermann
> Hi WanMil,
>
>
>  > Date: Wed, 8 Feb 2012 18:28:32 +0100
>  > From: [hidden email]
>  > To: [hidden email]
>  > Subject: Re: [mkgmap-dev] [PATCH V2] boundary preparer with quadtree
>  >
>  > Hi Gerd,
>  >
>  > > Would you mind dropping the support for the old format ?
>  >
>  > No!
>  > Would it be a big deal to implement a converter?
>
> It is already implemented in the BoundaryPreparer when you execute its
> main().
> Also, I'll keep the code that writes the old format, because it is used
> before preparer starts.
> I just drop analysing the mkgmap:lies_in tags.
>
> Today I've written the code to read & write the new format and to
> recombine the boundaries.
> There are two open problems:
> a) Some boundaries with equal admin levels intersect, and
> BoundaryQuadtree.merge() removes the intersection from one of the both.
> This can cause different results compared to trunk because the
> LocationHook in trunk can sort
> them in different order. I think one cannot expect correct results for
> this case, but it makes
> testing difficult.

Is it possible to create a rule which boundary is preferred (e.g. with
lower id)?

>
> b) The recombined boundaries have a few small holes, probably again the
> rounding error.
> I'll check this tomorrow.
>
> ciao,
> Gerd
>
>  >
>  > WanMil
>  >
>  >
>  > _______________________________________________
>  > mkgmap-dev mailing list
>  > [hidden email]
>  > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

osm-8
In reply to this post by WanMil
Am 08.02.2012 19:05, schrieb WanMil:
>> Where is the benefit of a converter? I think it would be better to tell
>> the user, that he should download or create new bounds-files.
>>
>> Henning
>>
> If you ask me: throw away the old stuff. But I expect that some people
> will complain ("I have precompiled bounds with perfect data. I want to
> continue using it...")). So if it is *easy* to implement there is
> nothing wrong with providing a converter.
Ok, you're right.

> Bye the way: On April 1st the licence changes and I expect that there
> will be some gaps in the boundaries afterwards.
Are there some official statements about the map-license after
license-change? Will it be a produced work or a database? How about your
boundary-files? So if maps will be a produced work, than we could use
old boundary-files until they were remapped.

Henning

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH V2] boundary preparer with quadtree

Gerd Petermann
In reply to this post by WanMil
Hi WanMil,

> > Today I've written the code to read & write the new format and to
> > recombine the boundaries.

> > There are two open problems:
> > a) Some boundaries with equal admin levels intersect, and
> > BoundaryQuadtree.merge() removes the intersection from one of the both.
> > This can cause different results compared to trunk because the
> > LocationHook in trunk can sort
> > them in different order. I think one cannot expect correct results for
> > this case, but it makes
> > testing difficult.
>
> Is it possible to create a rule which boundary is preferred (e.g. with
> lower id)?
>

Yes, that sounds like a good idea. I am not yet sure at what places the locator
may be involved in this. Something else for tomorrow ,-)

Gerd




_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev