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

Mon Apr 26 15:17:26 BST 2021

Hi Ticker,

I think I am making progress with my divide&conquer approach. I see ~20 secs instead of more than 7 minutes to process the monster relation r9488835.
The basic approach is to use ShapeSplitter.splitShape() multiple times to divide the multipolygon into smaller pieces where no ring has more than 20.000 nodes and executing the block

analyseRelationRoles()
...
doReporting()
for each piece.

The work is not yet done, the output file is a bit larger, not yet sure why, and the calculation of the "largestOuterPolygon" neads a bit more work.
There are probably edge cases where this doesn't work, esp. when inners are very large.

BTW: I found a bug in IsInUtil.isLineInShape() : It sometimes returns ON when it should return IN/ON
I think it happens when a ring has start /end node ON and also 2nd or 2nd-last node ON.
Probably a special case created by the ShapeSplitter. Attached patch fixes the problem in IsInUtil.

Gerd

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

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

_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: start-and-stop-on-line.patch
Type: application/octet-stream
Size: 836 bytes
Desc: start-and-stop-on-line.patch
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20210426/6ea3565a/attachment.obj>