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

Tue Apr 27 15:23:57 BST 2021

Hi Ticker,

I don't care much about invalid MP so far. It is not allowed that inner ways and outer ways are connected, nor is it allowed that outer rings share segments.
So, at the moment that means Garbage in -> Garbage out.
There are some special cases more than two outer ways are connected at the same node and there should be a back-tracking algo to combine them in a ways that doesn't produce self intersecting rings. No idea how to implement that.

reg. containsMatrix: I did not find any problems with nested polygons so far, but yes, the partitioning is more likely to produce more edge cases.

I don't see how a single call of isPointInShape() can be enough. It only helps if it returns OUT, but that is unlikely. If it returns IN the polygons may still be overlapping. I've not yet decided what to do with those MP because the real MP with complete data might be correct and the overlapping could be a result of artifically closed rings.

I've just noticed that the branch is sometimes erronously connecting ways which trunk doesn't connect (only with BoundaryRelation).

I think it will take a one or two more weeks before this branch is getting stable.

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, 27. April 2021 15:37
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] tile takes very long time to generate

Hi Gerd

I'd have thought using isPointInShape() in combination with polygon
areas to be more efficient and robust than isLineInShape() (which makes
multiple calls to isPointInShape). Would need to choose a reference
point within each polygon, ensuring it is IN but not ON itself.

Probably splitShape(), isPointInShape() and
calcAreaSize()/calcAreaSizeTestVal() all have very similar costs;
linear on number of points.

I understand some benefits of splitting a massive outer into multiples
polygons, in that a point-IN question might give an quicker answer, but
it must introduce a lot of other difficulties with edge cases on the
artificial boundaries, etc, etc. Splitting inners shouldn't cause a
probem in this respect (just a list of inners), but if there is another
outer in the hole, this will become confusing.

A couple of other things I meant to mention following earlier faster-mp
svn updates:

I found cases, as both inner and outer, where adjacent rectangles (eg
buildings) are touched together, with either a duplicate or identical
member being the dividing wall. I realise that some combinations of
this violate OSM MP rules, but, keeping the duplicate, allows this
simple "double-touching" structure to be resolved; where there are 4
ways at a node, don't join 2 that are identical or have same other-end
and no other points.

Joining ways if possible in the initial element iteration and ignoring
roles can lead to problems when inner and outer touch. Whereas saving
them all in a Map of both ends, before attempting to join, will avoid
the problem for single-touching. For double-touching, any roles can be
used to join the correct parts. For ordering stability if using a
HashMap, could just keep track of lowest element# in joinedWays and
always keep this first.

Ticker

On Mon, 2021-04-26 at 14:17 +0000, Gerd Petermann wrote:
> 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
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev