[mkgmap-dev] shapes with holes

Mon Jan 28 21:44:42 GMT 2013

Hi WanMil,

WanMil wrote
> Using the closest approach you would cut between point 6 and 1. But this 
> intersects the outer polygon so it's not a good idea...
> 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...
> 
> So if you can realize it it probably will be a good approach. The 
> algorithms are a bit more complex than it seems on a first sight.

yes, it turned out that the Line2D.ptSegDistSq() method used with the
mapunit values is fast enough,
but much too imprecise. I found 
uk.me.parabola.util.QuadTree.distanceToSegment() which 
gives much better results, but is very CPU consuming. I still don't fully
understand why 
the spherical calculation is needed since I only search for the smallest
distance, not 
the real value :-( 

Attached is the result of a split of a semi complex relation:
http://www.openstreetmap.org/browse/relation/108513

mpcut-connect.zip
<http://gis.19327.n5.nabble.com/file/n5746915/mpcut-connect.zip>  

I am now looking for a simple way to reduce the costly calculations of point
to line seqment distances.
Maybe some Voronoi diagram can help, but I fear that this all ends up in a
lot of code 
with many special cases :-(

Gerd

--
View this message in context: http://gis.19327.n5.nabble.com/shapes-with-holes-tp5745424p5746915.html
Sent from the Mkgmap Development mailing list archive at Nabble.com.