Re: [mkgmap-dev] new splitter branch solve-parallel

[Gerd Petermann]

Hi Ticker,

yes, I think splitter implements something like that.
A a start we have a grid with a given resolution and a single rectangle that 
covers (part of) this grid. Several criteria tell us if this "tile" has to be 
split or not.
A split can be horizontal or vertical, but only where the grid is. A simple 
straightforward approach is to always split in the middle, but that will 
produce (almost) empty areas in the sea or in deserts.  Therefore other splits 
have to be tested.  Goal is to find a good split in a reasonable time.
One problem: It is not clear if a valid solution exists  unless one is found.

Gerd


Von: mkgmap-dev  im Auftrag von Ticker 
Berkin 
Gesendet: Donnerstag, 1. Juli 2021 10:54
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] new splitter branch solve-parallel

Hi Gerd

Is this of any relevance -

https://en.wikipedia.org/wiki/Branch_and_bound

Ticker

On Wed, 2021-06-30 at 16:08 +, Gerd Petermann wrote:
> Hi all,
>
> I've started this branch to further improve the split results.
> Splitter has two different algorithms to find good splits.
> 1) Algo FULL tries first to split in the middle and then continues
> with the next positions (mid+1, mid-1, mid+2, mid-2, ...)
> The resulting parts are split again recursively. This should find the
> best possible split but can take very long when the only good split
> starts far from the middle.
>
> 2) Algo SOME uses some heuristics to test only some of the possible
> splits. This is typically much faster but sometimes doesn't find any
> solution and sometimes the FULL algo finds a better solution.
>
> The trunk version tries first the one that is more promising and - if
> that fails to find a good split - tries the other. So, sometimes the
> FULL algo works for 2 minutes and then SOME finds a good result in a
> few seconds.
>
> This branch executes both algorithms in parallel and uses the better
> result.
>
> One of the open problems is to decide under what conditions the
> execution should stop.
> If the SOME algo finds a good solution within 20 secs should we still
> continue the FULL algo to find the best solution? If yes, how long?
> I'm playing with this, any input is welcome.
>
> Gerd
> ___
> mkgmap-dev mailing list
> mkgmap-dev@lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Re: [mkgmap-dev] new splitter branch solve-parallel

[Felix Hartmann]

Hi Gerd,
well setting initial search limit to 100 solves already loads of bad
solutions and is still quite fast. Albeit using v 408 it was the best
universal value I felt. Not much slower but in many cases getting better
results. Going for much bigger initial value actually then caused also
worse splits. I do not know how right now it determines the max value. but
maybe increasing it would be good. And I feel it should increase/wait if
the split obviously is not good. If it is good (all tiles except one within
80% of maxnodes) or very good (all except one 85%) it could stop earlier in
order not to waste resources.
I do not know how easy such a solution is to be implemented however. So far
most bad splits are really realy bad (e.g. Norway 210 vs 135 tiles - in
such cases a much longer time taken to find a good split is reasonable.
Also as mkgmap will run faster if the split is better, compressing the maps
will produce a smaller overall size if the split is better.

On Thu, 1 Jul 2021 at 11:54, Ticker Berkin  wrote:

> Hi Gerd
>
> Is this of any relevance -
>
> https://en.wikipedia.org/wiki/Branch_and_bound
>
> Ticker
>
> On Wed, 2021-06-30 at 16:08 +, Gerd Petermann wrote:
> > Hi all,
> >
> > I've started this branch to further improve the split results.
> > Splitter has two different algorithms to find good splits.
> > 1) Algo FULL tries first to split in the middle and then continues
> > with the next positions (mid+1, mid-1, mid+2, mid-2, ...)
> > The resulting parts are split again recursively. This should find the
> > best possible split but can take very long when the only good split
> > starts far from the middle.
> >
> > 2) Algo SOME uses some heuristics to test only some of the possible
> > splits. This is typically much faster but sometimes doesn't find any
> > solution and sometimes the FULL algo finds a better solution.
> >
> > The trunk version tries first the one that is more promising and - if
> > that fails to find a good split - tries the other. So, sometimes the
> > FULL algo works for 2 minutes and then SOME finds a good result in a
> > few seconds.
> >
> > This branch executes both algorithms in parallel and uses the better
> > result.
> >
> > One of the open problems is to decide under what conditions the
> > execution should stop.
> > If the SOME algo finds a good solution within 20 secs should we still
> > continue the FULL algo to find the best solution? If yes, how long?
> > I'm playing with this, any input is welcome.
> >
> > Gerd
> > ___
> > mkgmap-dev mailing list
> > mkgmap-dev@lists.mkgmap.org.uk
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> ___
> mkgmap-dev mailing list
> mkgmap-dev@lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>


-- 
Felix Hartman - Openmtbmap.org & VeloMap.org
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Re: [mkgmap-dev] new splitter branch solve-parallel

[Ticker Berkin]

Hi Gerd

Is this of any relevance -

https://en.wikipedia.org/wiki/Branch_and_bound

Ticker

On Wed, 2021-06-30 at 16:08 +, Gerd Petermann wrote:
> Hi all,
> 
> I've started this branch to further improve the split results. 
> Splitter has two different algorithms to find good splits. 
> 1) Algo FULL tries first to split in the middle and then continues
> with the next positions (mid+1, mid-1, mid+2, mid-2, ...) 
> The resulting parts are split again recursively. This should find the
> best possible split but can take very long when the only good split
> starts far from the middle. 
> 
> 2) Algo SOME uses some heuristics to test only some of the possible
> splits. This is typically much faster but sometimes doesn't find any
> solution and sometimes the FULL algo finds a better solution. 
> 
> The trunk version tries first the one that is more promising and - if
> that fails to find a good split - tries the other. So, sometimes the
> FULL algo works for 2 minutes and then SOME finds a good result in a
> few seconds.
> 
> This branch executes both algorithms in parallel and uses the better
> result. 
> 
> One of the open problems is to decide under what conditions the
> execution should stop.
> If the SOME algo finds a good solution within 20 secs should we still
> continue the FULL algo to find the best solution? If yes, how long?
> I'm playing with this, any input is welcome.
> 
> Gerd
> ___
> mkgmap-dev mailing list
> mkgmap-dev@lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Re: [mkgmap-dev] new splitter branch solve-parallel

[Gerd Petermann]

Hi Felix,

yes, sounds reasonable to wait a while if result is not very good. In some 
cases both algos don't find a good solution, e.g. norway with polygon-file, 
search-limit=100 and --max-nodes=120 seems to be stressing, it results 
in 210 tiles. With search-limit 10 mio it finds a good split with 135 tiles.

Maybe I should simply use a much higher initial search-limit and implement an 
option to set the maximum time for the search.

Gerd


Von: mkgmap-dev  im Auftrag von Felix 
Hartmann 
Gesendet: Mittwoch, 30. Juni 2021 21:21
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] new splitter branch solve-parallel

I feel of all tiles are 85 percent of max then stop. If 5percent of tiles are 
less the 75 percent max then maybe stop after 30 seconds. If more then 10 
percent AND more then 10 tiles are less then 75 percent continue.

On Wed, 30 Jun 2021, 19:09 Gerd Petermann 
mailto:gpetermann_muenc...@hotmail.com>> wrote:
Hi all,

I've started this branch to further improve the split results.
Splitter has two different algorithms to find good splits.
1) Algo FULL tries first to split in the middle and then continues with the 
next positions (mid+1, mid-1, mid+2, mid-2, ...)
The resulting parts are split again recursively. This should find the best 
possible split but can take very long when the only good split starts far from 
the middle.

2) Algo SOME uses some heuristics to test only some of the possible splits. 
This is typically much faster but sometimes doesn't find any solution and 
sometimes the FULL algo finds a better solution.

The trunk version tries first the one that is more promising and - if that 
fails to find a good split - tries the other. So, sometimes the FULL algo works 
for 2 minutes and then SOME finds a good result in a few seconds.

This branch executes both algorithms in parallel and uses the better result.

One of the open problems is to decide under what conditions the execution 
should stop.
If the SOME algo finds a good solution within 20 secs should we still continue 
the FULL algo to find the best solution? If yes, how long?
I'm playing with this, any input is welcome.

Gerd
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Re: [mkgmap-dev] splitter r609 released

[Gerd Petermann]

Hi Felix,

the poly file for South America contains few points (< 40). I think splitter 
switched into the mode which tries hard to fit tiles into the polygon.
If you post a link to the corresponding densities-out.txt and log I can tell 
you more details.

Gerd


Von: mkgmap-dev  im Auftrag von Felix 
Hartmann 
Gesendet: Donnerstag, 1. Juli 2021 09:58
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] splitter r609 released

Well here are the results for 615:
If you would like the log files for any of those runs - tell me. Significantly 
better with polygon file are Norway, Russia, Australia-Oceania and Asia. This 
version has much less problem countries like 614. It would be too big to attach 
all of them here. If you like all of them then I can upload them to my server.

South America is really bad using polygon-file.

"for netherlands use polygon-file - cnt1 = 89 cnt0 = 88"
"for great-britain use polygon-file - cnt1 = 111 cnt0 = 110"
"for germany use polygon-file - cnt1 = 258 cnt0 = 257"
"for liechtenstein do not use polygon-file - cnt1 = 1 cnt0 = 6"
"for monaco do not use polygon-file - cnt1 = 1 cnt0 = 2"
"for slovenia do not use polygon-file - cnt1 = 27 cnt0 = 28"
"for ukraine use polygon-file - cnt1 = 62 cnt0 = 61"
"for norway use polygon-file - cnt1 = 129 cnt0 = 119"
"for switzerland do not use polygon-file - cnt1 = 29 cnt0 = 30"
"for poland use polygon-file - cnt1 = 132 cnt0 = 128"
"for sweden use polygon-file - cnt1 = 60 cnt0 = 54"
"for finland do not use polygon-file - cnt1 = 65 cnt0 = 84"
"for denmark use polygon-file - cnt1 = 33 cnt0 = 32"
"for andorra do not use polygon-file - cnt1 = 1 cnt0 = 4"
"for estonia use polygon-file - cnt1 = 9 cnt0 = 8"
"for saarland do not use polygon-file - cnt1 = 4 cnt0 = 17"
"for hamburg do not use polygon-file - cnt1 = 3 cnt0 = 12"
"for hessen do not use polygon-file - cnt1 = 17 cnt0 = 18"
"for bayern do not use polygon-file - cnt1 = 47 cnt0 = 48"
"for berlin do not use polygon-file - cnt1 = 5 cnt0 = 13"
"for australia-oceania use polygon-file - cnt1 = 131 cnt0 = 109"
"for south-america do not use polygon-file - cnt1 = 334 cnt0 = 463"
"for africa use polygon-file - cnt1 = 665 cnt0 = 663"
"for asia use polygon-file - cnt1 = 1592 cnt0 = 1549"
"for russia use polygon-file - cnt1 = 426 cnt0 = 408"
"for central-america use polygon-file - cnt1 = 61 cnt0 = 58"
"for morocco do not use polygon-file - cnt1 = 19 cnt0 = 27"
"for tanzania use polygon-file - cnt1 = 75 cnt0 = 74"
"for mozambique use polygon-file - cnt1 = 24 cnt0 = 23"
"for azerbaijan do not use polygon-file - cnt1 = 3 cnt0 = 4"
"for iran use polygon-file - cnt1 = 16 cnt0 = 15"
"for malaysia-singapore-brunei do not use polygon-file - cnt1 = 16 cnt0 = 17"
"for china use polygon-file - cnt1 = 106 cnt0 = 101"
"for india do not use polygon-file - cnt1 = 109 cnt0 = 112"
"for indonesia do not use polygon-file - cnt1 = 191 cnt0 = 200"
"for philippines use polygon-file - cnt1 = 52 cnt0 = 51"
"for afghanistan do not use polygon-file - cnt1 = 11 cnt0 = 20"
"for australia use polygon-file - cnt1 = 67 cnt0 = 66"
"for argentina use polygon-file - cnt1 = 32 cnt0 = 27"
"for brazil use polygon-file - cnt1 = 177 cnt0 = 172"
"for chile do not use polygon-file - cnt1 = 31 cnt0 = 33"
"for paraguay use polygon-file - cnt1 = 17 cnt0 = 16"
"for canada use polygon-file - cnt1 = 274 cnt0 = 272"
"for us-northeast do not use polygon-file - cnt1 = 109 cnt0 = 110"
"for us-pacific use polygon-file - cnt1 = 21 cnt0 = 18"
"for us-south use polygon-file - cnt1 = 262 cnt0 = 261"
"for us-west use polygon-file - cnt1 = 229 cnt0 = 227"
"for greenland use polygon-file - cnt1 = 4 cnt0 = 2"
"for mexico use polygon-file - cnt1 = 44 cnt0 = 42"
"for reunion do not use polygon-file - cnt1 = 3 cnt0 = 5"

On Wed, 30 Jun 2021 at 12:30, Gerd Petermann 
mailto:gpetermann_muenc...@hotmail.com>> wrote:
Hi Felix,

I've released r615 to fix the problems with Saarland (now 17 tiles with polygon 
instead of crash, 4 tiles without) and Norway (121 with polygon, 128 without)
Numbers for max-nodes=140

Gerd



Von: mkgmap-dev 
mailto:mkgmap-dev-boun...@lists.mkgmap.org.uk>>
 im Auftrag von Felix Hartmann 
mailto:extremecar...@gmail.com>>
Gesendet: Mittwoch, 30. Juni 2021 10:52
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] splitter r609 released

well yeah by now my list is down to very few countries (different then with 
older splitter.jar) that profit from --polygon-file.
I feel like I will only use polygon-file for Asia continent map and for Russia 
- they fit your description of spanning over 180° and needing polygon-file to 
be split into less tiles. They pretty consistently split better with 
polygon-file on several splitter versions.

Then maybe retest a year later.

On Wed, 30 Jun 2021 at 11:25, Gerd Petermann 
mailto:gpetermann_muenc...@hotmail.com>>>
 wrote:
Hi Felix,

sure, it's n

[mkgmap-dev] Commit r4800: improve unit test

[svn commit]

Version mkgmap-r4800 was committed by gerd on Thu, 01 Jul 2021

improve unit test
- fix more deprecation warnings from jdk 11
- fix order of expected/actual parameters


http://www.mkgmap.org.uk/websvn/revision.php?repname=mkgmap&rev=4800
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Re: [mkgmap-dev] splitter r609 released

[Felix Hartmann]

Well here are the results for 615:
If you would like the log files for any of those runs - tell me.
Significantly better with polygon file are Norway, Russia,
Australia-Oceania and Asia. This version has much less problem countries
like 614. It would be too big to attach all of them here. If you like all
of them then I can upload them to my server.

South America is really bad using polygon-file.

"for netherlands use polygon-file - cnt1 = 89 cnt0 = 88"
"for great-britain use polygon-file - cnt1 = 111 cnt0 = 110"
"for germany use polygon-file - cnt1 = 258 cnt0 = 257"
"for liechtenstein do not use polygon-file - cnt1 = 1 cnt0 = 6"
"for monaco do not use polygon-file - cnt1 = 1 cnt0 = 2"
"for slovenia do not use polygon-file - cnt1 = 27 cnt0 = 28"
"for ukraine use polygon-file - cnt1 = 62 cnt0 = 61"
*"for norway use polygon-file - cnt1 = 129 cnt0 = 119" *
"for switzerland do not use polygon-file - cnt1 = 29 cnt0 = 30"
"for poland use polygon-file - cnt1 = 132 cnt0 = 128"
"for sweden use polygon-file - cnt1 = 60 cnt0 = 54"
"for finland do not use polygon-file - cnt1 = 65 cnt0 = 84"
"for denmark use polygon-file - cnt1 = 33 cnt0 = 32"
"for andorra do not use polygon-file - cnt1 = 1 cnt0 = 4"
"for estonia use polygon-file - cnt1 = 9 cnt0 = 8"
"for saarland do not use polygon-file - cnt1 = 4 cnt0 = 17"
"for hamburg do not use polygon-file - cnt1 = 3 cnt0 = 12"
"for hessen do not use polygon-file - cnt1 = 17 cnt0 = 18"
"for bayern do not use polygon-file - cnt1 = 47 cnt0 = 48"
"for berlin do not use polygon-file - cnt1 = 5 cnt0 = 13"
*"for australia-oceania use polygon-file - cnt1 = 131 cnt0 = 109" *
"for south-america do not use polygon-file - cnt1 = 334 cnt0 = 463"
"for africa use polygon-file - cnt1 = 665 cnt0 = 663"
*"for asia use polygon-file - cnt1 = 1592 cnt0 = 1549" *
*"for russia use polygon-file - cnt1 = 426 cnt0 = 408" *
"for central-america use polygon-file - cnt1 = 61 cnt0 = 58"
"for morocco do not use polygon-file - cnt1 = 19 cnt0 = 27"
"for tanzania use polygon-file - cnt1 = 75 cnt0 = 74"
"for mozambique use polygon-file - cnt1 = 24 cnt0 = 23"
"for azerbaijan do not use polygon-file - cnt1 = 3 cnt0 = 4"
"for iran use polygon-file - cnt1 = 16 cnt0 = 15"
"for malaysia-singapore-brunei do not use polygon-file - cnt1 = 16 cnt0 =
17"
"for china use polygon-file - cnt1 = 106 cnt0 = 101"
"for india do not use polygon-file - cnt1 = 109 cnt0 = 112"
"for indonesia do not use polygon-file - cnt1 = 191 cnt0 = 200"
"for philippines use polygon-file - cnt1 = 52 cnt0 = 51"
"for afghanistan do not use polygon-file - cnt1 = 11 cnt0 = 20"
"for australia use polygon-file - cnt1 = 67 cnt0 = 66"
"for argentina use polygon-file - cnt1 = 32 cnt0 = 27"
"for brazil use polygon-file - cnt1 = 177 cnt0 = 172"
"for chile do not use polygon-file - cnt1 = 31 cnt0 = 33"
"for paraguay use polygon-file - cnt1 = 17 cnt0 = 16"
"for canada use polygon-file - cnt1 = 274 cnt0 = 272"
"for us-northeast do not use polygon-file - cnt1 = 109 cnt0 = 110"
"for us-pacific use polygon-file - cnt1 = 21 cnt0 = 18"
"for us-south use polygon-file - cnt1 = 262 cnt0 = 261"
"for us-west use polygon-file - cnt1 = 229 cnt0 = 227"
"for greenland use polygon-file - cnt1 = 4 cnt0 = 2"
"for mexico use polygon-file - cnt1 = 44 cnt0 = 42"
"for reunion do not use polygon-file - cnt1 = 3 cnt0 = 5"

On Wed, 30 Jun 2021 at 12:30, Gerd Petermann <
gpetermann_muenc...@hotmail.com> wrote:

> Hi Felix,
>
> I've released r615 to fix the problems with Saarland (now 17 tiles with
> polygon instead of crash, 4 tiles without) and Norway (121 with polygon,
> 128 without)
> Numbers for max-nodes=140
>
> Gerd
>
>
> 
> Von: mkgmap-dev  im Auftrag von
> Felix Hartmann 
> Gesendet: Mittwoch, 30. Juni 2021 10:52
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] splitter r609 released
>
> well yeah by now my list is down to very few countries (different then
> with older splitter.jar) that profit from --polygon-file.
> I feel like I will only use polygon-file for Asia continent map and for
> Russia - they fit your description of spanning over 180° and needing
> polygon-file to be split into less tiles. They pretty consistently split
> better with polygon-file on several splitter versions.
>
> Then maybe retest a year later.
>
> On Wed, 30 Jun 2021 at 11:25, Gerd Petermann <
> gpetermann_muenc...@hotmail.com>
> wrote:
> Hi Felix,
>
> sure, it's not good if splitter fails to split correct data. Still, an
> automated process should check the return code of the program. If splitter
> returns a values !=  0 you can be sure that something is wrong (same with
> mkgmap)
>
> It's okay to split small files like Liechtenstein, no problem with that.
> Just don't expect to always get fewer tiles when you use a polygon-file ;)
>
> Gerd
>
> 
> Von: mkgmap-dev  mkgmap-dev-boun...@lists.mkgmap.org.uk>> im Auftrag von Felix Hartmann <
> extremecar...@gmail.com

[mkgmap-dev] Commit r4799: add missing copyright info to extracted class

[svn commit]

Version mkgmap-r4799 was committed by gerd on Thu, 01 Jul 2021

add missing copyright info to extracted class

http://www.mkgmap.org.uk/websvn/revision.php?repname=mkgmap&rev=4799
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

[mkgmap-dev] Commit r4798: - add Xlint to all compile targets

[svn commit]

Version mkgmap-r4798 was committed by gerd on Thu, 01 Jul 2021

- add Xlint to all compile targets
- fix various warnings and deprecations

http://www.mkgmap.org.uk/websvn/revision.php?repname=mkgmap&rev=4798
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Re: [mkgmap-dev] r4793 fails to build (error: reference to forEach is ambiguous)

[Gerd Petermann]

Hi Bas,

thanks, I've changed a few things according to the log. I don't see these 
messages when I compile with OpenJDK 11, but my version is quite old: openjdk 
version "11.0.1" 2018-10-16
I still have to find out how to replace the newInstance() calls.

Gerd


Von: mkgmap-dev  im Auftrag von 
Sebastiaan Couwenberg 
Gesendet: Donnerstag, 1. Juli 2021 07:17
An: mkgmap-dev@lists.mkgmap.org.uk
Betreff: [mkgmap-dev] r4793 fails to build (error: reference to forEach is  
ambiguous)

The Debian package build for SVN r4793 fails to build:

[javac]
/build/mkgmap-0.0.0+svn4793/src/uk/me/parabola/mkgmap/filters/ShapeMergeFilter.java:230:
error: reference to forEach is ambiguous
[javac] byCenter.forEach(i ->
centers.put(i, Area.getBBox(similarShapes.get(i).points).getCenter()));
[javac] ^
[javac]   both method forEach(IntConsumer) in IntIterable and method
forEach(Consumer) in IntIterable match

The full buildlog is attached.

Kind Regards,

Bas

--
 GPG Key ID: 4096R/6750F10AE88D4AF1
Fingerprint: 8182 DE41 7056 408D 6146  50D1 6750 F10A E88D 4AF1
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev