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

Wed Apr 7 12:02:33 BST 2021

Hi Gerd

Problem is that IdentityHashMap is the ideal solution, but ordering
behaviour depends on internal java object handles. A solution to this
stability issue would be to rotate joinedWays.originalWays so, say, the
one with the lowest ID is first, doing this just before the full point
-list is created. 

Maybe not worth it if existing logic is not a problem.

Some of the other advantages my logic:

  Clearer and more efficient.

  Elements are scanned once; cOg and closed polygons are processed
  immediately. Elements from SeaGenerator are all closed.

  Single touching polygons are handled without difficulty;
  just part of the way the algo is expressed.

  Maintaining jw.inner/outerCount gives clarity to this issue.
  Can be used for error reporting and behavioral definition.
  If the roles are not to be trusted, the counts can be adjusted when
  the geometry is determined.

Ticker

On Wed, 2021-04-07 at 08:57 +0000, Gerd Petermann wrote:
> 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