Hi Gerd
I think this can cope with any number of lines, in either/both
directions, following the same path. Also it should give better output
if same number of lines in both directions.
With debug, if it notices a problem, it generates a GPX trace of the
original and traces of all the resultant bits individually in a
subdirectory relevant to the split line.
I've tested it on a few examples, but I'll stress-test GBR again and
check the shapes where it detects problems.
I probably need to tidy up some message levels and comments.
Ticker
On Wed, 2021-05-26 at 11:17 +0100, Ticker Berkin wrote:
> Hi Gerd
>
> I have to design a shape that does this and think what it means. With
> the extra handling needed for identical opposite lines it will be
> easy
> to detect. Maybe possible to just chuck it.
>
> I'm out for the rest of the day so can't do anything until tomorrow.
>
> Ticker
>
> On Wed, 2021-05-26 at 08:46 +0000, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > OK, I think your patch improves some cases. I've also fixed another
> > potential cause for these problems with r4744.
> >
> > I think I have to find a way to avoid those segments which are
> > visited multiple times in the same direction. There's probably
> > always
> > an alternative merge order that avoids this.
> >
> > Gerd
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev@lists.mkgmap.org.uk
> 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,6 +600,7 @@
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 (lessList != null) {
@@ -646,11 +690,32 @@
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;
+ // %%% which msg to warn/info etc
+ 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);
+ for (MergeCloseHelper thisLine : newMore)
+ log.warn("MoreLoop", thisLine.lowPoint-lowestPoint, thisLine.highPoint-lowestPoint, thisLine.direction, thisLine.areaOrHole, thisLine.areaToLine);
+ if (log.isDebugEnabled()) {
+ String fileName = (isLongitude ? "H" : "V") + dividingLine + "_" + lowestPoint;
+ GpxCreator.createGpx(fileName + "/S", coords); // original shape
+ // NB: lessList/moreList could be empty, same object or have already have contents
+ int fInx = 0;
+ for (List<Coord> fragment : lessList) {
+ ++fInx;
+ GpxCreator.createGpx(fileName + "/L" + fInx, fragment);
+ }
+ 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
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev