Huge improvement but not quite: http://farm3.static.flickr.com/2596/3830430206_886560d928_o.png The huge sea square is adjacent to a large lake south: http://www.openstreetmap.org/?lat=14.556&lon=121.17&zoom=11&layers=B000FTF I also notice qlandkartegt is very slow when zooming in and out when sea polygon was generated. On Mon, Aug 17, 2009 at 3:56 AM, Christian Gawron<christian.gawron@gmx.de> wrote:

Sorry, I replied to Robert instead of the list.

Best wishes Christian

Dear Robert,

sorry, I forgot to remove the remainings of another patch I recently tried before creating my patch.

Best wishes Christian

Robert Joop schrieb:

...

hi christian,

is it possible that the class uk.me.parabola.mkgmap.general.MultiShapeMerger is neither in the trunk revision 1135 nor contained in your patch? did you forget some -N option for diff or do i need to look elsewhere?

eagerly awaiting to see the sea around some mediterranean islands. :-)

thank you! rj

Index: src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java =================================================================== --- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java  (Revision 1135) +++ src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java  (Arbeitskopie) @@ -1,12 +1,12 @@  package uk.me.parabola.mkgmap.reader.osm;

 import java.util.ArrayList; -import java.util.Collection; +import java.util.Iterator;  import java.util.List;  import java.util.Map;

-import uk.me.parabola.imgfmt.Utils;  import uk.me.parabola.imgfmt.app.Coord; +import uk.me.parabola.mkgmap.general.MapShape;

 /**  * Representation of an OSM Multipolygon Relation. @@ -16,15 +16,19 @@  */  public class MultiPolygonRelation extends Relation {        private Way outer; -       private final Collection<Way> inners = new ArrayList<Way>(); +       private List<Way> outers = new ArrayList<Way>(); +       private List<Way> inners = new ArrayList<Way>(); +       private Map<Long, Way> myWayMap;

       /**         * Create an instance based on an exsiting relation.  We need to do         * this because the type of the relation is not known until after all         * its tags are read in.         * @param other The relation to base this one on. +        * @param wayMap Map of all ways.         */ -       public MultiPolygonRelation(Relation other) { +       public MultiPolygonRelation(Relation other, Map<Long, Way> wayMap) { +               myWayMap = wayMap;                setId(other.getId());                for (Map.Entry<Element, String> pairs: other.getRoles().entrySet()){                        addElement(pairs.getValue(), pairs.getKey()); @@ -33,10 +37,12 @@

                       if (value != null && pairs.getKey() instanceof Way) {                                Way way = (Way) pairs.getKey(); -                               if (value.equals("outer")) -                                       outer = way; -                               else if (value.equals("inner")) +                               if (value.equals("outer")){ +                                       outers.add(way); +                               } +                               else if (value.equals("inner")){                                        inners.add(way); +                               }                        }                }

@@ -44,19 +50,62 @@                copyTags(other);        }

-       /** Process the ways in this relation. -        * Adds ways with the role "inner" to the way with the role "outer" -        */ +        public void processElements() { -               if (outer != null) -               { + +               if (outers != null) +               { +                       // copy first outer way +                       Iterator<Way> it = outers.iterator(); +                       if (it.hasNext()){ +                               // duplicate outer way and remove tags for cascaded multipolygons +                               Way tempWay = it.next(); +                               outer = new Way(-tempWay.getId()); +                               outer.copyTags(tempWay); +                               for(Coord point: tempWay.getPoints()){ +                                       outer.addPoint(point); +                               } +                               myWayMap.put(outer.getId(), outer); +                               if (tempWay.getTags() != null){ +                                       tempWay.getTags().removeAll(); +                               } +                               it.remove(); +                       } + +                       // if we have more than one outer way, we join them if they are parts of a long way +                       it = outers.iterator(); +                       while (it.hasNext()){ +                               Way tempWay = it.next(); +                               if (tempWay.getPoints().get(0) == outer.getPoints().get(outer.getPoints().size()-1)){ +                                       for(Coord point: tempWay.getPoints()){ +                                               outer.addPoint(point); +                                       } +                                       if (tempWay.getTags() != null){ + tempWay.getTags().removeAll(); +                                       } +                                       it.remove(); +                                       it = outers.iterator(); +                               } +                       } +                        for (Way w: inners) { -                               if (w != null) { -                                       List<Coord> pts = w.getPoints(); -                                       int[] insert = findCpa(outer.getPoints(), pts); -                                       if (insert[0] > 0) -                                               insertPoints(pts, insert[0], insert[1]); -                                       pts.clear(); +                               if (w != null && outer!= null) { +                                       int[] insert = findCpa(outer.getPoints(), w.getPoints()); +                                       if (insert[0] >= 0) +                                           insertPoints(w, insert[0], insert[1]); + +                                       // remove tags from inner way that are available in the outer way +                                       if (outer.getTags() != null){ +                                               for (Map.Entry<String, String> mapTags: outer.getTags().getKeyValues().entrySet()){ +                                                       String key = mapTags.getKey(); +                                                       String value = mapTags.getValue(); +                                                       if (w.getTag(key) != null){ +                                                               if (w.getTag(key).equals(value)){ + w.deleteTag(key); +                                                               } +                                                       } +                                               } +                                       }                                }                        }                } @@ -64,22 +113,43 @@

       /**         * Insert Coordinates into the outer way. -        * @param inList List of Coordinates to be inserted +        * @param way Way to be inserted         * @param out Coordinates will be inserted after this point in the outer way.         * @param in Points will be inserted starting at this index,         *    then from element 0 to (including) this element;         */ -       private void insertPoints(List<Coord> inList, int out, int in){ +       private void insertPoints(Way way, int out, int in){                List<Coord> outList = outer.getPoints(); +               List<Coord> inList = way.getPoints();                int index = out+1; -               for (int i = in; i < inList.size(); i++) +               for (int i = in; i < inList.size(); i++){                        outList.add(index++, inList.get(i)); -               for (int i = 0; i <= in; i++) +               } +               for (int i = 0; i < in; i++){                        outList.add(index++, inList.get(i)); - -               //with this line commented we get triangles, when uncommented some areas disappear -               // at least in mapsource, on device itself looks OK. -               outList.add(index,outList.get(out)); +               } + +               if (outer.getPoints().size() < 32){ +                       outList.add(index++, inList.get(in)); +                       outList.add(index, outList.get(out)); +               } +               else{ +                       // we shift the nodes to avoid duplicate nodes (large areas only) +                       int oLat = outList.get(out).getLatitude(); +                       int oLon = outList.get(out).getLongitude(); +                       int iLat = inList.get(in).getLatitude(); +                       int iLon = inList.get(in).getLongitude(); +                       if (Math.abs(oLat - iLat) > Math.abs(oLon - iLon)){ +                               int delta = (oLon > iLon)? -1 : 1; +                               outList.add(index++, new Coord(iLat + delta, iLon)); +                               outList.add(index, new Coord(oLat + delta, oLon)); +                               } +                       else{ +                               int delta = (oLat > iLat)? 1 : -1; +                               outList.add(index++, new Coord(iLat, iLon + delta)); +                               outList.add(index, new Coord(oLat, oLon + delta)); +                       } +               }        }

       /** Index: src/uk/me/parabola/mkgmap/reader/osm/Way.java =================================================================== --- src/uk/me/parabola/mkgmap/reader/osm/Way.java       (Revision 1135) +++ src/uk/me/parabola/mkgmap/reader/osm/Way.java       (Arbeitskopie) @@ -76,6 +76,10 @@                }        }

+        public boolean isClosed() { +           return points.size() > 0 && points.get(0).equals(points.get(points.size()-1)); +        } +        /**         * A simple representation of this way.         * @return A string with the name and start point Index: src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java =================================================================== --- src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java  (Revision 1135) +++ src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java  (Arbeitskopie) @@ -19,9 +19,13 @@  import java.util.ArrayList;  import java.util.HashMap;  import java.util.IdentityHashMap; +import java.util.Iterator;  import java.util.LinkedHashMap;  import java.util.List;  import java.util.Map; +import java.util.SortedMap; +import java.util.TreeMap; +import java.util.NavigableSet;

 import uk.me.parabola.imgfmt.app.Area;  import uk.me.parabola.imgfmt.app.Coord; @@ -65,6 +69,7 @@        private final Map<String, Long> fakeIdMap = new HashMap<String, Long>();        private final List<Node> exits = new ArrayList<Node>();        private final List<Way> motorways = new ArrayList<Way>(); +       private final List<Way> shoreline = new ArrayList<Way>();

       private static final int MODE_NODE = 1;        private static final int MODE_WAY = 2; @@ -92,6 +97,7 @@        private final boolean ignoreTurnRestrictions;        private final boolean linkPOIsToWays;        private final boolean routing; +        private final boolean generateSea;        private final Double minimumArcLength;        private final String frigRoundabouts;

@@ -105,6 +111,7 @@                }                linkPOIsToWays = props.getProperty("link-pois-to-ways", false);                ignoreBounds = props.getProperty("ignore-osm-bounds", false); +               generateSea = props.getProperty("generate-sea", false);                routing = props.containsKey("route");                String rsa = props.getProperty("remove-short-arcs", null);                if(rsa != null) @@ -370,6 +377,8 @@                                if("motorway".equals(highway) ||                                   "trunk".equals(highway))                                        motorways.add(currentWay); +                               if(generateSea && "coastline".equals(currentWay.getTag("natural"))) +                                   shoreline.add(currentWay);                                currentWay = null;                                // ways are processed at the end of the document,                                // may be changed by a Relation class @@ -399,7 +408,7 @@                String type = currentRelation.getTag("type");                if (type != null) {                        if ("multipolygon".equals(type)) -                               currentRelation = new MultiPolygonRelation(currentRelation); +                               currentRelation = new MultiPolygonRelation(currentRelation, wayMap);                        else if("restriction".equals(type)) {

                               if(ignoreTurnRestrictions) @@ -446,6 +455,10 @@                }

               coordMap = null; + +               if (generateSea) +                   generateSeaPolygon(shoreline); +                for (Relation r : relationMap.values())                        converter.convertRelation(r);

@@ -707,7 +720,7 @@                        }                        currentWay.addPoint(co);                        co.incHighwayCount(); // nodes (way joins) will have highwayCount > 1 -                       if(minimumArcLength != null) +                       if (minimumArcLength != null || generateSea)                                nodeIdMap.put(co, id);                }        } @@ -746,4 +759,293 @@                        return fakeIdVal;                }        } + +        private void generateSeaPolygon(List<Way> shoreline) { + +           Area seaBounds; +           if (bbox != null) +               seaBounds = bbox; +           else +               seaBounds = mapper.getBounds(); + +           log.info("generating sea, seaBounds=", seaBounds); +           int minLat = seaBounds.getMinLat(); +           int maxLat = seaBounds.getMaxLat(); +           int minLong = seaBounds.getMinLong(); +           int maxLong = seaBounds.getMaxLong(); +           Coord nw = new Coord(minLat, minLong); +           Coord ne = new Coord(minLat, maxLong); +           Coord sw = new Coord(maxLat, minLong); +           Coord se = new Coord(maxLat, maxLong); + +           long seaId = (1L << 62) + nextFakeId++; +           Way sea = new Way(seaId); +           sea.addPoint(nw); +           sea.addPoint(sw); +           sea.addPoint(se); +           sea.addPoint(ne); +           sea.addPoint(nw); +           sea.addTag("natural", "sea"); +           log.info("sea: ", sea); +           wayMap.put(seaId, sea); + +           long multiId = (1L << 62) + nextFakeId++; +           Relation seaRelation = new GeneralRelation(multiId); +           seaRelation.addTag("type", "multipolygon"); +           seaRelation.addElement("outer", sea); + +           List<Way> islands = new ArrayList(); + +           // handle islands (closes shoreline components) first (they're easy) +           Iterator<Way> it = shoreline.iterator(); +           while (it.hasNext()) { +               Way w = it.next(); +               if (w.isClosed()) { +                   islands.add(w); +                   it.remove(); +               } +           } +           concatenateWays(shoreline); +           // there may be more islands now +           it = shoreline.iterator(); +           while (it.hasNext()) { +               Way w = it.next(); +               if (w.isClosed()) { +                   log.debug("island after concatenating\n"); +                   islands.add(w); +                   it.remove(); +               } +           } + +           // create a "inner" way for each island +           for (Way w : islands) { +               log.info("adding island " + w); +               seaRelation.addElement("inner", w); +           } + +           // the remaining shoreline segments should intersect the boundary +           // find the intersection points and store them in a SortedMap +           SortedMap<EdgeHit, Way> hitMap = new TreeMap<EdgeHit, Way>(); +           for (Way w : shoreline) { +               List<Coord> points = w.getPoints(); +               Coord pStart = points.get(0); +               Coord pEnd = points.get(points.size()-1); + +               EdgeHit hStart = getEdgeHit(seaBounds, pStart); +               EdgeHit hEnd = getEdgeHit(seaBounds, pEnd); +               if (hStart == null || hEnd == null) { +                   String msg = String.format("Non-closed coastline segment does not hit bounding box - expect strange results: %d (%s) %d (%s) %s\n", +                                              nodeIdMap.get(pStart),  pStart.toDegreeString(), +                                              nodeIdMap.get(pEnd),  pEnd.toDegreeString(), +                                              pStart.toOSMURL()); +                   log.error(msg); +                   seaRelation.addElement("inner", w); +               } +               else { +                   log.debug("hits: ", hStart, hEnd); +                   hitMap.put(hStart, w); +                   hitMap.put(hEnd, null); +               } +           } + + +           // now construct inner ways from these segments +           NavigableSet<EdgeHit> hits = (NavigableSet<EdgeHit>) hitMap.keySet(); +           while (hits.size() > 0) { +               long id = (1L << 62) + nextFakeId++; +               Way w = new Way(id); +               wayMap.put(id, w); + +               EdgeHit hit =  hits.first(); +               EdgeHit hFirst = hit; +               EdgeHit hNext; +               do { +                   Way segment = hitMap.get(hit); +                   log.info("current hit: " + hit); +                   if (segment != null) { +                       // add the segment and get the "ending hit" +                       log.info("adding: ", segment); +                       w.getPoints().addAll(segment.getPoints()); +                       hNext = getEdgeHit(seaBounds, segment.getPoints().get(segment.getPoints().size()-1)); +                   } +                   else { +                       w.addPoint(hit.getPoint(seaBounds)); +                       hNext = hits.higher(hit); +                       if (hNext == null) +                           hNext = hFirst; + +                       Coord p = hit.getPoint(seaBounds); +                       if (hit.edge < hNext.edge) { +                           log.info("joining: ", hit, hNext); +                           for (int i=hit.edge; i<hNext.edge; i++) { +                               EdgeHit corner = new EdgeHit(i, 1.0); +                               p = corner.getPoint(seaBounds); +                               log.debug("way: ", corner, p); +                               w.addPoint(p); +                           } +                       } +                       else if (hit.edge > hNext.edge) { +                           log.info("joining: ", hit, hNext); +                           for (int i=hit.edge; i<4; i++) { +                               EdgeHit corner = new EdgeHit(i, 1.0); +                               p = corner.getPoint(seaBounds); +                               log.debug("way: ", corner, p); +                               w.addPoint(p); +                           } +                           for (int i=0; i<hNext.edge; i++) { +                               EdgeHit corner = new EdgeHit(i, 1.0); +                               p = corner.getPoint(seaBounds); +                               log.debug("way: ", corner, p); +                               w.addPoint(p); +                           } +                       } +                       w.addPoint(hNext.getPoint(seaBounds)); +                   } +                   hits.remove(hit); +                   hit = hNext; +               } while (hits.size() > 0 && !hit.equals(hFirst)); + +               if (!w.isClosed()) +                   w.getPoints().add(w.getPoints().get(0)); +               log.info("adding non-island landmass, hits.size()=" + hits.size()); +               seaRelation.addElement("inner", w); +           } + +           seaRelation = new MultiPolygonRelation(seaRelation, wayMap); +           relationMap.put(multiId, seaRelation); +           seaRelation.processElements(); +        } + +        /** +        * Specifies where an edge of the bounding box is hit. +        */ +        private static class EdgeHit implements Comparable<EdgeHit> +       { +           int edge; +           double t; + +           EdgeHit(int edge, double t) { +               this.edge = edge; +               this.t = t; +           } + +           public int compareTo(EdgeHit o) { +               if (edge < o.edge) +                   return -1; +               else if (edge > o.edge) +                   return +1; +               else if (t > o.t) +                   return +1; +               else if (t < o.t) +                   return -1; +               else +                   return 0; +           } + +           @Override public boolean equals(Object o) { +               if (o instanceof EdgeHit) { +                   EdgeHit h = (EdgeHit) o; +                   return (h.edge == edge && Double.compare(h.t, t) == 0); +               } +               else +                   return false; +           } + +           Coord getPoint(Area a) { +               log.info("getPoint: ", this, a); +               switch (edge) { +               case 0: +                   return new Coord(a.getMinLat(), (int) (a.getMinLong() + t * (a.getMaxLong()-a.getMinLong()))); + +               case 1: +                   return new Coord((int)(a.getMinLat() + t * (a.getMaxLat()-a.getMinLat())), a.getMaxLong()); + +               case 2: +                   return new Coord(a.getMaxLat(), (int)(a.getMaxLong() - t * (a.getMaxLong()-a.getMinLong()))); + +               case 3: +                   return new Coord((int)(a.getMaxLat() - t * (a.getMaxLat()-a.getMinLat())), a.getMinLong()); + +               default: +                   throw new RuntimeException("illegal state"); +               } +           } + +           public String toString() { +               return "EdgeHit " + edge + "@" + t; +           } +       } + +        private EdgeHit getEdgeHit(Area a, Coord p) +        { +           return getEdgeHit(a, p, 10); +        } + +        private EdgeHit getEdgeHit(Area a, Coord p, int tolerance) +        { +           int lat = p.getLatitude(); +           int lon = p.getLongitude(); +           int minLat = a.getMinLat(); +           int maxLat = a.getMaxLat(); +           int minLong = a.getMinLong(); +           int maxLong = a.getMaxLong(); + +           log.info(String.format("getEdgeHit: (%d %d) (%d %d %d %d)", lat, lon, minLat, minLong, maxLat, maxLong)); +           if (lat <= minLat+tolerance) { +               return new EdgeHit(0, ((double)(lon - minLong))/(maxLong-minLong)); +           } +           else if (lon >= maxLong-tolerance) { +               return new EdgeHit(1, ((double)(lat - minLat))/(maxLat-minLat)); +           } +           else if (lat >= maxLat-tolerance) { +               return new EdgeHit(2, ((double)(maxLong - lon))/(maxLong-minLong)); +           } +           else if (lon <= minLong+tolerance) { +               return new EdgeHit(3, ((double)(maxLat - lat))/(maxLat-minLat)); +           } +           else +               return null; +        } + +        private void concatenateWays(List<Way> ways) { +           Map<Coord, Way> beginMap = new HashMap(); + +           for (Way w : ways) { +               if (!w.isClosed()) { +                   List<Coord> points = w.getPoints(); +                   beginMap.put(points.get(0), w); +               } +           } + +           int merged = 1; +           while (merged > 0) { +               merged = 0; +               for (Way w1 : ways) { +                   if (w1.isClosed()) continue; + +                   List<Coord> points1 = w1.getPoints(); +                   Way w2 = beginMap.get(points1.get(points1.size()-1)); +                   if (w2 != null) { +                       log.info("merging: ", ways.size(), w1.getId(), w2.getId()); +                       List<Coord> points2 = w2.getPoints(); +                       Way wm; +                       if (w1.getId() < (1L << 62)) { +                           wm = new Way((1L << 62) + nextFakeId++); +                           ways.remove(w1); +                           ways.add(wm); +                           wm.getPoints().addAll(points1); +                           beginMap.put(points1.get(0), wm); +                       } +                       else { +                           wm = w1; +                       } +                       wm.getPoints().addAll(points2); +                       ways.remove(w2); +                       beginMap.remove(points2.get(0)); +                       merged++; +                       break; +                   } +               } +           } +        }  } Index: src/uk/me/parabola/mkgmap/reader/osm/Element.java =================================================================== --- src/uk/me/parabola/mkgmap/reader/osm/Element.java   (Revision 1135) +++ src/uk/me/parabola/mkgmap/reader/osm/Element.java   (Arbeitskopie) @@ -86,6 +86,7 @@         * element.         */        public void copyTags(Element other) { +               if (other.tags != null)                tags = other.tags.copy();        }

@@ -97,4 +98,8 @@                if (this.name == null)                        this.name = name;        } + +       public Tags getTags() { +               return tags; +       }  } Index: src/uk/me/parabola/mkgmap/reader/osm/Tags.java =================================================================== --- src/uk/me/parabola/mkgmap/reader/osm/Tags.java      (Revision 1135) +++ src/uk/me/parabola/mkgmap/reader/osm/Tags.java      (Arbeitskopie) @@ -16,7 +16,9 @@  */  package uk.me.parabola.mkgmap.reader.osm;

+import java.util.HashMap;  import java.util.Iterator; +import java.util.Map;

 /**  * Store the tags that belong to an Element. @@ -120,7 +122,7 @@                }                return null;        } - +        /**         * Make a deep copy of this object.         * @return A copy of this object. @@ -271,4 +273,22 @@                                        put(e.key, e.value);                }        } -} + +       public void removeAll() { +               for (int i = 0; i < capacity; i++){ +                       keys[i] = null; +                       values[i] = null; +               } +               size = 0; +       } + +       public Map<String, String> getKeyValues() { +               Map<String, String> tagMap = new HashMap<String, String>(); +               for (int i = 0; i < capacity; i++) +                       if (keys[i] != null && values[i] != null) +                               tagMap.put(keys[i], values[i]); +               return tagMap; +       } + + +} \ No newline at end of file Index: src/uk/me/parabola/mkgmap/general/MapShape.java =================================================================== --- src/uk/me/parabola/mkgmap/general/MapShape.java     (Revision 1135) +++ src/uk/me/parabola/mkgmap/general/MapShape.java     (Arbeitskopie) @@ -67,6 +67,19 @@                return contains(this.getPoints(), co, true);        }

+       /** +        * Checks if a point is contained within this shape. An additional +        * option allows to control, whether points on the edge of the shape +        * are considered inside. +        * +        * @param co point to check +        * @param onLineIsInside controls, whether points on the edge are considered inside +        * @return true if point is in shape, false otherwise +        */ +       public boolean contains(Coord co, boolean onLineIsInside) { +               return contains(this.getPoints(), co, onLineIsInside); +       } +        /*         * Checks if a point is contained within a shape.         * Index: resources/styles/default/polygons =================================================================== --- resources/styles/default/polygons   (Revision 1135) +++ resources/styles/default/polygons   (Arbeitskopie) @@ -54,6 +54,7 @@  natural=mud [0x51 resolution 20]  natural=scrub [0x4f resolution 20]  natural=water [0x3c resolution 20] +natural=sea [0x32 resolution 10]  natural=wood [0x50 resolution 18]

 place=village [0x03 resolution 18]

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- cheers, maning ------------------------------------------------------ "Freedom is still the most radical idea of all" -N.Branden wiki: http://esambale.wikispaces.com/ blog: http://epsg4253.wordpress.com/ ------------------------------------------------------