[mkgmap-dev] shapes with holes

Thu Jan 24 20:02:11 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.

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 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.
If you mean the first it's another approach. That's ok but I first 
wanted to test with the mp_cut branch if it helps to use resolution 
dependend mp cutting algorithms.
In any case it's worthy to have a look on the existing filter chain. Any 
improvement in the concept or in real implementation will help fixing 
the mp cut problem with disappearing small polygons.

In my concept I am not sure if it is required to use the whole filter 
chain in the mp processing. But I have also learned that applying 
filters like the RoundCoordsFilter before cutting also gives new 
problems to be solved.
For example:
A simple polygon might contain a hole if its coords are mapped to 
another resolution:

res=24:

  ------   ------
/      \ |     |
|      / |     |
|    /   |     |
|    \---      |
|              |
|              |
----------------

might be transformed to res=16

----------------
|              |
|     ---      |
|     | |      |
|     ---      |
|              |
----------------

The existing mp cut algorithm must not handle this problem. So this is 
new thing to be solved in the resolution dependend mp cutting. Maybe not 
a big thing but there are some other things I didn't expect or I do not 
understand so far. That's the reason why there seem to be no progress in 
the last weeks.

>
> Ciao,
> Gerd
>

Have fun!
WanMil