Hi Gerd
There is something about "water.osm" that is breaking the original
logic of ShapeSplitter in a way I'm having trouble understanding. A
whole lot of points get assigned to 2 loops.
It doesn't seem to be related to multiple identical paths around the
cut-line, which should now work correctly with this patch - sorry about
the 2 failed attempts yesterday.
You mentioned slightly adjusting the high-prec values to help
shapeSplitter. I think it best not to do this. You'd have to get it
absolutely correct all the way through and, say, in cases where 3 lines
follow the same path it becomes impossible. Also the algo it makes some
decisions on very fine distinctions in areas which allow it to get rid
of spikes and similar and so this wouldn't happen.
Patch attached. with INFO/DEBUG enabled, it generates lots of gps
traces: original, the various loops either side of the cut-line and all
the resultant shapes.
Ticker
On Fri, 2021-05-28 at 05:03 +0000, Gerd Petermann wrote:
> Hi Ticker,
>
> I've probably not understood the problem before. I've added test code
> to find situations where the ShapeSplitter complains and I found a
> rather simple case where the ShapeMerger produces a self-crossing
> shape (see attached gpx). Now I have an idea what to look for.
>
> Gerd
>
> ________________________________________
> Von: mkgmap-dev <[email protected]> im Auftrag
> von Gerd Petermann <[email protected]>
> Gesendet: Donnerstag, 27. Mai 2021 18:14
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] special case where splitting fails without
> a log message
>
> Hi Ticker,
>
> I've attached my current state of work as patch for the branch.
> It fixes some bugs and merges shapes in a way that is less likely to
> produce long connections to islands.
>
> I think the main problem for shape splitter is when such a connection
> has a U-shape and the cut goes through it horizontally. But I'm just
> guessing...
>
> Gerd
>
> ________________________________________
> Von: mkgmap-dev <[email protected]> im Auftrag
> von Gerd Petermann <[email protected]>
> Gesendet: Donnerstag, 27. Mai 2021 17:59
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] special case where splitting fails without
> a log message
>
> Hi Ticker,
>
> JOSM shows the islands properly when you zoom in. And yes, it shows
> water on both sides of the connecting lines. Very simiar to the
> Garmin renderer.
> Does that help?
>
> Gerd
>
> ________________________________________
> Von: mkgmap-dev <[email protected]> im Auftrag
> von Ticker Berkin <[email protected]>
> Gesendet: Donnerstag, 27. Mai 2021 17:48
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] special case where splitting fails without
> a log message
>
> Hi Gerd
>
> I'm confused. After mp hole cutting and shape merging, I expect a
> single closed way that will have in/out lines, probably on top of
> each
> other, to connect each area that was a hole, eventually, to a point
> on
> the outside of the shape.
>
> However, JOSM does show the water band on the outside of what were
> the
> islands, and on both sides of the joining lines.
>
> Ticker
>
> On Thu, 2021-05-27 at 15:10 +0000, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > yes, sure. I've converted a gpx output to OSM. All polygons with
> > holes are not valid OSM ways, but they are very normal as MapShape.
> > Validator doesn't help much with these polygons.
> >
> > Gerd
> >
> > ________________________________________
> > Von: mkgmap-dev <[email protected]> im Auftrag
> > von Ticker Berkin <[email protected]>
> > Gesendet: Donnerstag, 27. Mai 2021 17:06
> > An: Development list for mkgmap
> > Betreff: Re: [mkgmap-dev] special case where splitting fails
> > without
> > a log message
> >
> > Hi Gerd
> >
> > JOSM gives a self-crossing way validation error on this.
> >
> > Ticker
> >
> > On Thu, 2021-05-27 at 14:53 +0000, Gerd Petermann wrote:
> > > Hi Ticker,
> > >
> > > no need to hurry ;)
> > > Here is one:
> > > https://files.mkgmap.org.uk/download/508/water.osm
> > >
> > > Gerd
> > >
> > > ________________________________________
> > > Von: mkgmap-dev <[email protected]> im
> > > Auftrag
> > > von Ticker Berkin <[email protected]>
> > > Gesendet: Donnerstag, 27. Mai 2021 16:47
> > > An: Development list for mkgmap
> > > Betreff: Re: [mkgmap-dev] special case where splitting fails
> > > without
> > > a log message
> > >
> > > Hi Gerd
> > >
> > > next patch also has a problem - sorry to waste your time.
> > > Can I have your test data.
> > >
> > > Ticker
> > >
> > > On Thu, 2021-05-27 at 14:33 +0000, Gerd Petermann wrote:
> > > > Hi Ticker,
> > > >
> > > > with my current test environment the patch doesn't improve the
> > > > result.
> > > > It reports some errors (the old code didn't always detect them)
> > > > and
> > > > eithers add or removes parts of the heavily merged shapes.
> > > >
> > > > I've inspected one shape and found no obvious problem. No point
> > > > is
> > > > visited more then twice, but 167 points are visited twice. Let
> > > > me
> > > > know if you need the data.
> > > >
> > > > Gerd
> > > >
> > > > ________________________________________
> > > > Von: mkgmap-dev <[email protected]> im
> > > > Auftrag
> > > > von Ticker Berkin <[email protected]>
> > > > Gesendet: Donnerstag, 27. Mai 2021 16:09
> > > > An: Development list for mkgmap
> > > > Betreff: Re: [mkgmap-dev] special case where splitting fails
> > > > without
> > > > a log message
> > > >
> > > > Thanks Gerd, that works for me
> > > >
> > > > Ticker
> > > >
> > > > On Thu, 2021-05-27 at 12:54 +0000, Gerd Petermann wrote:
> > > > > Hi Ticker,
> > > > >
> > > > > I first convert the gpx layer to a data layer, then add the
> > > > > tag
> > > > > natural=water
> > > > > Next execute validator which will complain that the way is
> > > > > not
> > > > > closed.
> > > > > Right click on that warning allows to "zoom to problem" .
> > > > > This tells you where the first point is.
> > > > >
> > > > > In the "OSM data" preferences I've enabled "Draw segment
> > > > > order
> > > > > numbers on selected way"
> > > > >
> > > > > Hope this helps.
> > > > >
> > > > > Gerd
> > > > >
> > > > > ________________________________________
> > > > > Von: mkgmap-dev <[email protected]> im
> > > > > Auftrag
> > > > > von Ticker Berkin <[email protected]>
> > > > > Gesendet: Donnerstag, 27. Mai 2021 14:21
> > > > > An: Development list for mkgmap
> > > > > Betreff: Re: [mkgmap-dev] special case where splitting fails
> > > > > without
> > > > > a log message
> > > > >
> > > > > Hi Gerd
> > > > >
> > > > > Trying to use JOSM to decide if a gpx trace represents a self
> > > > > -intersecting polygon is difficult. Is there a way of forcing
> > > > > it
> > > > > to
> > > > > consider it closed and then check itself? Failing that,
> > > > > number
> > > > > the
> > > > > points or segments somehow.
> > > > >
> > > > > Ticker
> > > > >
> > > > >
> > > > > _______________________________________________
> > > > > mkgmap-dev mailing list
> > > > > [email protected]
> > > > > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > > > > _______________________________________________
> > > > > mkgmap-dev mailing list
> > > > > [email protected]
> > > > > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > > > _______________________________________________
> > > > mkgmap-dev mailing list
> > > > [email protected]
> > > > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > > > _______________________________________________
> > > > mkgmap-dev mailing list
> > > > [email protected]
> > > > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > > _______________________________________________
> > > mkgmap-dev mailing list
> > > [email protected]
> > > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > > _______________________________________________
> > > mkgmap-dev mailing list
> > > [email protected]
> > > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > _______________________________________________
> > mkgmap-dev mailing list
> > [email protected]
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > _______________________________________________
> > mkgmap-dev mailing list
> > [email protected]
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> [email protected]
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> [email protected]
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> [email protected]
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Index: src/uk/me/parabola/util/ShapeSplitter.java
===================================================================
--- src/uk/me/parabola/util/ShapeSplitter.java (revision 4745)
+++ src/uk/me/parabola/util/ShapeSplitter.java (working copy)
@@ -12,21 +12,20 @@
*/
package uk.me.parabola.util;
+import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
import java.awt.Shape;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Rectangle2D;
+import java.util.ArrayList;
import java.util.Arrays;
+import java.util.List;
-// RWB new bits
-import java.util.ArrayList;
-import java.util.List;
-import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
import uk.me.parabola.imgfmt.Utils;
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
-
import uk.me.parabola.log.Logger;
+import uk.me.parabola.util.GpxCreator;
public class ShapeSplitter {
private static final Logger log = Logger.getLogger(ShapeSplitter.class);
@@ -321,14 +320,15 @@
* @param origList list of shapes to which we append new shapes formed from above
* @param fullArea of orig polygon. used for sign and handling of last line segment
*/
- private static void processLineList(List<MergeCloseHelper> lineInfo, List<List<Coord>> origList, long fullArea) {
+ private static int processLineList(List<MergeCloseHelper> lineInfo, List<List<Coord>> origList, long fullArea) {
+ int errorCount = 0;
if (origList == null) // never wanted this side
- return;
+ return errorCount;
MergeCloseHelper firstLine = lineInfo.get(0);
if (lineInfo.size() == 1) { // single shape that never crossed line
if (!firstLine.points.isEmpty()) // all on this side
firstLine.closeAppend(origList, false);
- return;
+ return errorCount;
}
// look at last item in list of lines
MergeCloseHelper lastLine = lineInfo.get(lineInfo.size()-1);
@@ -343,7 +343,7 @@
if (lineInfo.size() == 1) { // simple poly that crossed once and back
firstLine.setMoreInfo(0);
firstLine.closeAppend(origList, true);
- return;
+ return errorCount;
}
// Above were the simple cases - probably 99% of calls.
@@ -360,7 +360,7 @@
boolean someDirectionsNotSet = false;
int areaDirection = 0;
String diagMsg = "";
- for (MergeCloseHelper thisLine : lineInfo) {
+ for (MergeCloseHelper thisLine : lineInfo) {
thisLine.setMoreInfo(fullAreaSign);
if (thisLine.direction == 0)
someDirectionsNotSet = true;
@@ -382,20 +382,58 @@
}
if (!diagMsg.isEmpty()) {
log.warn(diagMsg, "Probably self-intersecting polygon", fullAreaSign, someDirectionsNotSet, areaDirection);
- for (MergeCloseHelper thisLine : lineInfo) {
- log.warn(thisLine);
- if (log.isDebugEnabled())
- for (Coord co : thisLine.points)
- log.debug("line", co, co.getHighPrecLat(), co.getHighPrecLon());
- }
+ ++errorCount;
}
lineInfo.sort(null);
+ errorCount += processDups(lineInfo);
int dummy = doLines(0, Integer.MAX_VALUE, null, lineInfo, origList);
assert dummy == lineInfo.size();
+ for (MergeCloseHelper thisLine : lineInfo)
+ errorCount += thisLine.errorCount;
+ return errorCount;
} // processLineList
+ private static int processDups(List<MergeCloseHelper> lineInfo) {
+ // find groups of duplicates, drop equal numbers of different direction (ie keep just 1)
+ int errorCount = 0; // shouldn't be any
+ List<MergeCloseHelper> newList = new ArrayList<>(lineInfo.size());
+ MergeCloseHelper forwardLine = null, backwardLine = null, lastIfDup = null;
+ int directionBalance = 0;
+ for (MergeCloseHelper thisLine : lineInfo) {
+ if (lastIfDup != null && (!thisLine.isDup || (thisLine.lowPoint != lastIfDup.lowPoint ||
+ thisLine.highPoint != lastIfDup.highPoint ||
+ Math.abs(thisLine.areaToLine) != Math.abs(lastIfDup.areaToLine)))) {
+ if (directionBalance > 0)
+ newList.add(forwardLine);
+ else if (directionBalance < 0)
+ newList.add(backwardLine);
+ directionBalance = 0;
+ }
+ if (thisLine.isDup) {
+ if (thisLine.direction > 0) {
+ forwardLine = thisLine;
+ ++directionBalance;
+ } else {
+ backwardLine = thisLine;
+ --directionBalance;
+ }
+ lastIfDup = thisLine;
+ } else {
+ newList.add(thisLine);
+ lastIfDup = null;
+ }
+ }
+ if (directionBalance > 0)
+ newList.add(forwardLine);
+ else if (directionBalance < 0)
+ newList.add(backwardLine);
+ if (newList.size() < lineInfo.size())
+ lineInfo = newList;
+ return errorCount;
+ } // removeDups
+
private static List<Coord> startLine(List<MergeCloseHelper> lineInfo) {
MergeCloseHelper thisLine = new MergeCloseHelper();
lineInfo.add(thisLine);
@@ -423,6 +461,8 @@
*/
private static class MergeCloseHelper implements Comparable<MergeCloseHelper> {
+ int errorCount = 0;
+ boolean isDup;
List<Coord> points;
int firstPoint, lastPoint;
long startingArea, endingArea; // from runningArea
@@ -469,15 +509,16 @@
cmp = other.highPoint - this.highPoint;
if (cmp != 0)
return cmp;
- // case where when have same start & end
- // return the shape as lower than the hole, to handle first
-// cmp = other.areaOrHole - this.areaOrHole;
- // Above is not reliable, there might be an earlier shape. try doing larger area first
- cmp = Long.compare(this.areaToLine * this.areaOrHole, other.areaToLine * other.areaOrHole);
+ // have same start & end. larger area first
+ cmp = Long.compare(Math.abs(other.areaToLine), Math.abs(this.areaToLine));
if (cmp != 0)
return cmp;
- log.warn("Lines hit divider at same points and have same area sign", "this:", this, "other:", other);
- // after this, don't think anthing else possible, but, for stability
+ // multiple lines appear to follow same path, some can be dropped after sort
+ this.isDup = true;
+ other.isDup = true;
+ // maybe don't need this, if good fix
+ //log.warn("Lines hit divider at same points and have same area", this);
+ // after this, don't think anything else possible, but, for stability
return this.direction - other.direction;
} // compareTo
@@ -485,11 +526,13 @@
if (other.areaToLine == 0)
return; // spike into this area. cf. closeAppend()
// shapes must have opposite directions.
- if (this.direction == 0 && other.direction == 0)
+ if (this.direction == 0 && other.direction == 0) {
log.warn("Direction of shape and hole indeterminate; probably self-intersecting polygon", "this:", this, "other:", other);
- else if (this.direction != 0 && other.direction != 0 && this.direction == other.direction)
+ ++errorCount;
+ } else if (this.direction != 0 && other.direction != 0 && this.direction == other.direction) {
log.warn("Direction of shape and hole conflict; probably self-intersecting polygon", "this:", this, "other:", other);
- else if (this.direction < 0 || other.direction > 0) {
+ ++errorCount;
+ } else if (this.direction < 0 || other.direction > 0) {
this.points.addAll(other.points);
if (this.direction == 0)
this.direction = -1;
@@ -557,8 +600,19 @@
List<List<Coord>> lessList, List<List<Coord>> moreList,
Long2ObjectOpenHashMap<Coord> coordPool) {
+ int errorCount = 0;
List<MergeCloseHelper> newLess = null, newMore = null;
List<Coord> lessPoly = null, morePoly = null;
+ if (log.isDebugEnabled()) { // force it to generate both sides
+ if (lessList == null)
+ lessList = new ArrayList<>();
+ if (moreList == null)
+ moreList = new ArrayList<>();
+ if (!coords.get(0).highPrecEquals(coords.get(coords.size()-1))) {
+ log.warn("Shape not closed");
+ ++errorCount;
+ }
+ }
if (lessList != null) {
newLess = new ArrayList<>();
lessPoly = startLine(newLess);
@@ -646,11 +700,45 @@
trailAlong = leadAlong;
trailRel = leadRel;
} // for leadCoord
- if (log.isDebugEnabled()) {
- log.debug("initSplit #points", coords.size(), "on", dividingLine, isLongitude, "Area", runningArea, "#newLess", newLess.size(), "#newMore", newMore.size());
+ errorCount += processLineList(newLess, lessList, runningArea);
+ errorCount += processLineList(newMore, moreList, runningArea);
+ if (errorCount > 0) {
+ int lowestPoint = newLess.get(0).lowPoint;
+ log.error("splitErrors:", errorCount, "on", dividingLine, isLongitude, "points", coords.size(), "area", runningArea, "lowest", lowestPoint, coords.get(0).toOSMURL());
+ for (MergeCloseHelper thisLine : newLess)
+ log.warn("LessLoop", thisLine.lowPoint-lowestPoint, thisLine.highPoint-lowestPoint, thisLine.direction, thisLine.areaOrHole, thisLine.areaToLine, thisLine.points.size());
+ for (MergeCloseHelper thisLine : newMore)
+ log.warn("MoreLoop", thisLine.lowPoint-lowestPoint, thisLine.highPoint-lowestPoint, thisLine.direction, thisLine.areaOrHole, thisLine.areaToLine, thisLine.points.size());
+ if (log.isDebugEnabled()) {
+ String fileName = (isLongitude ? "V" : "H") + dividingLine + "_" + lowestPoint;
+ GpxCreator.createGpx(fileName + "/S", coords); // original shape
+ int fInx = 0;
+ for (MergeCloseHelper thisLine : newLess) {
+ ++fInx;
+ GpxCreator.createGpx(fileName + "/N" + fInx, thisLine.points);
+ }
+ fInx = 0;
+ for (MergeCloseHelper thisLine : newMore) {
+ ++fInx;
+ GpxCreator.createGpx(fileName + "/P" + fInx, thisLine.points);
+ }
+ // NB: lessList/moreList could be non-existent (but debugEnabled stops this),
+ // then same object or have already have contents
+ fInx = 0;
+ String filePrefix = lessList == moreList ? "/B" : "/L";
+ for (List<Coord> fragment : lessList) {
+ ++fInx;
+ GpxCreator.createGpx(fileName + filePrefix + fInx, fragment);
+ }
+ if (lessList != moreList) {
+ fInx = 0;
+ for (List<Coord> fragment : moreList) {
+ ++fInx;
+ GpxCreator.createGpx(fileName + "/M" + fInx, fragment);
+ }
+ }
+ }
}
- processLineList(newLess, lessList, runningArea);
- processLineList(newMore, moreList, runningArea);
} // splitShape
_______________________________________________
mkgmap-dev mailing list
[email protected]
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
