Here is an improved version of the sea polygon patch which also handles shorelines intersecting the boundary of the map (set by the <bounds> element). I have tested it with Ireland - there are still some islands which are "flooded", so the patch should not be considered "final". Best wishes Christian Index: src/uk/me/parabola/mkgmap/reader/osm/Way.java =================================================================== --- src/uk/me/parabola/mkgmap/reader/osm/Way.java (Revision 1124) +++ src/uk/me/parabola/mkgmap/reader/osm/Way.java (Arbeitskopie) @@ -76,6 +76,10 @@ } } + public boolean isClosed() { + return 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/MultiPolygonRelation.java =================================================================== --- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java (Revision 1124) +++ src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java (Arbeitskopie) @@ -1,11 +1,10 @@ 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; /** @@ -16,15 +15,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 +36,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); + } } } @@ -45,18 +50,63 @@ } /** Process the ways in this relation. + * Joins way with the role "outer" * 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()); + 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 +114,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/xml/Osm5XmlHandler.java =================================================================== --- src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java (Revision 1124) +++ src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java (Arbeitskopie) @@ -19,9 +19,12 @@ 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 uk.me.parabola.imgfmt.app.Area; import uk.me.parabola.imgfmt.app.Coord; @@ -65,6 +68,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 +96,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 +110,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 +376,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 +407,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 +454,10 @@ } coordMap = null; + + if (generateSea) + generateSeaPolygon(shoreline); + for (Relation r : relationMap.values()) converter.convertRelation(r); @@ -707,7 +719,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 +758,267 @@ 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(); + } + } + + for (Way w : islands) { + seaRelation.addElement("inner", w); + } + + 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) { + log.error(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())); + } + else { + log.debug("hits: ", hStart, hEnd); + hitMap.put(hStart, w); + hitMap.put(hEnd, null); + } + } + + if (hitMap.size() > 0) { + Way w = new Way((1L << 62) + nextFakeId++); + Iterator<EdgeHit> it1; + it1=hitMap.keySet().iterator(); + EdgeHit hit = it1.next(); + while (hit != null) { + Way seg = hitMap.get(hit); + if (seg != null) { + log.info("adding shoreline ", w); + w.getPoints().addAll(seg.getPoints()); + if (it1.hasNext()) + hit = it1.next(); + else + hit = null; + } + else { + EdgeHit h1 = it1.next(); + Coord p; + p = hit.getPoint(seaBounds); + log.debug("way: ", hit, p); + w.addPoint(p); + if (hit.edge < h1.edge) { + log.info("joining: ", hit, h1); + for (int i=hit.edge; i<h1.edge; i++) { + hit = new EdgeHit(i, 1.0); + p = hit.getPoint(seaBounds); + log.debug("way: ", hit, p); + w.addPoint(p); + } + } + else if (hit.edge > h1.edge) { + log.info("joining: ", hit, h1); + for (int i=hit.edge; i<4; i++) { + hit = new EdgeHit(i, 1.0); + p = hit.getPoint(seaBounds); + log.debug("way: ", hit, p); + w.addPoint(p); + } + for (int i=0; i<h1.edge; i++) { + hit = new EdgeHit(i, 1.0); + p = hit.getPoint(seaBounds); + log.debug("way: ", hit, p); + w.addPoint(p); + } + } + w.addPoint(h1.getPoint(seaBounds)); + hit = h1; + } + } + 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; + } + + Coord getPoint(Area a) { + log.debug("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 1124) +++ 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 1124) +++ 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: resources/styles/default/polygons =================================================================== --- resources/styles/default/polygons (Revision 1124) +++ 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]