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

Thu Apr 29 11:21:12 BST 2021

Hi Gerd

I'm away at moment, without full access to sources, so can't follow the
current progress with partitioning, etc.

Regarding finding a point IN (and not ON) polygon:
1/ Try bounds center.
2/ Assumed determined [counter-]clockwise from area calculation.
   Pick 3 sequential points, bisect the angle and go in along this
   line by a small multiple of IsInUtil.EPS[_HP] and try this point.
3/ Move around by one and try again.
4/ If get back to the start, the polygon must be so thin that cannot
   contain another polygon.
   Take any Point and hope that this isn't ON more than possible outer

Ticker

On Thu, 2021-04-29 at 08:31 +0000, Gerd Petermann wrote:
> Hi Ticker,
> 
> I did a few tests with a tile in Zambia that contains some complex
> multipolygons and nestings. No
> 1) disable partitioning
> 2) disable partitioning and skip isLineInShape() test if center of
> geometry of the inner is IN for inner AND outer
> 3) use code in branch as is (enabled partitioning)
> 4) enable partitioning  and skip isLineInShape() test if center of
> geometry of the inner is IN for inner AND outer
> 
> Times for the compilation of the tile are
> 39 secs for 1)
> 32 secs for 2)
> 4 secs for 3) and 4)
> 
> With 3) and 4) I see only ~2 secs for the "processing MP relation"
> part, so it would require more complex relations to see improvements
> with 4)
> 
> If you know a quick and stable and simple method to find a point that
> is IN please let me know and I do some more testing. The getCofG()
> only works well for convex polygons. For around 3 percent of the
> polygons in my tests getCofG() returns a point outside of the
> polygon, and those polygons are likely more complex.
> 
> I've also done some tests with PrecompSeaGenerator and the complex
> tile sea_2752512_851968.osm.pbf
> Results are more or less equal for all 4 methods, the processing of
> the generated MP takes ~20 secs, only ~2 secs are used in
> createContainsMatrix() and ~18 secs are used in MultipolygonCutter
> 
> At the moment I try to decide what to do with incomplete data. I see
> three different situations with incomplete relations:
> 1) BoundaryPreprocessor is used with a country extract or maybe the
> combination of multiple extracts from geofabrik or other sources.
> In this case I tend to think that we can either ignore incomplete
> data completely or we might use the *.poly file(s) that were used to
> cut the data to "close the boundary polygon along the cutting
> polygon". The latter might help to avoid situations where the
> LocationHook returns no info for points outside of the cutting
> polygon.
> 2) mkgmap is used with splitter data and splitter was used with -
> -keep-complete=false
> In this case lots of multipolygons are incomplete, esp. those near
> the tile boundary. We MUST do some guessing about the missing data,
> else the maps are more or less unusable because large wood or lake
> areas wood be missing.
> 3) mkgmap is used with splitter data and splitter was used with -
> -keep-complete=true
> In this case we see incomplete MP when the country extract was
> already incomplete or with those MP that splitter doesn't keep
> complete.
> It's hard to say if we can ignore those incomplete MP or not. Most of
> them are boundaries. The default style doesn't render any boundary as
> polygon, but other styles do, e.g. the OpenFietsMap styles.
> 
> Maybe a simple new option "--ignore-incomplete-data" could improve
> performance. This would be easy to implement. A much more complex
> solution would be a new hook that is called directly before the
> processElements() call. It would use a new rule file similar to
> relations and could set special tags to tell mkgmap if it should
> calculate the areas of the multipolygon or just handle the outlines
> to produce the mkgmap:stylefilter=polyline ways.
> Just an idea so far.
> 
> The current code only tries to use the "tile boundary" to complete
> data. I think it would be better to use the cutting polygon. I
> started to experiment with that but found out that many *.poly files
> from geofabrik intersect with the country borders which are expected
> to be fully inside. I contacted them about this and Frederick Ramm
> confirmed that they want to fix that.
> 
> ciao,
> Gerd