[PATCH v3] sea polygons

8 Aug 2009

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]

    

Christian Gawron

Dermot McNally

Dermot McNally

maning sambale

maning sambale

maning sambale

Christian Gawron

maning sambale

Christian Gawron

Marko Mäkelä

tags

participants (4)