[mkgmap-dev] shapes with holes

Thu Jan 24 09:24:26 GMT 2013

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.