Hi WanMil,
Date: Thu, 24 Jan 2013 21:02:11 +0100 From: wmgcnfg@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] shapes with holes
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.
Great! Which algorithm did you implement? Do you use connect the inner polygon by one line in both directions with the outer polygon? How did you implement the visibility graph (which I think is required to ensure that the cutting line does not intersect with any other polygon)? I remember that I used some library to test the usage of such a graph. It was ok for small mps but for sea multipolygons with large polygons and lots of inner polygons it was performance trash! But maybe one can cut down the visibility graph to the required information which might also improve the performance. I did not try with huge polygons containing many large inner polygons, I assume this will be the worst case. In short, I calculate the the distance between each line segment of the outer polygon to each point of the inner polygons. For each inner polygon, the combination with the smallest dist is kept. Next, these values are sorted so that the smallest dist comes first. then, for each inner polygons I try to find a point in an other inner polygon that is closer than the outer polygon. Finally, I connect the inner polygons with the outer in the order that was retrieved by the sort. This should make sure that I don't cross lines, but I am not yet 100% sure.
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) ...
Arghh, I've fixed that in my working copy but didn't commit it... It should be working now :-)
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?
Do you want to move the mp calculation to the filter chain or do you describe the resolution based cutting of mps by reusing parts of the filter chain?
I guess you mean the second. That's what I am trying to do. Yes, I think the filters have not enough information to decide how the simplified shape should look like. That has to be done in the mp-cut algorithm.
So, I think we work in the same direction. I'll continue testing the algo. I guess I should find worse cases in the polygons created by the SeaGenerator. Ciao, Gerd