[mkgmap-dev] [Fwd: [PATCH v4a] sea polygons]
From maning sambale emmanuel.sambale at gmail.com on Mon Aug 17 15:49:59 BST 2009
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 at 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 at 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/ ------------------------------------------------------
- Previous message: [mkgmap-dev] [Fwd: [PATCH v4a] sea polygons]
- Next message: [mkgmap-dev] [Fwd: [PATCH v4a] sea polygons]
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the mkgmap-dev mailing list