Hi Gerd Using your split of germany, 63240135.osm.pbf gives me the problem after I converted PolygonSplitterBase and AreaClipper to the new algo It is the outer way of relation/27312 at 48.94071,13.70245 At highest resolution, openStreetMap shows no intersection, but when I dump the highRes points after the split complains and plot them it shows an overlap. Ticker On Wed, 2017-01-25 at 14:29 +0000, Gerd Petermann wrote:

Hi Ticker,

do you have an example for such a problem case?

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 25. Januar 2017 13:25:34 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

Yes - please

I started looking at MultiPolygonRelation yesterday with a view of trying to convert it to use the new ShapeSplitter algorithm.

I think that the way a self-intersecting polygon is rewritten after a split using the Java2D library causes problems for the new algorithm when it makes a later cut for points limits or subdivisions, even when the next cut isn't in the overlapped area.

All I've done so far is convert a few more places to use highPrec logic and then slightly disparaging at the complexity of the whole thing.

Ticker

On Wed, 2017-01-25 at 09:05 +0000, Gerd Petermann wrote:

...

Hi all,

I'd like to rewrite the code in MultiPolygonRelation so that it tolerates more mp-rels. For example, the relation http://www.openstreetmap.org/relation/2199651 produces these warnings: WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: Some polygons are intersecting. This is not allowed in multipolygons. WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: - http://www.openstreetmap.org/way/165084794 WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: - http://www.openstreetmap.org/way/165084810 WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: Polygon 4611686018427387906(8P)(165084810[8P]) carries role inner but is not inside any other polygon. Potentially it does not belong to this multipolygon. The inner way touches the outer way in one point. My understanding is that this is correct, mkgmap should not complain about it.

OK? Gerd

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

---

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, the overlap is produced by the RoundCoordsFilter at res 20. This is quite normal and the algo should be able to handle them. The alternative would be to change the the filter(s) so that they don't produce self- intersecting polygons. Gerd ________________________________________ Von: Gerd Petermann Gesendet: Mittwoch, 25. Januar 2017 16:22:05 An: Development list for mkgmap Betreff: AW: [mkgmap-dev] Multipolygon-Relation checks in mkgmap Hi Ticker, okay, I'll have a look at the branch. The problem in http://www.openstreetmap.org/relation/2199651 is solved with r3773, but your case looks different. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 25. Januar 2017 15:56:06 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap Hi Gerd Using your split of germany, 63240135.osm.pbf gives me the problem after I converted PolygonSplitterBase and AreaClipper to the new algo It is the outer way of relation/27312 at 48.94071,13.70245 At highest resolution, openStreetMap shows no intersection, but when I dump the highRes points after the split complains and plot them it shows an overlap. Ticker On Wed, 2017-01-25 at 14:29 +0000, Gerd Petermann wrote:

Hi Ticker,

do you have an example for such a problem case?

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 25. Januar 2017 13:25:34 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

Yes - please

I started looking at MultiPolygonRelation yesterday with a view of trying to convert it to use the new ShapeSplitter algorithm.

I think that the way a self-intersecting polygon is rewritten after a split using the Java2D library causes problems for the new algorithm when it makes a later cut for points limits or subdivisions, even when the next cut isn't in the overlapped area.

All I've done so far is convert a few more places to use highPrec logic and then slightly disparaging at the complexity of the whole thing.

Ticker

On Wed, 2017-01-25 at 09:05 +0000, Gerd Petermann wrote:

...

Hi all,

I'd like to rewrite the code in MultiPolygonRelation so that it tolerates more mp-rels. For example, the relation http://www.openstreetmap.org/relation/2199651 produces these warnings: WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: Some polygons are intersecting. This is not allowed in multipolygons. WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: - http://www.openstreetmap.org/way/165084794 WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: - http://www.openstreetmap.org/way/165084810 WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: Polygon 4611686018427387906(8P)(165084810[8P]) carries role inner but is not inside any other polygon. Potentially it does not belong to this multipolygon. The inner way touches the outer way in one point. My understanding is that this is correct, mkgmap should not complain about it.

OK? Gerd

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

---

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, I like the idea to do the cutting only at high-prec. Maybe some backtracking algo would help here? Something like "If the shape is still to complex after DouglasPeucker was applied go back, split, and try again." Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 26. Januar 2017 11:40:09 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap Hi Gerd Ah. I need to have a think about when the filters operate and do they generate new points. It is quite expensive to detect polygon self -intersection (and that probably quite a bit of the cost if using Java2D intersect) so don't think this should be added into filters as well. My idea would be along the lines of always cutting at high-prec, only doing real filtering at the final map generation stage, but having pre -filter functions that have estimates of the number of points in line/poly so that splitting can be done earlier presumed necessary Also, when a polygon is known to cover too large an area, instead of being split arbitrarily by PolyonSubDivSizeSplitter, it is split as part of MapSplitter.SplitMaxSize, forcing it into the MapArea.splitIntoAreas logic. Ticker On Thu, 2017-01-26 at 08:42 +0000, Gerd Petermann wrote:

Hi Ticker,

the overlap is produced by the RoundCoordsFilter at res 20. This is quite normal and the algo should be able to handle them. The alternative would be to change the the filter(s) so that they don't produce self- intersecting polygons.

Gerd

________________________________________ Von: Gerd Petermann Gesendet: Mittwoch, 25. Januar 2017 16:22:05 An: Development list for mkgmap Betreff: AW: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Ticker,

okay, I'll have a look at the branch. The problem in http://www.openstreetmap.org/relation/2199651 is solved with r3773, but your case looks different.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 25. Januar 2017 15:56:06 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

Using your split of germany, 63240135.osm.pbf gives me the problem after I converted PolygonSplitterBase and AreaClipper to the new algo

It is the outer way of relation/27312 at 48.94071,13.70245 At highest resolution, openStreetMap shows no intersection, but when I dump the highRes points after the split complains and plot them it shows an overlap.

Ticker

On Wed, 2017-01-25 at 14:29 +0000, Gerd Petermann wrote:

...

Hi Ticker,

do you have an example for such a problem case?

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 25. Januar 2017 13:25:34 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

Yes - please

I started looking at MultiPolygonRelation yesterday with a view of trying to convert it to use the new ShapeSplitter algorithm.

I think that the way a self-intersecting polygon is rewritten after a split using the Java2D library causes problems for the new algorithm when it makes a later cut for points limits or subdivisions, even when the next cut isn't in the overlapped area.

All I've done so far is convert a few more places to use highPrec logic and then slightly disparaging at the complexity of the whole thing.

Ticker

On Wed, 2017-01-25 at 09:05 +0000, Gerd Petermann wrote:

...

Hi all,

I'd like to rewrite the code in MultiPolygonRelation so that it tolerates more mp-rels. For example, the relation http://www.openstreetmap.org/relation/2199651 produces these warnings: WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: Some polygons are intersecting. This is not allowed in multipolygons. WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: - http://www.openstreetmap.org/way/165084794 WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: - http://www.openstreetmap.org/way/165084810 WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: Polygon 4611686018427387906(8P)(165084810[8P]) carries role inner but is not inside any other polygon. Potentially it does not belong to this multipolygon. The inner way touches the outer way in one point. My understanding is that this is correct, mkgmap should not complain about it.

OK? Gerd

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

---

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

---

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, I am not sure but I think those are filtered by RemoveObsoletePointsFilter. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 26. Januar 2017 15:53:00 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap I'll try something like this. On a slightly related point, a some of the filters are suppressed at the highest res (24) - wont OSM data have a higher res. than this and so could there be multiple adjacent points on a line/poly with the same std mapRes coordinates? Ticker On Thu, 2017-01-26 at 10:54 +0000, Gerd Petermann wrote:

Hi Ticker,

I like the idea to do the cutting only at high-prec. Maybe some backtracking algo would help here? Something like "If the shape is still to complex after DouglasPeucker was applied go back, split, and try again."

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 26. Januar 2017 11:40:09 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

Ah.

I need to have a think about when the filters operate and do they generate new points. It is quite expensive to detect polygon self -intersection (and that probably quite a bit of the cost if using Java2D intersect) so don't think this should be added into filters as well.

My idea would be along the lines of always cutting at high-prec, only doing real filtering at the final map generation stage, but having pre -filter functions that have estimates of the number of points in line/poly so that splitting can be done earlier presumed necessary

Also, when a polygon is known to cover too large an area, instead of being split arbitrarily by PolyonSubDivSizeSplitter, it is split as part of MapSplitter.SplitMaxSize, forcing it into the MapArea.splitIntoAreas logic.

Ticker

On Thu, 2017-01-26 at 08:42 +0000, Gerd Petermann wrote:

...

Hi Ticker,

the overlap is produced by the RoundCoordsFilter at res 20. This is quite normal and the algo should be able to handle them. The alternative would be to change the the filter(s) so that they don't produce self- intersecting polygons.

Gerd

________________________________________ Von: Gerd Petermann Gesendet: Mittwoch, 25. Januar 2017 16:22:05 An: Development list for mkgmap Betreff: AW: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Ticker,

okay, I'll have a look at the branch. The problem in http://www.openstreetmap.org/relation/2199651 is solved with r3773, but your case looks different.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 25. Januar 2017 15:56:06 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

Using your split of germany, 63240135.osm.pbf gives me the problem after I converted PolygonSplitterBase and AreaClipper to the new algo

It is the outer way of relation/27312 at 48.94071,13.70245 At highest resolution, openStreetMap shows no intersection, but when I dump the highRes points after the split complains and plot them it shows an overlap.

Ticker

On Wed, 2017-01-25 at 14:29 +0000, Gerd Petermann wrote:

...

Hi Ticker,

do you have an example for such a problem case?

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 25. Januar 2017 13:25:34 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

Yes - please

I started looking at MultiPolygonRelation yesterday with a view of trying to convert it to use the new ShapeSplitter algorithm.

I think that the way a self-intersecting polygon is rewritten after a split using the Java2D library causes problems for the new algorithm when it makes a later cut for points limits or subdivisions, even when the next cut isn't in the overlapped area.

All I've done so far is convert a few more places to use highPrec logic and then slightly disparaging at the complexity of the whole thing.

Ticker

On Wed, 2017-01-25 at 09:05 +0000, Gerd Petermann wrote:

...

Hi all,

I'd like to rewrite the code in MultiPolygonRelation so that it tolerates more mp-rels. For example, the relation http://www.openstreetmap.org/relation/2199651 produces these warnings: WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: Some polygons are intersecting. This is not allowed in multipolygons. WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: - http://www.openstreetmap.org/way/165084794 WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: - http://www.openstreetmap.org/way/165084810 WARN: uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation f:\osm\rel2199651.osm: Polygon 4611686018427387906(8P)(165084810[8P]) carries role inner but is not inside any other polygon. Potentially it does not belong to this multipolygon. The inner way touches the outer way in one point. My understanding is that this is correct, mkgmap should not complain about it.

OK? Gerd

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

---

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

---

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

---

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, please review. I think the results at lower resolutions are worse compared to older versions. Example: Use 63240135.img and compare the results in GPSMapEdit. Zoom to 50 m and go to (Ctrl+G) 48.907440 13.471183. At level 1 the one half of the city park is lost. In other places it seems to improve things, e.g. the soccer field near 48.906100 13.460832 no longer disappears at level 1. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Freitag, 27. Januar 2017 14:18:45 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap Hi Gerd I've just committed something to split polygons early at high precision. It has become a work-in-progress to stop needless area splitting at low resolutions; hence I've left in comments and thoughts to myself that I'll gradually tidy up. Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Gerd I've just committed another batch of changes. It is getting close to being finished but not quite there yet and still doesn't solve the 1/2 park issue but I will address this soon. Ticker On Sat, 2017-01-28 at 11:07 +0000, Ticker Berkin wrote:

Hi Gerd

I see this problem. Yesterday afternoon I made a lot more changes, but still a work-in-progress. I'll run all of Germany through and if it fixes this and, if no obvious additional problems, I'll commit.

Ticker

On Sat, 2017-01-28 at 08:38 +0000, Gerd Petermann wrote:

...

Hi Ticker,

please review. I think the results at lower resolutions are worse compared to older versions. Example: Use 63240135.img and compare the results in GPSMapEdit. Zoom to 50 m and go to (Ctrl+G) 48.907440 13.471183. At level 1 the one half of the city park is lost.

In other places it seems to improve things, e.g. the soccer field near 48.906100 13.460832 no longer disappears at level 1.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Freitag, 27. Januar 2017 14:18:45 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

I've just committed something to split polygons early at high precision. It has become a work-in-progress to stop needless area splitting at low resolutions; hence I've left in comments and thoughts to myself that I'll gradually tidy up.

Ticker

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

---

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, thanks, will look again later. I am working on a patch for the MultiPolygonCutter. It works without java.awt.geom.Area, the basic idea is to connect shapes where they are close to each other. I've tried that in 2012, maybe I get it working now. One problem that I've noticed: The code in ShapeSplitter seems to consider some shapes as self-intersecting when the connected inner ways are clockwise (or not clockwise, not sure which one causes trouble). I assume you coded this because the shapes produced by java.awt.geom.Area are like that, outer shape is one direction and inner shapes are in the other direction. I have some problems with this behaviour, is it needed ? For now I found a work around by reversing the ways so that they are ordered. Attached is a patch with what I coded so far, open problems are mp-rels at tile boundaries and performance. Be careful, the code contains lots of GPXCreator statements and other debug code. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 31. Januar 2017 16:26:41 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap Hi Gerd I've think I've finished making all the changes I want to do at the moment - It seems to work nicely. Sometime can you merge the branch back if you are happy with it. Thanks Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, you are right that self-intersecting polygons are not allowed in OSM. On the other hand, the current code in MultiPolygonRelation is meant to produce self intersecting polygons as it connects the holes with the outer shapes. As far as I know the Garmin algos do not care about self intersection, so up to now I never cared about the direction of the ways when connecting them to the outer shape. I think that means that java area code also doesn't care. Anyhow, I think that problem is solved with the reversing. I am running further tests with r3781 rnow. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 31. Januar 2017 18:35:11 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap Hi Gerd ShapeSplitter only works on a single-path shape. Considering the act of splitting a shape with a single line, you are left with a list of lines that start and end on the divider. These lines don't cross each other unless the polygon was self-intersecting which is not allowed. Then, just considering one side of the divider, the complexities of how the other side contorted to define multiple holes in a shape, and shapes in a hole can all be ignored. Lines going one way relating to the dividing line define the outer edge of a shape, and if the shape has direct holes, they must go the other way. I think the above is true for any non-self-intersecting polygon. ShapeSplitter has to resort to using the sign of the area of a shape defined by one of these lines and the divider only when multiple lines start and end at the same point. It can handle a shape and hole going through a single dividing point, so can easily cope with dividing a polygon where there is a single cut to an inner hole. Without self-intersection, if the dominant direction of the polygon is, say, anti-clockwise, then the hole must be clockwise. Does this make sense? Ticker On Tue, 2017-01-31 at 15:41 +0000, Gerd Petermann wrote:

Hi Ticker,

thanks, will look again later. I am working on a patch for the MultiPolygonCutter. It works without java.awt.geom.Area, the basic idea is to connect shapes where they are close to each other. I've tried that in 2012, maybe I get it working now. One problem that I've noticed: The code in ShapeSplitter seems to consider some shapes as self -intersecting when the connected inner ways are clockwise (or not clockwise, not sure which one causes trouble). I assume you coded this because the shapes produced by java.awt.geom.Area are like that, outer shape is one direction and inner shapes are in the other direction. I have some problems with this behaviour, is it needed ? For now I found a work around by reversing the ways so that they are ordered. Attached is a patch with what I coded so far, open problems are mp-rels at tile boundaries and performance. Be careful, the code contains lots of GPXCreator statements and other debug code.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 31. Januar 2017 16:26:41 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

I've think I've finished making all the changes I want to do at the moment - It seems to work nicely. Sometime can you merge the branch back if you are happy with it.

Thanks Ticker

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, yes, you are probably right. My new algo produces a result similar to the old one directly followed by ShapeMergeFilter. I think most of the complex logic in MultiPolygonCutter is used to find the best place for splitting. The target is probably to find cut lines which go through more than one inner ring so that the number of splits is reduced. Other important targets are - aspect ratio should be small - added lines should be short Maybe you find a way to implement that without using java area or maybe with fewer uses. I have a cold and cannot concentrate well, so sorry for the noise. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 1. Februar 2017 10:24:43 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap Hi Gerd I got lost in the logic of MultiPolygonRelation, but the impression I got was it cut right through the outer polygon to expose the inner one, which it could then combine into one of the bits of the outer if it just touches the edge of the inner - just adding the points in the same direction. ShapeMergeFilter might partially rejoin the outer. Ticker On Wed, 2017-02-01 at 08:33 +0000, Gerd Petermann wrote:

Hi Ticker,

you are right that self-intersecting polygons are not allowed in OSM. On the other hand, the current code in MultiPolygonRelation is meant to produce self intersecting polygons as it connects the holes with the outer shapes. As far as I know the Garmin algos do not care about self intersection, so up to now I never cared about the direction of the ways when connecting them to the outer shape. I think that means that java area code also doesn't care. Anyhow, I think that problem is solved with the reversing.

I am running further tests with r3781 rnow.

Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 31. Januar 2017 18:35:11 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

ShapeSplitter only works on a single-path shape. Considering the act of splitting a shape with a single line, you are left with a list of lines that start and end on the divider. These lines don't cross each other unless the polygon was self-intersecting which is not allowed.

Then, just considering one side of the divider, the complexities of how the other side contorted to define multiple holes in a shape, and shapes in a hole can all be ignored. Lines going one way relating to the dividing line define the outer edge of a shape, and if the shape has direct holes, they must go the other way.

I think the above is true for any non-self-intersecting polygon.

ShapeSplitter has to resort to using the sign of the area of a shape defined by one of these lines and the divider only when multiple lines start and end at the same point.

It can handle a shape and hole going through a single dividing point, so can easily cope with dividing a polygon where there is a single cut to an inner hole. Without self-intersection, if the dominant direction of the polygon is, say, anti-clockwise, then the hole must be clockwise.

Does this make sense?

Ticker

On Tue, 2017-01-31 at 15:41 +0000, Gerd Petermann wrote:

...

Hi Ticker,

thanks, will look again later. I am working on a patch for the MultiPolygonCutter. It works without java.awt.geom.Area, the basic idea is to connect shapes where they are close to each other. I've tried that in 2012, maybe I get it working now. One problem that I've noticed: The code in ShapeSplitter seems to consider some shapes as self -intersecting when the connected inner ways are clockwise (or not clockwise, not sure which one causes trouble). I assume you coded this because the shapes produced by java.awt.geom.Area are like that, outer shape is one direction and inner shapes are in the other direction. I have some problems with this behaviour, is it needed ? For now I found a work around by reversing the ways so that they are ordered. Attached is a patch with what I coded so far, open problems are mp-rels at tile boundaries and performance. Be careful, the code contains lots of GPXCreator statements and other debug code.

Gerd

________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 31. Januar 2017 16:26:41 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Multipolygon-Relation checks in mkgmap

Hi Gerd

I've think I've finished making all the changes I want to do at the moment - It seems to work nicely. Sometime can you merge the branch back if you are happy with it.

Thanks Ticker

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

---

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev