[mkgmap-dev] shapes with holes

Mon Jan 28 22:10:23 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
>

Hi Gerd,

looks nice.

Some notes:
I don't understand why you calculate the distance between a point and a 
segment and not between two points?

Of course you can create your own distance calculation without the 
spherical part. It is required in the Quadtree because it checks if the 
checked point is more far away than a given gap. Another reason is that 
one Garmin map unit does not have a constant length. Was that your 
problem with Line2D.ptSegDistSq()?

Your cut procedure still requires that all parts of mkgmap that use the 
resulting ways do not use the java.awt.geom.Area class. So another hard 
second part of the implementation is to find an adequate replacement for 
this.

WanMil