[mkgmap-dev] shapes with holes

Thu Jan 24 20:25:01 GMT 2013

Hi WanMil,

> Date: Thu, 24 Jan 2013 21:02:11 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20130124/dd6a1af4/attachment.html 