Changeset 36056 in osm

Timestamp:

2023-02-23T21:45:50+01:00 (18 months ago)

Author:

taylor.smock

Message:

Fix #22317: IOOBE in DrawnPolyLine.getLastPoint (patch by TrickyFoxy, modified)

The modifications are as follows:

• Added som unit tests
• Fixed some SonarLint issues (not from patch)
• Ensure that the last node can always be deleted

Location:

applications/editors/josm/plugins/FastDraw

Files:

• src/org/openstreetmap/josm/plugins/fastdraw/DrawnPolyLine.java (modified) (18 diffs)
• test (added)
• test/unit (added)
• test/unit/org (added)
• test/unit/org/openstreetmap (added)
• test/unit/org/openstreetmap/josm (added)
• test/unit/org/openstreetmap/josm/plugins (added)
• test/unit/org/openstreetmap/josm/plugins/fastdraw (added)
• test/unit/org/openstreetmap/josm/plugins/fastdraw/DrawnPolyLineTest.java (added)

applications/editors/josm/plugins/FastDraw/src/org/openstreetmap/josm/plugins/fastdraw/DrawnPolyLine.java

@@ -13 +13 @@
 import org.openstreetmap.josm.data.coor.LatLon;
 import org.openstreetmap.josm.gui.MapView;
-
+import org.openstreetmap.josm.tools.Logging;
+
+/**
+ * A holder for how the polyline has been drawn
+ */
 public class DrawnPolyLine {
     MapView mv;
-    private LinkedList<LatLon> points = new LinkedList<>();
+    private final LinkedList<LatLon> points = new LinkedList<>();
     private LinkedList<LatLon> simplePoints = new LinkedList<>();
     private Set<LatLon> used;
-    private Set<LatLon> fixed = new HashSet<>();
+    private final Set<LatLon> fixed = new HashSet<>();
 
     private int lastIdx;
     private boolean closedFlag;
 
+    /**
+     * Create a new object
+     */
     public DrawnPolyLine() {
         clear();
@@ -57 +64 @@
 
     boolean wasSimplified() {
-        return (simplePoints != null && simplePoints.size() > 0);
+        return (simplePoints != null && !simplePoints.isEmpty());
     }
 
@@ -85 +92 @@
 
     void undo() {
-        //if (points.size() > 0) points.removeLast();
         if (lastIdx > 0 && lastIdx < points.size()) {
             points.remove(lastIdx);
@@ -114 +120 @@
             }
         } else {
-            // insert point into midlle of the line
+            // insert point into middle of the line
             if (points.isEmpty() || !coor.equals(points.get(lastIdx))) {
-                points.add(lastIdx+1, coor);
+                points.add(lastIdx + 1, coor);
                 lastIdx++;
             }
@@ -137 +143 @@
     /**
      * Increase epsilon to fit points count in maxPKM point per 1 km
+     * @param initEpsilon min point-to line distance in pixels (tolerance, initial)
+     * @param ekf The multiplier against the epsilon for the next round, until the max points per km is reached
+     * @param k see {@link #getNodesPerKm(int)}
+     * @param maxPKM The maximum nodes per km
+     * @return The final epsilon value used
      */
     double autoSimplify(double initEpsilon, double ekf, int k, double maxPKM) {
         double e = initEpsilon;
         if (e < 1e-3) e = 1e-3;
-        if (ekf < 1+1e-2) ekf = 1.01;
+        if (ekf < 1 + 1e-2) ekf = 1.01;
         simplify(e);
         while (getNodesPerKm(k) > maxPKM && e < 1e3) {
-            e = e*ekf;
+            e = e * ekf;
             simplify(e);
-            //System.out.printf("eps=%f n=%d\n", e,simplePoints.size());
+            Logging.trace("DrawnPolyLine: eps={0} n={1}", e, simplePoints.size());
         }
         return e;
@@ -153 +164 @@
     /**
      * Simplified drawn line, not touching the nodes includes in "fixed" set.
+     * @param epsilon min point-to line distance in pixels (tolerance)
      */
     void simplify(double epsilon) {
-        //System.out.println("Simplify polyline...");
+        Logging.trace("DrawnPolyLine: Simplify polyline...");
         int n = points.size();
         if (n < 3) return;
@@ -173 +185 @@
         simplePoints.addAll(points);
         simplePoints.retainAll(used);
-        //Main.map.mapView.repaint();
         used = null;
     }
@@ -179 +190 @@
     /**
      * Simplification of the line specified by "points" field.
-     * Remainin points are included to "used" set.
+     * Remaining points are included to "used" set.
      * @param start - starting index
      * @param end - ending index
@@ -190 +201 @@
         LatLon first = points.get(start);
         LatLon last = points.get(end);
-        Point firstp = getPoint(first);
-        Point lastp = getPoint(last);
+        Point firstP = getPoint(first);
+        Point lastP = getPoint(last);
         used.add(first);
         used.add(last);
@@ -197 +208 @@
         if (end - start < 2) return;
 
-        int farthest_node = -1;
-        double farthest_dist = 0;
-
-        double d = 0;
+        int farthestNode = -1;
+        double farthestDist = 0;
 
         for (int i = start + 1; i < end; i++) {
-            d = pointLineDistance(getPoint(points.get(i)), firstp, lastp);
-            if (d > farthest_dist) {
-                farthest_dist = d;
-                farthest_node = i;
-            }
-        }
-
-        if (farthest_dist > epsilon) {
-            douglasPeucker(start, farthest_node, epsilon, depth + 1);
-            douglasPeucker(farthest_node, end, epsilon, depth + 1);
-        }
-    }
-
-    /** Modfified funclion from LakeWalker
+            double d = pointLineDistance(getPoint(points.get(i)), firstP, lastP);
+            if (d > farthestDist) {
+                farthestDist = d;
+                farthestNode = i;
+            }
+        }
+
+        if (farthestDist > epsilon) {
+            douglasPeucker(start, farthestNode, epsilon, depth + 1);
+            douglasPeucker(farthestNode, end, epsilon, depth + 1);
+        }
+    }
+
+    /**
+     * Modified function from LakeWalker
      * Gets distance from point p1 to line p2-p3
+     * @param p1 The originating point
+     * @param p2 An end of the line
+     * @param p3 The other end of the line
+     * @return The distance from point p1 to the line p2-p3
      */
     public double pointLineDistance(Point p1, Point p2, Point p3) {
@@ -240 +254 @@
 
     void deleteNode(int idx) {
-        if (idx <= lastIdx) lastIdx--;
+        final boolean isClosed = isClosed();
+        final LatLon point = points.get(idx);
+        if (isClosed) {
+            if (idx == 0) idx = getPointCount() - 1;
+            if (idx == getPointCount() - 1) closedFlag = false;
+        }
+        if (idx <= lastIdx && lastIdx != 0) lastIdx--;
         fixed.remove(points.get(idx));
         points.remove(idx);
+        if (isClosed && points.size() == 1 && points.get(0) == point) {
+            this.deleteNode(0);
+        }
     }
 
@@ -280 +303 @@
     }
 
-    /** find starting point of the polyline line fragment close to p
+    /**
+     * find starting point of the polyline line fragment close to p
      *  line fragment = segments between two fixed (green) nodes
+     * @param p The point to find the segment for
+     * @return the LatLon of the start of the segment
      */
     LatLon findBigSegment(Point p) {
@@ -288 +314 @@
         Iterator<LatLon> it2 = points.listIterator(1);
         Point p1, p2;
-        LatLon pp1, pp2, start = null;
+        LatLon pp1, pp2, start;
         start = points.getFirst();
         do {
@@ -306 +332 @@
     }
 
-    private double pointSegmentDistance(Point p, Point p1, Point p2) {
-        double a, b, x, y, l, kt, kn, dist;
-        x = p.x-p1.x;
-        y = p.y-p1.y;
-        a = p2.x-p1.x;
-        b = p2.y-p1.y;
-        l = Math.hypot(a, b);
-        if (l == 0) return Math.hypot(x, y); // p1 = p2
-        kt = (x*a+y*b)/l;
-        kn = Math.abs((-x*b+y*a)/l);
+    private static double pointSegmentDistance(Point p, Point p1, Point p2) {
+        final int x = p.x - p1.x;
+        final int y = p.y - p1.y;
+        final int a = p2.x - p1.x;
+        final int b = p2.y - p1.y;
+        final double l = Math.hypot(a, b);
+        if (l == 0) {
+            return Math.hypot(x, y); // p1 = p2
+        }
+        final double kt = (x * a + y * b)/l;
+        final double kn = Math.abs((-x * b + y * a)/l);
+        double dist;
         if (kt >= 0 && kt < l) dist = kn; else {
-            dist = Math.min(Math.hypot(x, y), Math.hypot(x-a, y-b));
+            dist = Math.min(Math.hypot(x, y), Math.hypot((double) x - a, (double) y - b));
         }
         return dist;
@@ -360 +388 @@
      * max((k-1) / (L(i,i+1)+L(i+1,i+2)+...+L(i+k-1,i+k))) [ i=1..n-k ]
      * @param k - window size (number of points to average points per km
+     * @return The maximum number of <i>simplified</i> line points divided by the segment length
      */
     public double getNodesPerKm(int k) {
@@ -369 +398 @@
         if (k > n) k = n;
 
-        ILatLon pp1, pp2 = null;
+        ILatLon pp1, pp2;
         Iterator<LatLon> it1, it2;
         it1 = pts.listIterator(0);
@@ -376 +405 @@
         for (int i = 0; i < n-1; i++) {
             pp1 = it1.next();
-            //p1 = getPoint(pp1);
             pp2 = it2.next();
-            //p2 =sa getPoint(pp2);
             lens[i] = pp1.greatCircleDistance(pp2);
         }
         double pkm = 0, maxpkm = 0;
         double len = 0;
-        int seg = 0; // averaged segments counts
+        int seg; // averaged segments counts
         for (int i = 1; i < n; i++) {
             len += lens[i-1]; // add next next point
@@ -395 +422 @@
                 // len is length of points[i-windowSize] .. points[i]
                 if (len > 0) pkm = seg / len * 1000;
-                //System.out.println("i="+i+" pkm="+len+" pkm="+pkm);
+                Logging.trace("DrawnPolyLine: i={0} len={1} pkm={2}", i, len, pkm);
                 if (pkm > maxpkm) maxpkm = pkm;
             }