[mkgmap-dev] [PATCH v4] produce overlarge sea background only if generate-sea=multipolygon is enabled

Mon Jan 18 19:20:51 GMT 2010

>
> Hi Steve,
>
>> On 18/01/10 18:05, WanMil wrote:
>>> Attached patch (against the mp branch) solves this.
>>
>> OK thanks, applied.
>>
>> Is everyone happy that this is now a big improvement over trunk?
>
> It's performed well when processing the Baltic map.
>
> One thought, and I may be completely wrong here because I haven't
> looked at the "spec" for multipolygon processing, but this new MP
> implementation seems to have a constraint that the inner polys can't
> touch the outer poly(s). Is that so? and is that reasonable? After all
> why is it not acceptable to have a MP like this:
>
> .......*******.....
> .......*******.....
> .......*******.....
> ...................
> ...................
>
> or even more interesting:
>
> ...........*........
> ..........***.......
> .........*****......
> ....................
>
> i.e. the inner poly butts up against the edge of the outer?
>
> Are those "naughty" MPs?
>
> Mark

In the end I don't really care very much about what's the exact 
definition. There will be some mps that have touching polys. So we 
should try to implement it.

The problem is the algorithm in the mp code that detects if a polygon 
contains another polygon. It works as follows:
* Create a java.awt.Polygon class from p1
* Check if p1 contains the first point of p2
=> This contains the first problem: The definition of the 
java.awt.Polygon.contains(..) method is a bit complicated (and not 
completely understood by me). The problem arises if a point lies on the 
boundary. To get more information about this study the class comment of 
http://java.sun.com/javase/6/docs/api/java/awt/Shape.html

* Now the algorithm checks that no line of p2 intersects a line of p1. 
If p2 has an overlapping line with p1 this check fails and p1 does not 
contain p2 in the meaning of the mp code.
=> I think this could be easily improved.

The algorithm is VERY simple. If anyone knows a good and speedy 
algorithm that checks if p1 contains p2 please post a reference to the 
algorithm so that we can implement it.

WanMil