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

Tue Apr 27 17:09:52 BST 2021

Hi Gerd

Point IN and area should be adequate for determining enclosed/enclosing
polygons relationships. Overlapping / intersecting is an error anyway,
but, even with badly/arbitrarily closed boundaries, provided the
closing takes a similar route around the known mapArea, the area shouldsuffice.

Ticker

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