[mkgmap-dev] tile takes very long time to generate

Wed Apr 7 09:57:13 BST 2021

Hi Ticker,

reg. mpInitialLogic.patch: I think I tried the same approach to join the ways in the past. Problem is that the patched code produces rings with an unpredictable start/end and thus random content in RGN. This makes comparisons of two mkgmap outputs much more difficult if not impossable.

The existing algo works quite well if the members are sorted and most complex MP are sorted well enough. I think in the worst case (badly shuffled member list) the algo complexity is probably O(n²) , in the best case it is O(n) where n gives the number of unclosed ways in the member list.

Maybe you find a way to use the HashMap to avoid the sequential search for the next member without adding too much complexity to the current code?
Or a simple sort to avoid the worst case?
Even with worse cases I don't see more than a few seconds for very complex MP.

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at hotmail.com>
Gesendet: Dienstag, 6. April 2021 13:06
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] tile takes very long time to generate

Hi Ticker,

no need for another patch at the moment. I just try to make up my mind at what places the role info should/must be used and while looking at your code I wondered how it would work.

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
Gesendet: Dienstag, 6. April 2021 12:59
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] tile takes very long time to generate

Hi Gerd

One of the ideas of the code is that it doesn't keep reversing all the
points as it gets to joining the ways to make a polygon. Once all the
ways have been gathered, then another stage is needed adds the points
from JoinedWay.originalWay to .points the correct order, removing the
intermediate joining points, etc.

Another part that's missing is what to do with unclosed ways, and here
I guess it can take a similar line to the existing logic.

I can do another patch, based on faster_mp branch - for real - if you
think this change is worth while.

Ticker

On Tue, 2021-04-06 at 10:45 +0000, Gerd Petermann wrote:
> Hi Ticker,
>
> I tried to use your patch mpInitialLogic.patch.
> It is missing the code to update the field Way.points, means, the
> final polygons only contain the points of one way.
>
> Not sure how you used that code?
>
> Gerd
>
> ________________________________________
> Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
> Gesendet: Montag, 15. März 2021 17:15
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] tile takes very long time to generate
>
> Hi Gerd
>
> You might consider the some of the ideas here as improvements to the
> initial parts of MP processing.
>
> This is a patch based on trunk rather than the new branch. It isn't
> structured as for final usage, rather for minimising the spread of
> changes, working in parallel with the existing code so I could see if
> found the same MP problems as the existing code and having clearly
> identifiable diagnostics in the log file.
>
> Ticker
> _______________________________________________
> 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
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev