Hi WanMil, WanMil wrote
So you have to add some costly checks which point is directly connectable. There is an algorithm (I don't remember the name) that calculates which points are directly visible from a given point. If you want to implement it would work. Just search Wikipedia and the polygon algorithms. You will find it. I guss it's not very nice to the performance...
Performing a quick search I haven't found an algorithm but the problem is very similar to the visibility problems described in wikipedia: http://en.wikipedia.org/wiki/Visibility_%28geometry%29 http://en.wikipedia.org/wiki/Isovist http://en.wikipedia.org/wiki/Visibility_graph http://en.wikipedia.org/wiki/Art_gallery_problem
I have an algo now and performance seems to be quite ok. I did not yet try to place it into the mp-cut branch because I see NPE when I use the version as is: java.lang.NullPointerException at uk.me.parabola.mkgmap.reader.osm.mp.FewCutOptimizedAlgorithm.createAreas(FewCutOptimizedAlgorithm.java:431) at uk.me.parabola.mkgmap.reader.osm.mp.FewCutOptimizedAlgorithm.cutOutInnerPolygons(FewCutOptimizedAlgorithm.java:262) at uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation.processElements(MultiPolygonRelation.java:982) at uk.me.parabola.mkgmap.reader.osm.ElementSaver.addRelation(ElementSaver.java:167) ... Anyway, I want to make sure that we plan the same changes. As you already pointed out, the filter chain for shapes is probably not in the right order. Here is my proposal in pseudo-code: for each polygon (including holes){ for each resolution{ distinguish inner/outer smooth lines (eg. round coords, use Douglas-Peucker) of outer if outer is big enough for the selected resolution{ for each inner { smooth lines if inner is big enough: save it in list } if (list not empty): cutOutInnerPolygons(outer, list of inner) } cut shapes into pieces with max. 250 points } } The method MapBuilder.processShapes() should not change the shapes. Do you think the same way? Ciao, Gerd -- View this message in context: http://gis.19327.n5.nabble.com/shapes-with-holes-tp5745424p5746085.html Sent from the Mkgmap Development mailing list archive at Nabble.com.