[Git][debian-gis-team/mkgmap][master] 4 commits: New upstream version 0.0.0+svn4223
Bas Couwenberg
gitlab at salsa.debian.org
Sat Sep 1 07:53:13 BST 2018
Bas Couwenberg pushed to branch master at Debian GIS Project / mkgmap
Commits:
5ad77dbd by Bas Couwenberg at 2018-09-01T06:33:16Z
New upstream version 0.0.0+svn4223
- - - - -
a9dbb870 by Bas Couwenberg at 2018-09-01T06:33:20Z
Merge tag 'upstream/0.0.0+svn4223'
Upstream version 0.0.0+svn4223
- - - - -
2e5587ee by Bas Couwenberg at 2018-09-01T06:33:53Z
New upstream SVN snapshot.
- - - - -
4697e867 by Bas Couwenberg at 2018-09-01T06:36:52Z
Set distribution to unstable.
- - - - -
25 changed files:
- debian/changelog
- doc/options.txt
- resources/help/en/options
- resources/mkgmap-version.properties
- resources/styles/default/inc/address
- src/uk/me/parabola/imgfmt/Utils.java
- src/uk/me/parabola/imgfmt/app/Area.java
- src/uk/me/parabola/imgfmt/app/Coord.java
- src/uk/me/parabola/imgfmt/app/CoordNode.java
- src/uk/me/parabola/imgfmt/app/net/RouteNode.java
- src/uk/me/parabola/imgfmt/app/trergn/RGNFileReader.java
- src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java
- src/uk/me/parabola/mkgmap/filters/RoundCoordsFilter.java
- src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
- src/uk/me/parabola/mkgmap/osmstyle/WrongAngleFixer.java
- src/uk/me/parabola/mkgmap/osmstyle/housenumber/ExtNumbers.java
- src/uk/me/parabola/mkgmap/reader/osm/CoastlineFileLoader.java
- src/uk/me/parabola/mkgmap/reader/osm/ElementSaver.java
- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonFinishHook.java
- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
- src/uk/me/parabola/mkgmap/reader/osm/RoutingHook.java
- src/uk/me/parabola/mkgmap/reader/osm/UnusedElementsRemoverHook.java
- src/uk/me/parabola/mkgmap/reader/polish/RoadHelper.java
- src/uk/me/parabola/util/ElementQuadTree.java
- src/uk/me/parabola/util/ElementQuadTreeNode.java
Changes:
=====================================
debian/changelog
=====================================
@@ -1,8 +1,9 @@
-mkgmap (0.0.0+svn4214-2) UNRELEASED; urgency=medium
+mkgmap (0.0.0+svn4223-1) unstable; urgency=medium
+ * New upstream SVN snapshot.
* Bump Standards-Version to 4.2.1, no changes.
- -- Bas Couwenberg <sebastic at debian.org> Sun, 05 Aug 2018 20:30:45 +0200
+ -- Bas Couwenberg <sebastic at debian.org> Sat, 01 Sep 2018 08:36:44 +0200
mkgmap (0.0.0+svn4214-1) unstable; urgency=medium
=====================================
doc/options.txt
=====================================
@@ -534,6 +534,24 @@ not need a map that supports routing.
that support routing. If you specify this option, you do not need
to specify --net.
<p>
+;--add-boundary-nodes-at-admin-boundaries=NUM
+: This option controls how mkgmap calculates special routing nodes which
+are needed by Garmin software to allow routing between different map tiles.
+These nodes are written to section 3 and 4 in the NOD file.
+When a road crosses the tile boundary (bbox), the road is split at this
+point and such a special node is written. This allows routing between
+one set of tiles produced by splitter.jar. However, if you create a map
+from different sets of tiles, those tiles are likely to overlap.
+For the overlapping tiles, none of the entries in NOD3 match and thus
+routing across tile border doesn't work when the route is not fully
+covered by one of the tiles.
+The option tells mkgmap to add special nodes whereever a road touches or
+crosses an administratve boundary. The NUM parameter specifies a filter
+for the admin_level. Boundaries with a higher admin_level value are ignored.
+The default value is 2 (country borders). Another reasonable value might
+be 4. A value less or equal to 0 tells mkgmap to ignore intersections at
+administrative boundaries.
+<p>
;--drive-on=left|right|detect|detect,left|detect,right
: Explicitly specify which side of the road vehicles are
expected to drive on.
=====================================
resources/help/en/options
=====================================
@@ -539,6 +539,24 @@ Miscellaneous options:
of drive-on-left roads with the rest.
Use the --bounds option to make sure that the detection
finds the correct country.
+
+--add-boundary-nodes-at-admin-boundaries=NUM
+ This option controls how mkgmap calculates special routing nodes which
+ are needed by Garmin software to allow routing between different map tiles.
+ These nodes are written to section 3 and 4 in the NOD file.
+ When a road crosses the tile boundary (bbox), the road is split at this
+ point and such a special node is written. This allows routing between
+ one set of tiles produced by splitter.jar. However, if you create a map
+ from different sets of tiles, those tiles are likely to overlap.
+ For the overlapping tiles, none of the entries in NOD3 match and thus
+ routing across tile border doesn't work when the route is not fully
+ covered by one of the tiles.
+ The option tells mkgmap to add special nodes whereever a road touches or
+ crosses an administratve boundary. The NUM parameter specifies a filter
+ for the admin_level. Boundaries with a higher admin_level value are ignored.
+ The default value is 2 (country borders). Another reasonable value might
+ be 4. A value less or equal to 0 tells mkgmap to ignore intersections at
+ administrative boundaries.
--check-roundabouts
Check that roundabouts have the expected direction (clockwise
=====================================
resources/mkgmap-version.properties
=====================================
@@ -1,2 +1,2 @@
-svn.version: 4214
-build.timestamp: 2018-07-28T09:29:55+0100
+svn.version: 4223
+build.timestamp: 2018-08-13T07:21:37+0100
=====================================
resources/styles/default/inc/address
=====================================
@@ -19,11 +19,11 @@ mkgmap:country=NLD & mkgmap:city!=* & mkgmap:admin_level8=* { set mkgmap:city='$
mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level4=Hamburg {set mkgmap:city='${mkgmap:admin_level4}' }
mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level4=Berlin {set mkgmap:city='${mkgmap:admin_level4}' }
mkgmap:country=DEU & mkgmap:region!=* & mkgmap:admin_level4=* { set mkgmap:region='${mkgmap:admin_level4}' }
-mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level8=* { set mkgmap:city='${mkgmap:admin_level8|subst:Gemeinde |subst:Stadt}' }
-mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level7=* { set mkgmap:city='${mkgmap:admin_level7|subst:Gemeinde |subst:Stadt}' }
-mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level6=* { set mkgmap:city='${mkgmap:admin_level6|subst:Gemeinde |subst:Stadt}' }
-mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level9=* { set mkgmap:city='${mkgmap:admin_level9|subst:Gemeinde |subst:Stadt}' }
-mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level10=* { set mkgmap:city='${mkgmap:admin_level10|subst:Gemeinde |subst:Stadt}' }
+mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level8=* { set mkgmap:city='${mkgmap:admin_level8|subst:Gemeinde |subst:Stadt }' }
+mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level7=* { set mkgmap:city='${mkgmap:admin_level7|subst:Gemeinde |subst:Stadt }' }
+mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level6=* { set mkgmap:city='${mkgmap:admin_level6|subst:Gemeinde |subst:Stadt }' }
+mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level9=* { set mkgmap:city='${mkgmap:admin_level9|subst:Gemeinde |subst:Stadt }' }
+mkgmap:country=DEU & mkgmap:city!=* & mkgmap:admin_level10=* { set mkgmap:city='${mkgmap:admin_level10|subst:Gemeinde |subst:Stadt }' }
# Austria = AUT
=====================================
src/uk/me/parabola/imgfmt/Utils.java
=====================================
@@ -16,6 +16,7 @@
*/
package uk.me.parabola.imgfmt;
+import java.awt.geom.Line2D;
import java.io.Closeable;
import java.io.File;
import java.io.FileInputStream;
@@ -28,8 +29,8 @@ import java.util.Calendar;
import java.util.Date;
import java.util.zip.GZIPInputStream;
-import uk.me.parabola.imgfmt.app.ImgFileWriter;
import uk.me.parabola.imgfmt.app.Coord;
+import uk.me.parabola.imgfmt.app.ImgFileWriter;
/**
* Some miscellaneous functions that are used within the .img code.
*
@@ -389,49 +390,6 @@ public class Utils {
return (long)(latHp & 0xffffffffL) << 32 | (lonHp & 0xffffffffL);
}
- /**
- * Check if the line p1_1 to p1_2 cuts line p2_1 to p2_2 in two pieces and vice versa.
- * This is a form of intersection check where it is allowed that one line ends on the
- * other line or that the two lines overlap.
- * @param p1_1 first point of line 1
- * @param p1_2 second point of line 1
- * @param p2_1 first point of line 2
- * @param p2_2 second point of line 2
- * @return true if both lines intersect somewhere in the middle of each other
- */
- public static boolean linesCutEachOther(Coord p1_1, Coord p1_2, Coord p2_1, Coord p2_2) {
- int width1 = p1_2.getHighPrecLon() - p1_1.getHighPrecLon();
- int width2 = p2_2.getHighPrecLon() - p2_1.getHighPrecLon();
-
- int height1 = p1_2.getHighPrecLat() - p1_1.getHighPrecLat();
- int height2 = p2_2.getHighPrecLat() - p2_1.getHighPrecLat();
-
- int denominator = ((height2 * width1) - (width2 * height1));
- if (denominator == 0) {
- // the lines are parallel
- // they might overlap but this is ok for this test
- return false;
- }
-
- int x1Mx3 = p1_1.getHighPrecLon() - p2_1.getHighPrecLon();
- int y1My3 = p1_1.getHighPrecLat() - p2_1.getHighPrecLat();
-
- double isx = (double)((width2 * y1My3) - (height2 * x1Mx3))
- / denominator;
- if (isx <= 0 || isx >= 1) {
- return false;
- }
-
- double isy = (double)((width1 * y1My3) - (height1 * x1Mx3))
- / denominator;
-
- if (isy <= 0 || isy >= 1) {
- return false;
- }
-
- return true;
- }
-
public static int numberToPointerSize(int n) {
// moved from imgfmt/app/mdr/MdrSection.java and app/typ/TYPFile.java
if (n <= 0xff)
@@ -452,4 +410,40 @@ public class Utils {
writer.put3s(longitude);
}
+ /**
+ * Finds the intersection of two line segments, also if one ends on the other
+ * See https://de.wikipedia.org/wiki/Geod%C3%A4tisches_Rechnen#Geradenschnitt
+ * @param p1_1 the coordinates of the start point of the first specified line segment
+ * @param p1_2 the coordinates of the end point of the first specified line segment
+ * @param p2_1 the coordinates of the start point of the second specified line segment
+ * @param p2_2 the coordinates of the end point of the second specified line segment
+ * @return null if no intersection was found, else a new Coord instance with the coordinates of the intersection
+ */
+ public static Coord getSegmentSegmentIntersection (Coord p1_1, Coord p1_2, Coord p2_1, Coord p2_2) {
+ long x1 = p1_1.getHighPrecLon();
+ long y1 = p1_1.getHighPrecLat();
+ long x2 = p1_2.getHighPrecLon();
+ long y2 = p1_2.getHighPrecLat();
+ long x3 = p2_1.getHighPrecLon();
+ long y3 = p2_1.getHighPrecLat();
+ long x4 = p2_2.getHighPrecLon();
+ long y4 = p2_2.getHighPrecLat();
+
+ if (!Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4))
+ return null;
+
+ long divider = (y2 - y1) * (x4 - x3) - (y4 - y3) * (x2 - x1);
+ if (divider == 0)
+ return null; // parallel
+ double h = ((y4 - y3) * (x1 - x4) - (y1 - y4) * (x4 - x3)) / (double) divider;
+
+ if (h < 0 || h > 1) {
+ return null; // intersection of lines is not on given segment
+ }
+ double xs = x1 + h * (x2 - x1);
+ double ys = y1 + h * (y2 - y1);
+ return Coord.makeHighPrecCoord((int)Math.round(ys), (int) Math.round(xs));
+ }
+
}
+
=====================================
src/uk/me/parabola/imgfmt/app/Area.java
=====================================
@@ -69,6 +69,28 @@ public class Area {
, Utils.toMapUnit(maxLat), Utils.toMapUnit(maxLong));
}
+ public static Area getBBox(List<Coord> points) {
+ int tmpMinLat = Integer.MAX_VALUE;
+ int tmpMaxLat = Integer.MIN_VALUE;
+ int tmpMinLong = Integer.MAX_VALUE;
+ int tmpMaxLong = Integer.MIN_VALUE;
+
+ for (Coord co : points) {
+ int lat = co.getLatitude();
+ if (lat < tmpMinLat)
+ tmpMinLat = lat;
+ if (lat > tmpMaxLat)
+ tmpMaxLat = lat;
+
+ int lon = co.getLongitude();
+ if (lon < tmpMinLong)
+ tmpMinLong = lon;
+ if (lon > tmpMaxLong)
+ tmpMaxLong = lon;
+ }
+ return new Area(tmpMinLat, tmpMinLong, tmpMaxLat, tmpMaxLong);
+ }
+
public int getMinLat() {
return minLat;
}
=====================================
src/uk/me/parabola/imgfmt/app/Coord.java
=====================================
@@ -50,6 +50,7 @@ public class Coord implements Comparable<Coord> {
private final static short END_OF_WAY = 0x0200; // use only in WrongAngleFixer
private final static short HOUSENUMBER_NODE = 0x0400; // start/end of house number interval
private final static short ADDED_HOUSENUMBER_NODE = 0x0800; // node was added for house numbers
+ private final static short ON_COUNTRY_BORDER = 0x1000; // node is on a country border
private final static int HIGH_PREC_BITS = 30;
public final static int DELTA_SHIFT = HIGH_PREC_BITS - 24;
@@ -340,7 +341,7 @@ public class Coord implements Comparable<Coord> {
}
/**
- * @return if this is the beginning/end of a house number interval
+ * @return true if this is the beginning/end of a house number interval
*/
public boolean isNumberNode(){
return (flags & HOUSENUMBER_NODE) != 0;
@@ -357,7 +358,7 @@ public class Coord implements Comparable<Coord> {
}
/**
- * @return if this is the beginning/end of a house number interval
+ * @return true if this was added by the housenumber processing
*/
public boolean isAddedNumberNode(){
return (flags & ADDED_HOUSENUMBER_NODE) != 0;
@@ -373,6 +374,24 @@ public class Coord implements Comparable<Coord> {
this.flags &= ~ADDED_HOUSENUMBER_NODE;
}
+ /**
+ * @return true if this was marked as place on country border.
+ */
+ public boolean getOnCountryBorder() {
+ return (flags & ON_COUNTRY_BORDER) != 0;
+ }
+
+ /**
+ * Mark as place on a country border
+ * @param onCountryBorder
+ */
+ public void setOnCountryBorder(boolean onCountryBorder) {
+ if (onCountryBorder)
+ this.flags |= ON_COUNTRY_BORDER;
+ else
+ this.flags &= ~ON_COUNTRY_BORDER;
+ }
+
public int hashCode() {
// Use a factor for latitude to span over the whole integer range:
// max lat: 4194304
@@ -682,7 +701,7 @@ public class Coord implements Comparable<Coord> {
* @return true if rounding error is large.
*/
public boolean hasAlternativePos(){
- if (getOnBoundary())
+ if (getOnBoundary() || getOnCountryBorder())
return false;
return (Math.abs(latDelta) > MAX_DELTA || Math.abs(lonDelta) > MAX_DELTA);
}
@@ -694,7 +713,7 @@ public class Coord implements Comparable<Coord> {
*/
public List<Coord> getAlternativePositions(){
ArrayList<Coord> list = new ArrayList<>();
- if (getOnBoundary())
+ if (getOnBoundary() || getOnCountryBorder())
return list;
int modLatDelta = 0;
int modLonDelta = 0;
=====================================
src/uk/me/parabola/imgfmt/app/CoordNode.java
=====================================
@@ -32,19 +32,22 @@ public class CoordNode extends Coord {
* @param longitude The longitude in map units.
* @param id The ID of this routing node.
* @param boundary This is a routing node on the boundary.
+ * @param onCountryBorder This is a routing node on a country boundary.
*/
- public CoordNode(int latitude, int longitude, int id, boolean boundary) {
+ public CoordNode(int latitude, int longitude, int id, boolean boundary, boolean onCountryBorder) {
super(latitude, longitude);
this.id = id;
setOnBoundary(boundary);
+ setOnCountryBorder(onCountryBorder);
setNumberNode(true);
preserved(true);
}
- public CoordNode(Coord other, int id, boolean boundary){
+ public CoordNode(Coord other, int id, boolean boundary, boolean onCountryBorder) {
super(other);
this.id = id;
setOnBoundary(boundary);
+ setOnCountryBorder(onCountryBorder);
setNumberNode(true);
preserved(true);
=====================================
src/uk/me/parabola/imgfmt/app/net/RouteNode.java
=====================================
@@ -76,7 +76,7 @@ public class RouteNode implements Comparable<RouteNode> {
public RouteNode(Coord coord) {
this.coord = (CoordNode) coord;
- setBoundary(this.coord.getOnBoundary());
+ setBoundary(this.coord.getOnBoundary() || this.coord.getOnCountryBorder());
}
private boolean haveLargeOffsets() {
=====================================
src/uk/me/parabola/imgfmt/app/trergn/RGNFileReader.java
=====================================
@@ -403,7 +403,7 @@ public class RGNFileReader extends ImgReader {
Utils.toDegrees(currLon)));
if (extra)
- line.addCoord(new CoordNode(currLat, currLon, 0/* XXX */, false));
+ line.addCoord(new CoordNode(currLat, currLon, 0/* XXX */, false, false));
else
line.addCoord(new Coord(currLat, currLon));
@@ -478,7 +478,7 @@ public class RGNFileReader extends ImgReader {
currLon += dx << (24 - div.getResolution());
Coord coord;
if (isnode)
- coord = new CoordNode(currLat, currLon, 0/* XXX */, false);
+ coord = new CoordNode(currLat, currLon, 0/* XXX */, false, false);
else
coord = new Coord(currLat, currLon);
=====================================
src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java
=====================================
@@ -68,10 +68,6 @@ public class DouglasPeuckerFilter implements MapFilter {
int endIndex = coords.size()-1;
for(int i = endIndex-1; i > 0; i--) {
Coord p = coords.get(i);
- //int highwayCount = p.getHighwayCount();
-
- // If a node in the line use the douglas peucker algorithm for upper segment
- // TODO: Should consider only nodes connected to roads visible at current resolution.
if (p.preserved()) {
// point is "preserved", don't remove it
douglasPeucker(coords, i, endIndex, maxErrorDistance);
@@ -100,18 +96,17 @@ public class DouglasPeuckerFilter implements MapFilter {
*/
public static void douglasPeucker(List<Coord> points, int startIndex, int endIndex, double allowedError)
{
- if (startIndex >= endIndex)
+ if (endIndex - startIndex <= 1) {
return;
-
+ }
+
double maxDistance = 0; //Highest distance
int maxIndex = endIndex; //Index of highest distance
Coord a = points.get(startIndex);
Coord b = points.get(endIndex);
-
// Find point with highest distance to line between start- and end-point.
- // handle also closed or nearly closed lines and spikes on straight lines
for(int i = endIndex-1; i > startIndex; i--) {
Coord p = points.get(i);
double distance = p.shortestDistToLineSegment(a, b);
@@ -127,19 +122,13 @@ public class DouglasPeuckerFilter implements MapFilter {
}
else {
// All points in tolerance, delete all of them.
- // Remove the end-point if it is the same as the start point
- if (a.highPrecEquals(b) && points.get(endIndex).preserved() == false)
- endIndex++;
-
- if (endIndex - startIndex > 4){
+ if (endIndex - startIndex > 4) {
// faster than many repeated remove actions
- points.subList(startIndex+1, endIndex).clear();
- return;
- }
-
- // Remove the points in between
- for (int i = endIndex - 1; i > startIndex; i--) {
- points.remove(i);
+ points.subList(startIndex + 1, endIndex).clear();
+ } else {
+ for (int i = endIndex - 1; i > startIndex; i--) {
+ points.remove(i);
+ }
}
}
}
=====================================
src/uk/me/parabola/mkgmap/filters/RoundCoordsFilter.java
=====================================
@@ -55,7 +55,7 @@ public class RoundCoordsFilter implements MapFilter {
Coord newP;
if(p instanceof CoordNode && checkRouting)
- newP = new CoordNode(lat, lon, p.getId(), p.getOnBoundary());
+ newP = new CoordNode(lat, lon, p.getId(), p.getOnBoundary(), p.getOnCountryBorder());
else
newP = new Coord(lat, lon);
newP.preserved(p.preserved());
=====================================
src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
=====================================
@@ -25,12 +25,16 @@ import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
+import java.util.Set;
import java.util.Map.Entry;
import java.util.logging.Level;
+import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
import uk.me.parabola.imgfmt.ExitException;
+import uk.me.parabola.imgfmt.Utils;
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.imgfmt.app.CoordNode;
@@ -60,6 +64,7 @@ import uk.me.parabola.mkgmap.reader.osm.Element;
import uk.me.parabola.mkgmap.reader.osm.FakeIdGenerator;
import uk.me.parabola.mkgmap.reader.osm.FeatureKind;
import uk.me.parabola.mkgmap.reader.osm.GType;
+import uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation;
import uk.me.parabola.mkgmap.reader.osm.Node;
import uk.me.parabola.mkgmap.reader.osm.OsmConverter;
import uk.me.parabola.mkgmap.reader.osm.Relation;
@@ -70,6 +75,7 @@ import uk.me.parabola.mkgmap.reader.osm.TagDict;
import uk.me.parabola.mkgmap.reader.osm.Tags;
import uk.me.parabola.mkgmap.reader.osm.TypeResult;
import uk.me.parabola.mkgmap.reader.osm.Way;
+import uk.me.parabola.util.ElementQuadTree;
import uk.me.parabola.util.EnhancedProperties;
import uk.me.parabola.util.MultiHashMap;
@@ -112,7 +118,13 @@ public class StyledConverter implements OsmConverter {
public final static String WAY_POI_NODE_IDS = "mkgmap:way-poi-node-ids";
private final HashMap<Integer, Map<String,MapPoint>> pointMap;
-
+
+ /** boundary ways with admin_level=2 */
+ private final Set<Way> borders = new LinkedHashSet<>();
+ private boolean addBoundaryNodesAtAdminBoundaries;
+ private int admLevelNod3;
+
+
private List<ConvertedWay> roads = new ArrayList<>();
private List<ConvertedWay> lines = new ArrayList<>();
private HashMap<Long, ConvertedWay> modifiedRoads = new HashMap<>();
@@ -210,6 +222,10 @@ public class StyledConverter implements OsmConverter {
String styleOption= props.getProperty("style-option",null);
styleOptionTags = parseStyleOption(styleOption);
prefixSuffixFilter = new PrefixSuffixFilter(props);
+
+ // control calculation of extra nodes in NOD3 / NOD4
+ admLevelNod3 = props.getProperty("add-boundary-nodes-at-admin-boundaries", 2);
+ addBoundaryNodesAtAdminBoundaries = routable && admLevelNod3 > 0;
}
/**
@@ -308,6 +324,13 @@ public class StyledConverter implements OsmConverter {
removeRestrictionsWithWay(Level.WARNING, way, "is ignored");
return;
}
+ if (addBoundaryNodesAtAdminBoundaries) {
+ // is this a country border ?
+ if (!FakeIdGenerator.isFakeId(way.getId()) && isNod3Border(way)) {
+ borders.add(way);
+ }
+ }
+
preConvertRules(way);
String styleFilterTag = way.getTag(styleFilterTagKey);
@@ -372,6 +395,20 @@ public class StyledConverter implements OsmConverter {
}
}
+ private boolean isNod3Border(Element el) {
+ if ("administrative".equals(el.getTag("boundary"))) {
+ String admLevelString = el.getTag("admin_level");
+ if (admLevelString != null) {
+ try {
+ int al = Integer.valueOf(admLevelString);
+ return al <= admLevelNod3;
+ } catch (NumberFormatException e) {
+ }
+ }
+ }
+ return false;
+ }
+
private int lineIndex = 0;
private final static short onewayTagKey = TagDict.getInstance().xlate("oneway");
private void addConvertedWay(Way way, GType foundType) {
@@ -431,6 +468,7 @@ public class StyledConverter implements OsmConverter {
/** One type result for nodes to avoid recreating one for each node. */
private NodeTypeResult nodeTypeResult = new NodeTypeResult();
+
private class NodeTypeResult implements TypeResult {
private Node node;
/** flag if the rule was fired */
@@ -582,6 +620,124 @@ public class StyledConverter implements OsmConverter {
}
}
+ /**
+ * Find all intersections of roads with country borders.
+ * If a node exists close to the intersection, use the existing node, else add one. The nodes will be
+ * written as external nodes to NOD file (NOD3 + NOD4)
+ */
+ private void checkRoutingNodesAtAdminBoundaries() {
+ if (!addBoundaryNodesAtAdminBoundaries || borders.isEmpty())
+ return;
+ long t1 = System.currentTimeMillis();
+
+ // prepare boundary ways so that we can search them
+ List<Element> clippedBorders = new ArrayList<>();
+ for (Way b : borders) {
+ List<List<Coord>> clipped = LineClipper.clip(bbox, b.getPoints());
+ if (clipped == null) {
+ splitBoundary(clippedBorders, b, b.getPoints());
+ } else {
+ for (List<Coord> lco : clipped) {
+ splitBoundary(clippedBorders, b, lco);
+ }
+ }
+ }
+ ElementQuadTree qt = new ElementQuadTree(bbox, clippedBorders);
+
+ long countChg = 0;
+ Long2ObjectOpenHashMap<Coord> commonCoordMap = new Long2ObjectOpenHashMap<>();
+ for (ConvertedWay r : roads) {
+ if (!r.isValid())
+ continue;
+ Way way = r.getWay();
+ Area searchRect = Area.getBBox(way.getPoints());
+ Set<Element> boundaries = qt.get(searchRect);
+ if (boundaries.isEmpty())
+ continue;
+
+ // the bounding box of the road intersects with one or more bounding boxes of borders
+ Coord pw1 = way.getPoints().get(0);
+ int pos = 1;
+ while (pos < way.getPoints().size()) {
+ boolean changed = false;
+ Coord pw2 = way.getPoints().get(pos);
+ for (Element el : boundaries) {
+ List<Coord> b = ((Way) el).getPoints();
+ for (int i = 0; i < b.size() - 1; i++) {
+ Coord pb1 = b.get(i);
+ Coord pb2 = b.get(i + 1);
+ Coord is = Utils.getSegmentSegmentIntersection(pw1, pw2, pb1, pb2);
+ if (is != null) {
+ // intersection can be equal to given nodes on road or close to it
+ double dist1 = is.distance(pw1);
+ double dist2 = is.distance(pw2);
+ if (dist1 < dist2 && dist1 < 1) {
+ if (!pw1.getOnCountryBorder()) {
+ ++countChg;
+ if (!pw1.getOnBoundary())
+ log.info("road intersects admin boundary, changing existing node to external routing node at",pw1.toDegreeString());
+ }
+ pw1.setOnCountryBorder(true);
+ } else if (dist2 < dist1 && dist2 < 1) {
+ if (!pw2.getOnCountryBorder()) {
+ ++countChg;
+ if (!pw2.getOnBoundary())
+ log.info("road intersects admin boundary, changing existing node to external routing node at",pw2.toDegreeString());
+ }
+ pw2.setOnCountryBorder(true);
+ } else {
+ long key = Utils.coord2Long(is);
+ Coord replacement = commonCoordMap.get(key);
+ if (replacement == null) {
+ commonCoordMap.put(key, is);
+ } else {
+ assert is.highPrecEquals(replacement);
+ is = replacement;
+ }
+ is.setOnCountryBorder(true);
+ log.info("road intersects admin boundary, adding external routing node at",is.toDegreeString());
+
+ way.getPoints().add(pos, is);
+ changed = true;
+ pw2 = is;
+ }
+ }
+ }
+ }
+ if (!changed) {
+ ++pos;
+ pw1 = pw2;
+ }
+ }
+ }
+ long t2 = System.currentTimeMillis() - t1;
+ log.info("added",commonCoordMap.size(),"new nodes at country borders");
+ log.info("marked",countChg,"existing nodes at country borders");
+ log.info("adding country border routing nodes took " + t2 + " ms");
+
+ }
+
+ /**
+ * Split complex border ways into smaller portions.
+ * @param clippedBorders
+ * @param orig
+ * @param points
+ */
+ private void splitBoundary(List<Element> clippedBorders, Way orig, List<Coord> points) {
+ int pos = 0;
+ final int max = 20; // seems to be a good compromise
+ while (pos < points.size()) {
+ int right = Math.min(points.size(), pos + max);
+ Way w = new Way(orig.getId(), points.subList(pos, right));
+ w.setFakeId();
+ clippedBorders.add(w);
+ pos += max - 1;
+ if (pos + 1 == points.size())
+ pos--;
+ }
+ }
+
+
/**
* Merges roads with identical attributes (GType, OSM tags) to reduce the size of the
* road network.
@@ -601,6 +757,9 @@ public class StyledConverter implements OsmConverter {
style.reportStats();
driveOnLeft = calcDrivingSide();
+ checkRoutingNodesAtAdminBoundaries();
+ borders.clear();
+
setHighwayCounts();
findUnconnectedRoads();
rotateClosedWaysToFirstNode();
@@ -636,7 +795,6 @@ public class StyledConverter implements OsmConverter {
}
deletedRoads = null;
modifiedRoads = null;
-
mergeRoads();
resetHighwayCounts();
@@ -961,6 +1119,17 @@ public class StyledConverter implements OsmConverter {
}
else if("through_route".equals(relation.getTag("type"))) {
throughRouteRelations.add(relation);
+ } else if (addBoundaryNodesAtAdminBoundaries) {
+ if (relation instanceof MultiPolygonRelation || "boundary".equals(relation.getTag("type"))) {
+ if (isNod3Border(relation)) {
+ for (Entry<String, Element> e : relation.getElements()) {
+ if (FakeIdGenerator.isFakeId(e.getValue().getId()))
+ continue;
+ if (e.getValue() instanceof Way)
+ borders.add((Way) e.getValue());
+ }
+ }
+ }
}
}
@@ -1361,7 +1530,7 @@ public class StyledConverter implements OsmConverter {
nWay.copyTags(way);
for(Coord co : lco) {
nWay.addPoint(co);
- if(co.getOnBoundary()) {
+ if(co.getOnBoundary() || co.getOnCountryBorder()) {
// this point lies on a boundary
// make sure it becomes a node
co.incHighwayCount();
@@ -1631,12 +1800,12 @@ public class StyledConverter implements OsmConverter {
arcLength += d;
}
}
- if(p.getHighwayCount() > 1) {
+ if(p.getHighwayCount() > 1 || p.getOnCountryBorder()) {
// this point is a node connecting highways
CoordNode coordNode = nodeIdMap.get(p);
if(coordNode == null) {
// assign a node id
- coordNode = new CoordNode(p, nextNodeId++, p.getOnBoundary());
+ coordNode = new CoordNode(p, nextNodeId++, p.getOnBoundary(), p.getOnCountryBorder());
nodeIdMap.put(p, coordNode);
}
@@ -1751,7 +1920,7 @@ public class StyledConverter implements OsmConverter {
Coord coord = points.get(n);
CoordNode thisCoordNode = nodeIdMap.get(coord);
assert thisCoordNode != null : "Way " + debugWayName + " node " + i + " (point index " + n + ") at " + coord.toOSMURL() + " yields a null coord node";
- boolean boundary = coord.getOnBoundary();
+ boolean boundary = coord.getOnBoundary() || coord.getOnCountryBorder();
if(boundary && log.isInfoEnabled()) {
log.info("Way", debugWayName + "'s point #" + n, "at", coord.toOSMURL(), "is a boundary node");
}
=====================================
src/uk/me/parabola/mkgmap/osmstyle/WrongAngleFixer.java
=====================================
@@ -149,6 +149,13 @@ public class WrongAngleFixer {
}
replacement.setOnBoundary(true);
}
+ if (toRepl.getOnCountryBorder()){
+ if (replacement.equals(toRepl) == false){
+ log.error("country boundary node is replaced by node with non-equal coordinates at", toRepl.toOSMURL());
+ assert false : "country boundary node is replaced" ;
+ }
+ replacement.setOnCountryBorder(true);
+ }
toRepl.setReplaced(true);
if (toRepl instanceof CoordPOI) {
CoordPOI cp = (CoordPOI) toRepl;
@@ -834,7 +841,7 @@ public class WrongAngleFixer {
* @return true if remove is okay
*/
private boolean allowedToRemove(Coord p){
- if (p.getOnBoundary())
+ if (p.getOnBoundary() || p.getOnCountryBorder())
return false;
if (mode == MODE_LINES && p.isEndOfWay())
return false;
@@ -1100,26 +1107,27 @@ public class WrongAngleFixer {
}
Coord c = getCurrentLocation(replacements);
Coord n = neighbour.getCurrentLocation(replacements);
-
// check special cases: don't merge if
// 1) both points are via nodes
// 2) both nodes are boundary nodes with non-equal coords
// 3) one point is via node and the other is a boundary node, the result could be that the restriction is ignored.
- if (c.getOnBoundary()){
- if (n.isViaNodeOfRestriction() || n.getOnBoundary() && c.equals(n) == false)
+ boolean cOnBoundary = c.getOnBoundary() || c.getOnCountryBorder();
+ boolean nOnBoundary = n.getOnBoundary() || n.getOnCountryBorder();
+ if (cOnBoundary){
+ if (n.isViaNodeOfRestriction() || nOnBoundary && c.equals(n) == false)
return false;
}
- if (c.isViaNodeOfRestriction() && (n.isViaNodeOfRestriction() || n.getOnBoundary()))
+ if (c.isViaNodeOfRestriction() && (n.isViaNodeOfRestriction() || nOnBoundary))
return false;
- if (c instanceof CoordPOI && (n instanceof CoordPOI || n.getOnBoundary()))
+ if (c instanceof CoordPOI && (n instanceof CoordPOI || nOnBoundary))
return false;
- if (n instanceof CoordPOI && (c instanceof CoordPOI || c.getOnBoundary()))
+ if (n instanceof CoordPOI && (c instanceof CoordPOI || cOnBoundary))
return false;
-
+ //TODO: nodes on country borders?
Coord mergePoint;
- if (c.getOnBoundary() || c instanceof CoordPOI)
+ if (cOnBoundary || c instanceof CoordPOI)
mergePoint = c;
- else if (n.getOnBoundary() || n instanceof CoordPOI)
+ else if (nOnBoundary || n instanceof CoordPOI)
mergePoint = n;
else if (c.equals(n))
mergePoint = c;
=====================================
src/uk/me/parabola/mkgmap/osmstyle/housenumber/ExtNumbers.java
=====================================
@@ -944,6 +944,7 @@ public class ExtNumbers {
Coord closePoint = getRoad().getPoints().get(index);
Coord toAdd = new Coord(closePoint);
toAdd.setOnBoundary(closePoint.getOnBoundary());
+ toAdd.setOnCountryBorder(closePoint.getOnCountryBorder());
toAdd.incHighwayCount();
// we have to make sure that the road starts and ends with a CoordNode!
this.endInRoad = addAsNumberNode(splitSegment, toAdd);
=====================================
src/uk/me/parabola/mkgmap/reader/osm/CoastlineFileLoader.java
=====================================
@@ -152,26 +152,7 @@ public final class CoastlineFileLoader {
if (log.isDebugEnabled())
log.debug("Create coastline way", id, "with", points.size(),
"points");
- Coord firstPoint = getPoints().get(0);
-
- int minLat = firstPoint.getLatitude();
- int maxLat = firstPoint.getLatitude();
- int minLong = firstPoint.getLongitude();
- int maxLong = firstPoint.getLongitude();
-
- for (Coord c : getPoints()) {
- if (c.getLatitude() < minLat) {
- minLat = c.getLatitude();
- } else if (c.getLatitude() > maxLat) {
- maxLat = c.getLatitude();
- }
- if (c.getLongitude() < minLong) {
- minLong = c.getLongitude();
- } else if (c.getLongitude() > maxLong) {
- maxLong = c.getLongitude();
- }
- }
- bbox = new Area(minLat, minLong, maxLat, maxLong);
+ bbox = Area.getBBox(points);
}
@Override
=====================================
src/uk/me/parabola/mkgmap/reader/osm/ElementSaver.java
=====================================
@@ -66,10 +66,8 @@ public class ElementSaver {
// Options
private final boolean ignoreTurnRestrictions;
- /** name of the tag that contains a ;-separated list of tagnames that should be removed after all elements have been processed */
- public static final String MKGMAP_REMOVE_TAG = "mkgmap:removetags";
- /** tagvalue of the {@link ElementSaver#MKGMAP_REMOVE_TAG} if all tags should be removed */
- public static final String MKGMAP_REMOVE_TAG_ALL_KEY = "mkgmap:ALL";
+ /** name of the tag that contains a ;-separated list of tag names that should be removed after all elements have been processed */
+ public static final short MKGMAP_REMOVE_TAG_KEY = TagDict.getInstance().xlate("mkgmap:removetags");
public ElementSaver(EnhancedProperties args) {
if (args.getProperty("preserve-element-order", false)) {
=====================================
src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonFinishHook.java
=====================================
@@ -34,22 +34,17 @@ public class MultiPolygonFinishHook extends OsmReadingHooksAdaptor {
long t1 = System.currentTimeMillis();
log.info("Finishing multipolygons");
for (Way way : saver.getWays().values()) {
- String removeTag = way.getTag(ElementSaver.MKGMAP_REMOVE_TAG);
+ String removeTag = way.getTag(ElementSaver.MKGMAP_REMOVE_TAG_KEY);
if (removeTag == null) {
continue;
}
- if (ElementSaver.MKGMAP_REMOVE_TAG_ALL_KEY.equals(removeTag)) {
- if (log.isDebugEnabled())
- log.debug("Remove all tags from way",way.getId(),way.toTagString());
- way.removeAllTags();
- } else {
- String[] tagsToRemove = removeTag.split(";");
- if (log.isDebugEnabled())
- log.debug("Remove tags",Arrays.toString(tagsToRemove),"from way",way.getId(),way.toTagString());
- for (String rTag : tagsToRemove) {
- way.deleteTag(rTag);
- }
- way.deleteTag(ElementSaver.MKGMAP_REMOVE_TAG);
+ String[] tagsToRemove = removeTag.split(";");
+ if (log.isDebugEnabled()) {
+ log.debug("Remove tags",Arrays.toString(tagsToRemove),"from way",way.getId(),way.toTagString());
+ }
+ way.deleteTag(ElementSaver.MKGMAP_REMOVE_TAG_KEY);
+ for (String rTag : tagsToRemove) {
+ way.deleteTag(rTag);
}
}
log.info("Multipolygon hook finished in "+(System.currentTimeMillis()-t1)+" ms");
=====================================
src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
=====================================
@@ -18,6 +18,7 @@ import java.awt.Rectangle;
import java.awt.geom.Area;
import java.awt.geom.Line2D;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
@@ -37,7 +38,6 @@ import java.util.Set;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.logging.Level;
-import uk.me.parabola.imgfmt.Utils;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;
import uk.me.parabola.util.Java2DConverter;
@@ -1632,7 +1632,7 @@ public class MultiPolygonRelation extends Relation {
|| (prevLatField == 0 && prevLonField == 0);
boolean intersects = intersectionPossible
- && Utils.linesCutEachOther(p1_1, p1_2, p2_1, p2_2);
+ && linesCutEachOther(p1_1, p1_2, p2_1, p2_2);
if (intersects) {
if ((polygon1.getWay().isClosedArtificially() && !it1.hasNext())
@@ -1725,12 +1725,54 @@ public class MultiPolygonRelation extends Relation {
Coord sw = new Coord(tileBounds.getMinLat(), tileBounds.getMinLong());
Coord se = new Coord(tileBounds.getMinLat(), tileBounds.getMaxLong());
Coord ne = new Coord(tileBounds.getMaxLat(), tileBounds.getMaxLong());
- return Utils.linesCutEachOther(nw, sw, p1_1, p1_2)
- || Utils.linesCutEachOther(sw, se, p1_1, p1_2)
- || Utils.linesCutEachOther(se, ne, p1_1, p1_2)
- || Utils.linesCutEachOther(ne, nw, p1_1, p1_2);
+ return linesCutEachOther(nw, sw, p1_1, p1_2)
+ || linesCutEachOther(sw, se, p1_1, p1_2)
+ || linesCutEachOther(se, ne, p1_1, p1_2)
+ || linesCutEachOther(ne, nw, p1_1, p1_2);
}
+ /**
+ * XXX: This code presumes that certain tests were already done!
+ * Check if the line p1_1 to p1_2 cuts line p2_1 to p2_2 in two pieces and vice versa.
+ * This is a form of intersection check where it is allowed that one line ends on the
+ * other line or that the two lines overlap.
+ * @param p1_1 first point of line 1
+ * @param p1_2 second point of line 1
+ * @param p2_1 first point of line 2
+ * @param p2_2 second point of line 2
+ * @return true if both lines intersect somewhere in the middle of each other
+ */
+ private static boolean linesCutEachOther(Coord p1_1, Coord p1_2, Coord p2_1, Coord p2_2) {
+ long width1 = p1_2.getHighPrecLon() - p1_1.getHighPrecLon();
+ long width2 = p2_2.getHighPrecLon() - p2_1.getHighPrecLon();
+
+ long height1 = p1_2.getHighPrecLat() - p1_1.getHighPrecLat();
+ long height2 = p2_2.getHighPrecLat() - p2_1.getHighPrecLat();
+
+ long denominator = ((height2 * width1) - (width2 * height1));
+ if (denominator == 0) {
+ // the lines are parallel
+ // they might overlap but this is ok for this test
+ return false;
+ }
+
+ long x1Mx3 = p1_1.getHighPrecLon() - p2_1.getHighPrecLon();
+ long y1My3 = p1_1.getHighPrecLat() - p2_1.getHighPrecLat();
+
+ double isx = (double)((width2 * y1My3) - (height2 * x1Mx3))
+ / denominator;
+ if (isx <= 0 || isx >= 1) {
+ return false;
+ }
+
+ double isy = (double)((width1 * y1My3) - (height1 * x1Mx3))
+ / denominator;
+
+ if (isy <= 0 || isy >= 1) {
+ return false;
+ }
+ return true;
+ }
private List<JoinedWay> getWaysFromPolygonList(BitSet selection) {
if (selection.isEmpty()) {
@@ -1873,11 +1915,9 @@ public class MultiPolygonRelation extends Relation {
* @param way
* a joined way
* @param tagname
- * the tag to be removed (<code>null</code> means remove all
- * tags)
+ * the tag to be removed
* @param tagvalue
- * the value of the tag to be removed (<code>null</code> means
- * don't check the value)
+ * the value of the tag to be removed
*/
private void removeTagInOrgWays(JoinedWay way, String tagname,
String tagvalue) {
@@ -1888,54 +1928,33 @@ public class MultiPolygonRelation extends Relation {
continue;
}
- boolean remove = false;
- if (tagname == null) {
- // remove all tags
- remove = true;
- } else if (tagvalue == null) {
- // remove the tag without comparing the value
- remove = w.getTag(tagname) != null;
- } else if (tagvalue.equals(w.getTag(tagname))) {
- remove = true;
- }
-
- if (remove) {
- if (tagname == null) {
- // remove all tags
- if (log.isDebugEnabled())
- log.debug("Will remove all tags from", w.getId(), w
- .toTagString());
- removeTagsInOrgWays(w, tagname);
- } else {
- if (log.isDebugEnabled())
- log.debug("Will remove", tagname + "="
- + w.getTag(tagname), "from way", w.getId(), w
- .toTagString());
- removeTagsInOrgWays(w, tagname);
+ if (tagvalue.equals(w.getTag(tagname))) {
+ if (log.isDebugEnabled()) {
+ log.debug("Will remove", tagname + "=" + w.getTag(tagname), "from way", w.getId(), w.toTagString());
}
+ removeTagsInOrgWays(w, tagname);
}
}
}
protected void removeTagsInOrgWays(Way way, String tag) {
- if (tag == null) {
- way.addTag(ElementSaver.MKGMAP_REMOVE_TAG, ElementSaver.MKGMAP_REMOVE_TAG_ALL_KEY);
+ if (tag == null || tag.isEmpty()) {
return;
}
- if (tag.isEmpty()) {
- return;
- }
- String removedTagsTag = way.getTag(ElementSaver.MKGMAP_REMOVE_TAG);
- if (ElementSaver.MKGMAP_REMOVE_TAG_ALL_KEY.equals(removedTagsTag)) {
- // cannot add more tags to remove
+ String tagsToRemove = way.getTag(ElementSaver.MKGMAP_REMOVE_TAG_KEY);
+
+ if (tagsToRemove == null) {
+ tagsToRemove = tag;
+ } else if (tag.equals(tagsToRemove)) {
return;
- }
-
- if (removedTagsTag == null) {
- way.addTag(ElementSaver.MKGMAP_REMOVE_TAG, tag);
- } else if (removedTagsTag.equals(tag) == false) {
- way.addTag(ElementSaver.MKGMAP_REMOVE_TAG, removedTagsTag+";"+tag);
- }
+ } else {
+ String[] keys = tagsToRemove.split(";");
+ if (Arrays.asList(keys).contains(tag)) {
+ return;
+ }
+ tagsToRemove += ";" + tag;
+ }
+ way.addTag(ElementSaver.MKGMAP_REMOVE_TAG_KEY, tagsToRemove);
}
/**
=====================================
src/uk/me/parabola/mkgmap/reader/osm/RoutingHook.java
=====================================
@@ -63,6 +63,12 @@ public class RoutingHook extends OsmReadingHooksAdaptor {
usedTags.add("route");
usedTags.add("taxi");
}
+ int admLevelNod3 = props.getProperty("add-boundary-nodes-at-admin-boundaries", 2);
+ if (admLevelNod3 > 0) {
+ usedTags.add("boundary");
+ usedTags.add("admin_level");
+ }
+
// only enabled if the route option is set
return props.containsKey("route");
=====================================
src/uk/me/parabola/mkgmap/reader/osm/UnusedElementsRemoverHook.java
=====================================
@@ -100,6 +100,8 @@ public class UnusedElementsRemoverHook extends OsmReadingHooksAdaptor {
Rectangle bboxRect = new Rectangle(bbox.getMinLong(), bbox.getMinLat(), bbox.getWidth(), bbox.getHeight());
long ways = saver.getWays().size();
for (Way way : new ArrayList<Way>(saver.getWays().values())) {
+ if (way.isViaWay())
+ continue;
if (way.getPoints().isEmpty()) {
// empty way will not appear in the map => remove it
saver.getWays().remove(way.getId());
@@ -120,13 +122,6 @@ public class UnusedElementsRemoverHook extends OsmReadingHooksAdaptor {
// It is possible that the way is larger than the bounding box and therefore
// contains the bbox completely. Especially this is true for the sea polygon
// when using --generate-sea=polygon
- // So need the calc the bbox of the way
- Coord firstC = way.getPoints().get(0);
- int minLat = firstC.getLatitude();
- int maxLat = firstC.getLatitude();
- int minLong = firstC.getLongitude();
- int maxLong = firstC.getLongitude();
-
for (Coord c : way.getPoints()) {
if (bbox.contains(c)) {
coordInBbox = true;
@@ -144,23 +139,12 @@ public class UnusedElementsRemoverHook extends OsmReadingHooksAdaptor {
}
}
- if (minLat > c.getLatitude()) {
- minLat = c.getLatitude();
- } else if (maxLat < c.getLatitude()) {
- maxLat = c.getLatitude();
- }
- if (minLong > c.getLongitude()) {
- minLong = c.getLongitude();
- } else if (maxLong < c.getLongitude()) {
- maxLong = c.getLongitude();
- }
-
prevC = c;
}
if (coordInBbox==false) {
// no coord of the way is within the bounding box
// check if the way possibly covers the bounding box completely
- Area wayBbox = new Area(minLat, minLong, maxLat, maxLong);
+ Area wayBbox = Area.getBBox(way.getPoints());
if (wayBbox.contains(saver.getBoundingBox())) {
log.debug(way, "possibly covers the bbox completely. Keep it.");
} else {
=====================================
src/uk/me/parabola/mkgmap/reader/polish/RoadHelper.java
=====================================
@@ -150,7 +150,7 @@ class RoadHelper {
if (id == 0) {
CoordNode node = nodeCoords.get((long) ni.nodeId);
if (node == null) {
- node = new CoordNode(coord, ni.nodeId, ni.boundary);
+ node = new CoordNode(coord, ni.nodeId, ni.boundary, false);
nodeCoords.put((long) ni.nodeId, node);
}
points.set(n, node);
=====================================
src/uk/me/parabola/util/ElementQuadTree.java
=====================================
@@ -2,13 +2,11 @@ package uk.me.parabola.util;
import java.util.Collection;
import java.util.HashSet;
-import java.util.List;
+import java.util.LinkedHashSet;
import java.util.Set;
import uk.me.parabola.imgfmt.app.Area;
-import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.mkgmap.reader.osm.Element;
-import uk.me.parabola.util.ElementQuadTreeNode.ElementQuadTreePolygon;
public class ElementQuadTree {
@@ -18,42 +16,16 @@ public class ElementQuadTree {
this.root = new ElementQuadTreeNode(bbox, elements);
}
- public void remove(Element element) {
- root.remove(element);
- }
-
public Set<Element> get(Area bbox) {
- return root.get(bbox, new HashSet<Element>());
- }
-
- public Set<Element> get(java.awt.geom.Area polygon) {
- return root.get(new ElementQuadTreePolygon(polygon), new HashSet<Element>());
- }
-
- public Set<Element> get(Collection<List<Coord>> polygons) {
- return root.get(new ElementQuadTreePolygon(polygons),
- new HashSet<Element>());
+ HashSet<Element> res = new LinkedHashSet<>();
+ root.get(bbox, res);
+ return res;
}
public int getDepth() {
return root.getDepth();
}
- public Set<Element> get(List<Coord> polygon) {
- if (polygon.size() < 3) {
- return new HashSet<Element>();
- }
- if (polygon.get(0).equals(polygon.get(polygon.size() - 1)) == false) {
- return new HashSet<Element>();
- }
- return root.get(new ElementQuadTreePolygon(polygon),
- new HashSet<Element>());
- }
-
- public long getCoordSize() {
- return root.getSize();
- }
-
public boolean isEmpty() {
return root.isEmpty();
}
=====================================
src/uk/me/parabola/util/ElementQuadTreeNode.java
=====================================
@@ -14,96 +14,57 @@ package uk.me.parabola.util;
import java.awt.Rectangle;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collection;
-import java.util.Collections;
-import java.util.HashMap;
+import java.util.Iterator;
import java.util.List;
-import java.util.Map;
-import java.util.Map.Entry;
import java.util.Set;
import uk.me.parabola.imgfmt.app.Area;
-import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.reader.osm.Element;
import uk.me.parabola.mkgmap.reader.osm.Node;
import uk.me.parabola.mkgmap.reader.osm.Way;
+/**
+ * A quad tree node. All nodes in the tree can contain elements. The element is stored in the node when its bbox is too large to fit into a single child.
+ * @author Gerd Petermann
+ *
+ */
public final class ElementQuadTreeNode {
private static final Logger log = Logger.getLogger(ElementQuadTreeNode.class);
- /**
- * A static empty list used for node objects. They have one coord only and
- * it is too costly to create a list for each node
- */
- private static final List<Coord> EMPTY_LIST = Collections.emptyList();
-
/** The maximum number of coords in the quadtree node. */
private static final int MAX_POINTS = 1000;
- /** Maps elements to its coords located in this quadtree node. */
- private Map<Element, List<Coord>> elementMap;
+ private List<BoxedElement> elementList; // can be null
/** The bounds of this quadtree node */
private final Area bounds;
private final Rectangle boundsRect;
- /** Flag if this node and all subnodes are empty */
+ /** Flag if this node and all sub-nodes are empty */
private Boolean empty;
- /** The subnodes in case this node is not a leaf */
+ /** The sub-nodes in case this node is not a leaf */
private ElementQuadTreeNode[] children;
- public static final class ElementQuadTreePolygon {
- private final java.awt.geom.Area javaArea;
- private final Area bbox;
-
- public ElementQuadTreePolygon(java.awt.geom.Area javaArea) {
- this.javaArea = javaArea;
- Rectangle bboxRect = javaArea.getBounds();
- bbox = new Area(bboxRect.y, bboxRect.x, bboxRect.y
- + bboxRect.height, bboxRect.x + bboxRect.width);
- }
-
- public ElementQuadTreePolygon(List<Coord> points) {
- this(Java2DConverter.createArea(points));
- }
-
- public ElementQuadTreePolygon(Collection<List<Coord>> polygonList) {
- this.javaArea = new java.awt.geom.Area();
- for (List<Coord> polygon : polygonList) {
- javaArea.add(Java2DConverter.createArea(polygon));
- }
- Rectangle bboxRect = javaArea.getBounds();
- bbox = new Area(bboxRect.y, bboxRect.x, bboxRect.y
- + bboxRect.height, bboxRect.x + bboxRect.width);
- }
-
- public Area getBbox() {
- return bbox;
- }
-
- public java.awt.geom.Area getArea() {
- return javaArea;
- }
- }
-
/**
- * Retrieves if this quadtree node (and all subnodes) contains any elements.
+ * Retrieves if this quadtree node (and all sub-nodes) contains any elements.
* @return <code>true</code> this quadtree node does not contain any elements; <code>false</code> else
*/
public boolean isEmpty() {
if (empty == null) {
- if (isLeaf()) {
- empty = elementMap.isEmpty();
+ if (elementList != null && !elementList.isEmpty()) {
+ empty = false;
} else {
empty = true;
for (ElementQuadTreeNode child : children) {
- if (child.isEmpty()==false) {
- empty = false;
- break;
- }
+ if (!child.isEmpty()) {
+ empty = false;
+ break;
+ }
}
}
}
@@ -112,27 +73,20 @@ public final class ElementQuadTreeNode {
/**
- * Retrieves the number of coords hold by this quadtree node and all subnodes.
+ * Retrieves the number of coords hold by this quadtree node and all sub-nodes.
* @return the number of coords
*/
- public long getSize() {
- if (isLeaf()) {
- int items = 0;
- for (List<Coord> points : elementMap.values()) {
- if (points == EMPTY_LIST) {
- items++;
- } else {
- items += points.size();
- }
- }
- return items;
- } else {
- int items = 0;
+ private long getSize() {
+ int items = 0;
+ for (BoxedElement bel : elementList) {
+ items += bel.getSize();
+ }
+ if (children != null) {
for (ElementQuadTreeNode child : children) {
- items += child.getSize();
+ items += child.getSize();
}
- return items;
}
+ return items;
}
/**
@@ -140,24 +94,22 @@ public final class ElementQuadTreeNode {
* @return the depth of this quadtree node
*/
public int getDepth() {
- if (isLeaf()) {
+ if (children == null)
return 1;
- } else {
- int maxDepth = 0;
- for (ElementQuadTreeNode node : children) {
- maxDepth = Math.max(node.getDepth(), maxDepth);
- }
- return maxDepth + 1;
+ int maxDepth = 0;
+ for (ElementQuadTreeNode node : children) {
+ maxDepth = Math.max(node.getDepth(), maxDepth);
}
+ return maxDepth + 1;
}
- private ElementQuadTreeNode(Area bounds, Map<Element, List<Coord>> elements) {
+ private ElementQuadTreeNode(Area bounds, List<BoxedElement> elements) {
this.bounds = bounds;
boundsRect = new Rectangle(bounds.getMinLong(), bounds.getMinLat(),
bounds.getWidth(), bounds.getHeight());
this.children = null;
- elementMap =elements;
- empty = elementMap.isEmpty();
+ elementList = elements;
+ empty = elementList.isEmpty();
checkSplit();
}
@@ -169,18 +121,13 @@ public final class ElementQuadTreeNode {
bounds.getWidth(), bounds.getHeight());
this.children = null;
- this.elementMap = new HashMap<Element, List<Coord>>(elements.size()*4/3+10);
+ this.elementList = new ArrayList<>();
for (Element el : elements) {
- if (el instanceof Way) {
- List<Coord> points = ((Way) el).getPoints();
- // no need to create a copy of the points because the list is never changed
- elementMap.put(el, points);
- } else if (el instanceof Node) {
- elementMap.put(el, EMPTY_LIST);
- }
+ BoxedElement bel = new BoxedElement(el);
+ elementList.add(bel);
}
- empty = elementMap.isEmpty();
+ empty = elementList.isEmpty();
checkSplit();
}
@@ -196,196 +143,32 @@ public final class ElementQuadTreeNode {
* Checks if this quadtree node exceeds the maximum size and splits it in such a case.
*/
private void checkSplit() {
- if (getSize() > MAX_POINTS) {
+ if (elementList != null && elementList.size() > 1 && getSize() > MAX_POINTS) {
split();
}
}
- /**
- * Removes the element with the given bounding box from this quadtree node and all subnodes.
- * @param elem the element to be removed
- * @param bbox the bounding box of the element
- */
- private void remove(Element elem, Area bbox) {
- if (bbox == null || isEmpty()) {
- return;
- }
- if (isLeaf()) {
- elementMap.remove(elem);
- empty = elementMap.isEmpty();
- } else {
- for (ElementQuadTreeNode child : children) {
- if (child.getBounds().intersects(bbox)) {
- child.remove(elem, bbox);
- if (child.isEmpty()) {
- // update the empty flag
- empty = null;
- }
- }
- }
- }
- }
-
- /**
- * Calculates the bounding box of the given element.
- * @param elem an element
- * @return the bounding box of the element
- */
- private Area getBbox(Element elem) {
- if (elem instanceof Node) {
- Coord c = ((Node) elem).getLocation();
- return new Area(c.getLatitude(), c.getLongitude(), c.getLatitude(),c.getLongitude());
- } else if (elem instanceof Way) {
- List<Coord> points = ((Way) elem).getPoints();
- if (points.isEmpty()) {
- return null;
- }
- Coord c = points.get(0);
- int minLat = c.getLatitude();
- int maxLat = c.getLatitude();
- int minLong = c.getLongitude();
- int maxLong = c.getLongitude();
- for (Coord co : points) {
- if (co.getLatitude() < minLat) {
- minLat = co.getLatitude();
- } else if (co.getLatitude() > maxLat) {
- maxLat = co.getLatitude();
- }
- if (co.getLongitude() < minLong) {
- minLong = co.getLongitude();
- } else if (co.getLongitude() > maxLong) {
- maxLong = co.getLongitude();
- }
- }
- return new Area(minLat,minLong, maxLat, maxLong);
- }
- return null;
- }
-
- /**
- * Removes the element from this quadtree node and all subnodes.
- * @param elem the element to be removed
- */
- public void remove(Element elem) {
- remove(elem, getBbox(elem));
- }
-
/**
* Retrieves all elements that intersects the given bounding box.
* @param bbox the bounding box
- * @param resultList results are stored in this collection
+ * @param resultSet results are stored in this collection
* @return the resultList
*/
- public Set<Element> get(Area bbox, Set<Element> resultList) {
- if (isEmpty()) {
- return resultList;
+ public void get(Area bbox, Set<Element> resultSet) {
+ if (isEmpty() || bbox.intersects(bounds) == false) {
+ return;
}
- if (isLeaf()) {
- if (bbox.getMinLat() <= bounds.getMinLat()
- && bbox.getMaxLat() >= bounds.getMaxLat()
- && bbox.getMinLong() <= bounds.getMinLong()
- && bbox.getMaxLong() >= bounds.getMaxLong()) {
-
- // the bounding box is contained completely in the bbox
- // => add all points without further check
- resultList.addAll(elementMap.keySet());
- } else {
- // check each point
- for (Entry<Element, List<Coord>> elem : elementMap.entrySet()) {
- if (elem.getKey() instanceof Node) {
- Node n = (Node) elem.getKey();
- if (bbox.contains(n.getLocation())) {
- resultList.add(n);
- }
- } else if (elem.getKey() instanceof Way) {
- // no need to check - the element is already in the result list
- if (resultList.contains(elem.getKey())) {
- continue;
- }
- for (Coord c : elem.getValue()) {
- if (bbox.contains(c)) {
- resultList.add(elem.getKey());
- break;
- }
- }
- }
- }
- }
- } else {
- for (ElementQuadTreeNode child : children) {
- if (child.isEmpty() == false
- && bbox.intersects(child.getBounds())) {
- resultList = child.get(bbox, resultList);
- }
+ if (elementList != null) {
+ for (BoxedElement bel : elementList) {
+ if (bbox.intersects(bel.getBBox()))
+ resultSet.add(bel.el);
}
}
- return resultList;
- }
-
- /**
- * Retrieves all elements that intersects the given polygon.
- * @param polygon the polygon
- * @param resultList results are stored in this collection
- * @return the resultList
- */
- public Set<Element> get(ElementQuadTreePolygon polygon,
- Set<Element> resultList) {
- if (isEmpty()) {
- return resultList;
- }
- if (polygon.getBbox().intersects(getBounds())) {
- if (isLeaf()) {
- for (Entry<Element, List<Coord>> elem : elementMap.entrySet()) {
- if (resultList.contains(elem.getKey())) {
- continue;
- }
- if (elem.getKey() instanceof Node) {
- Node n = (Node)elem.getKey();
- Coord c = n.getLocation();
- if (polygon.getArea().contains(c.getLongitude(),
- c.getLatitude())) {
- resultList.add(n);
- }
- } else if (elem.getKey() instanceof Way) {
- for (Coord c : elem.getValue()) {
- if (polygon.getArea().contains(c.getLongitude(),
- c.getLatitude())) {
- resultList.add(elem.getKey());
- break;
- }
- }
- }
- }
- } else {
- for (ElementQuadTreeNode child : children) {
- if (child.isEmpty()==false
- && polygon.getArea().intersects(
- child.getBoundsAsRectangle())) {
- java.awt.geom.Area subArea = (java.awt.geom.Area) polygon
- .getArea().clone();
-
- subArea.intersect(Java2DConverter.createBoundsArea(new Area(child.getBounds()
- .getMinLat() - 1, child.getBounds()
- .getMinLong() - 1, child.getBounds()
- .getMaxLat() + 1, child.getBounds()
- .getMaxLong() + 1))
- );
- child.get(new ElementQuadTreePolygon(subArea),
- resultList);
- }
- }
+ if (children != null) {
+ for (ElementQuadTreeNode child : children) {
+ child.get(bbox, resultSet);
}
}
- return resultList;
-
- }
-
- /**
- * Retrieves if this quadtree node is a leaf.
- * @return <code>true</code> this node is a leaf
- */
- public boolean isLeaf() {
- return elementMap != null;
}
/**
@@ -399,7 +182,6 @@ public final class ElementQuadTreeNode {
int halfLat = (bounds.getMinLat() + bounds.getMaxLat()) / 2;
int halfLong = (bounds.getMinLong() + bounds.getMaxLong()) / 2;
- children = new ElementQuadTreeNode[4];
Area[] childBounds = new Area[4];
childBounds[0] = new Area(bounds.getMinLat(), bounds.getMinLong(),
@@ -411,52 +193,67 @@ public final class ElementQuadTreeNode {
childBounds[3] = new Area(halfLat, halfLong, bounds.getMaxLat(),
bounds.getMaxLong());
- List<Map<Element, List<Coord>>> childElems = new ArrayList<Map<Element, List<Coord>>>(4);
+ List<List<BoxedElement>> childElems = new ArrayList<>();
for (int i = 0; i < 4; i++) {
- childElems.add(new HashMap<Element, List<Coord>>());
+ childElems.add(new ArrayList<>());
}
- for (Entry<Element,List<Coord>> elem : elementMap.entrySet()) {
- if (elem.getKey() instanceof Node) {
- Node node = (Node) elem.getKey();
- for (int i = 0; i < childBounds.length; i++) {
- if (childBounds[i].contains(node.getLocation())) {
- childElems.get(i).put(node, EMPTY_LIST);
+ boolean modified = false;
+ Iterator<BoxedElement> iter = elementList.iterator();
+ while (iter.hasNext()) {
+ BoxedElement bel = iter.next();
+ int count = 0;
+ int lastIndex = -1;
+ for (int i = 0; i < 4; i++) {
+ if (childBounds[i].intersects(bel.getBBox())) {
+ count++;
+ lastIndex = i;
+ if (childBounds[i].insideBoundary(bel.getBBox())) {
break;
}
}
- } else if (elem.getKey() instanceof Way) {
- List<List<Coord>> points = new ArrayList<List<Coord>>(4);
- for (int i = 0; i < 4; i++) {
- // usually ways are quite local
- // therefore there is a high probability that only one child is covered
- // dim the new list as the old list
- points.add(new ArrayList<Coord>(elem.getValue().size()));
- }
- for (Coord c : elem.getValue()) {
- for (int i = 0; i < childBounds.length; i++) {
- if (childBounds[i].contains(c)) {
- points.get(i).add(c);
- break;
- }
- }
- }
- for (int i = 0; i< 4; i++) {
- if (points.get(i).isEmpty()==false) {
- childElems.get(i).put(elem.getKey(), points.get(i));
- }
- }
+ }
+ if (count == 1) {
+ childElems.get(lastIndex).add(bel);
+ iter.remove();
+ modified = true;
}
}
-
- for (int i = 0; i < 4; i++) {
- children[i] = new ElementQuadTreeNode(childBounds[i], childElems.get(i));
+ if (modified) {
+ children = new ElementQuadTreeNode[4];
+ for (int i = 0; i < 4; i++) {
+ children[i] = new ElementQuadTreeNode(childBounds[i], childElems.get(i));
+ }
}
-
- elementMap = null;
+ if (elementList.isEmpty())
+ elementList = null;
}
public void clear() {
this.children = null;
- elementMap = new HashMap<Element, List<Coord>>();
+ elementList = null;
+ }
+
+ private class BoxedElement{
+ private Area bbox;
+ private final Element el;
+
+ Area getBBox() {
+ if (el instanceof Way) {
+ if (bbox == null)
+ bbox = Area.getBBox(((Way) el).getPoints());
+ return bbox;
+ }
+ return Area.getBBox(Arrays.asList(((Node) el).getLocation()));
+ }
+
+ BoxedElement(Element el) {
+ this.el = el;
+ }
+
+ int getSize() {
+ if (el instanceof Way)
+ return ((Way) el).getPoints().size();
+ return 1;
+ }
}
}
View it on GitLab: https://salsa.debian.org/debian-gis-team/mkgmap/compare/c555f4292996efd0d9f487c7ab9f7c78743f72fb...4697e8677bd1869f5a21e84a204e95917250b914
--
View it on GitLab: https://salsa.debian.org/debian-gis-team/mkgmap/compare/c555f4292996efd0d9f487c7ab9f7c78743f72fb...4697e8677bd1869f5a21e84a204e95917250b914
You're receiving this email because of your account on salsa.debian.org.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://alioth-lists.debian.net/pipermail/pkg-grass-devel/attachments/20180901/4279a567/attachment-0001.html>
More information about the Pkg-grass-devel
mailing list