logo separator

[mkgmap-dev] [PATCH v2] sea polygons

From Apollinaris Schoell aschoell at gmail.com on Sun Aug 2 16:22:47 BST 2009

this is really great to get sea polygons. makes maps really much better
Don't understand why is there a need for relations?
is it common to have relations for coastline? have never seen it. my  
understanding is the right side of the way is sea, left side is land.  
how can the knowledge of inner way help here except in the case of an  
island where you have the whole closed polygon available to make a  
decision.
it's nearly impossible to build a relation for a whole continent. due  
to restriction in relation members you would need parent relations  
collecting all pieces. and when done all coastlines will be inner  
elements. there can't be an outer element except you extend the  
definition to leave earth



On Aug 2, 2009, at 2:32 AM, Christian Gawron wrote:

> This improved version should fix an OutOfMemoryError reported by  
> maning sambale and Dermot McNally.
> It also contains an update of the multipolygon patch by Rudi (which  
> seems to produce better results fo Corsica).
>
> Best wishes
> Christian
> Index: src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
> ===================================================================
> --- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java	 
> (Revision 1115)
> +++ 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/Way.java
> ===================================================================
> --- src/uk/me/parabola/mkgmap/reader/osm/Way.java	(Revision 1115)
> +++ 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/xml/Osm5XmlHandler.java
> ===================================================================
> --- src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java	 
> (Revision 1115)
> +++ src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java	 
> (Arbeitskopie)
> @@ -19,6 +19,7 @@
> 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;
> @@ -65,6 +66,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 +94,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 +108,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 +374,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 +405,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 +452,10 @@
> 		}
>
> 		coordMap = null;
> +
> +		if (generateSea)
> +		    generateSeaPolygon(shoreline);
> +
> 		for (Relation r : relationMap.values())
> 			converter.convertRelation(r);
>
> @@ -746,4 +756,102 @@
> 			return fakeIdVal;
> 		}
> 	}
> +
> +        private void generateSeaPolygon(List<Way> shoreline) {
> +	    System.out.printf("generating sea\n");
> +	    long seaId;
> +	    seaId = (1L << 62) + nextFakeId++;
> +	    Way sea = new Way(seaId);
> +	    wayMap.put(seaId, sea);
> +	    Area bbox = mapper.getBounds();
> +	    Coord nw = new Coord(bbox.getMinLat(), bbox.getMinLong());
> +	    Coord ne = new Coord(bbox.getMinLat(), bbox.getMaxLong());
> +	    Coord sw = new Coord(bbox.getMaxLat(), bbox.getMinLong());
> +	    Coord se = new Coord(bbox.getMaxLat(), bbox.getMaxLong());
> +	    sea.addPoint(nw);
> +	    sea.addPoint(ne);
> +	    sea.addPoint(se);
> +	    sea.addPoint(sw);
> +	    sea.addPoint(nw);
> +	    sea.addTag("natural", "sea");
> +
> +	    Relation seaRelation = new GeneralRelation((1L << 62) +  
> nextFakeId++);
> +	    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()) {
> +		    System.out.println("island after concatenating\n");
> +		    islands.add(w);
> +		    it.remove();
> +		}
> +	    }
> +
> +	    for (Way w : islands) {
> +		seaRelation.addElement("inner", w);
> +	    }
> +	    for (Way w : shoreline) {
> +		seaRelation.addElement("inner", w);
> +	    }
> +	    seaRelation = new MultiPolygonRelation(seaRelation, wayMap);
> +	    relationMap.put(seaId, seaRelation);
> +	    seaRelation.processElements();
> +        }
> +
> +        public 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) {
> +			System.out.printf("merging: %d %d %d\n", 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 1115)
> +++ 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 1115)
> +++ 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.
> @@ -111,7 +113,7 @@
> 		}
> 		return null;
> 	}
> -
> +	
> 	/**
> 	 * Make a deep copy of this object.
> 	 * @return A copy of this object.
> @@ -262,4 +264,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 1115)
> +++ resources/styles/default/polygons	(Arbeitskopie)
> @@ -55,6 +55,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 at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev




More information about the mkgmap-dev mailing list