Changeset 18589 in josm


Ignore:
Timestamp:
2022-11-08T18:51:13+01:00 (2 years ago)
Author:
taylor.smock
Message:

Fix #22453: Decrease allocations/CPU samples in Geometry.getDistanceSegmentSegment

Statistics, using Mesa County, CO as the data ("nwr in 'Mesa County, CO'") with
the MapWithAI plugin validations enabled (validation run):

  • CPU samples: 54,604 -> 39,146 (-15,458, -28.3%)
  • Memory allocations: 170,983,028,400 -> 4,645,539,624 (-166,337,488,776, -97.3%)
    • All remaining allocations are from creating a new LatLon during interpolation.
  • .7% improvement in GC threads (overall, see notes).

Notes:

  • getDistanceWayNode was also modified to avoid EastNorth allocations.
  • All remaining allocations come from the creation of new LatLon objects. This may be alleviated when value classes become a thing in Java LTS, and we start using them.
  • Profiling was done from application startup to shut down.
Location:
trunk
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/data/coor/ILatLon.java

    r18495 r18589  
    144144        return bearing;
    145145    }
     146
     147    /**
     148     * Does a linear interpolation between two ILatLon instances.
     149     * @param ll2 The other ILatLon instance.
     150     * @param proportion The proportion the other instance influences the result.
     151     * @return The new {@link ILatLon} position.
     152     * @since 18589
     153     */
     154    default ILatLon interpolate(ILatLon ll2, double proportion) {
     155        // this is an alternate form of this.lat() + proportion * (ll2.lat() - this.lat()) that is slightly faster
     156        return new LatLon((1 - proportion) * this.lat() + proportion * ll2.lat(),
     157                (1 - proportion) * this.lon() + proportion * ll2.lon());
     158    }
     159
     160    /**
     161     * Returns the square of euclidean distance from this {@code Coordinate} to a specified coordinate.
     162     *
     163     * @param lon the X coordinate of the specified point to be measured against this {@code Coordinate}
     164     * @param lat the Y coordinate of the specified point to be measured against this {@code Coordinate}
     165     * @return the square of the euclidean distance from this {@code Coordinate} to a specified coordinate
     166     * @since 18589
     167     */
     168    default double distanceSq(final double lon, final double lat) {
     169        final double dx = this.lon() - lon;
     170        final double dy = this.lat() - lat;
     171        return dx * dx + dy * dy;
     172    }
     173
     174    /**
     175     * Returns the euclidean distance from this {@code ILatLon} to a specified {@code ILatLon}.
     176     *
     177     * @param other the specified coordinate to be measured against this {@code ILatLon}
     178     * @return the euclidean distance from this {@code ILatLon} to a specified {@code ILatLon}
     179     * @since 18589
     180     */
     181    default double distanceSq(final ILatLon other) {
     182        return this.distanceSq(other.lon(), other.lat());
     183    }
    146184}

  • trunk/src/org/openstreetmap/josm/data/coor/LatLon.java

    r18495 r18589  
    259259
    260260    /**
    261      * Interpolate between this and a other latlon
     261     * Interpolate between this and a other latlon. If you don't care about the return type, use {@link ILatLon#interpolate(ILatLon, double)}
     262     * instead.
    262263     * @param ll2 The other lat/lon object
    263264     * @param proportion The proportion to interpolate
    … …  
    265266     */
    266267    public LatLon interpolate(LatLon ll2, double proportion) {
    267         // this is an alternate form of this.lat() + proportion * (ll2.lat() - this.lat()) that is slightly faster
    268         return new LatLon((1 - proportion) * this.lat() + proportion * ll2.lat(),
    269                 (1 - proportion) * this.lon() + proportion * ll2.lon());
     268        ILatLon interpolated = ILatLon.super.interpolate(ll2, proportion);
     269        if (interpolated instanceof LatLon) {
     270            return (LatLon) interpolated;
     271        }
     272        return new LatLon(interpolated);
    270273    }
    271274

  • trunk/src/org/openstreetmap/josm/tools/Geometry.java

    r18553 r18589  
    492492        double pdx = point.getX() - p1.getX();
    493493        double pdy = point.getY() - p1.getY();
     494
     495        double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy);
     496
     497        if (segmentOnly && offset <= 0)
     498            return p1;
     499        else if (segmentOnly && offset >= 1)
     500            return p2;
     501        else
     502            return p1.interpolate(p2, offset);
     503    }
     504
     505    /**
     506     * Get the closest point to a segment
     507     * @param p1 Point 1 of the segment
     508     * @param p2 Point 2 of the segment
     509     * @param point The point to use to get the closest point on the segment
     510     * @param segmentOnly {@code true} if the point <i>must</i> be on the segment
     511     * @return The closest point on the segment if {@code segmentOnly = true}, otherwise the closest point on the infinite line.
     512     */
     513    private static ILatLon closestPointTo(ILatLon p1, ILatLon p2, ILatLon point, boolean segmentOnly) {
     514        CheckParameterUtil.ensureParameterNotNull(p1, "p1");
     515        CheckParameterUtil.ensureParameterNotNull(p2, "p2");
     516        CheckParameterUtil.ensureParameterNotNull(point, "point");
     517
     518        double ldx = p2.lon() - p1.lon();
     519        double ldy = p2.lat() - p1.lat();
     520
     521        //segment zero length
     522        if (ldx == 0 && ldy == 0)
     523            return p1;
     524
     525        double pdx = point.lon() - p1.lon();
     526        double pdy = point.lat() - p1.lat();
    494527
    495528        double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy);
    … …  
    15011534
    15021535        double smallest = Double.MAX_VALUE;
    1503         EastNorth en0 = node.getEastNorth();
    15041536        // go through the nodes as if they were paired
    15051537        Iterator<Node> iter = way.getNodes().iterator();
    1506         EastNorth en1 = iter.next().getEastNorth();
     1538        Node en1 = iter.next();
    15071539        while (iter.hasNext()) {
    1508             EastNorth en2 = iter.next().getEastNorth();
    1509             double distance = getSegmentNodeDistSq(en1, en2, en0);
     1540            Node en2 = iter.next();
     1541            double distance = getSegmentNodeDistSq(en1, en2, node);
    15101542            if (distance < smallest)
    15111543                smallest = distance;
    … …  
    15611593        Iterator<Node> iter1 = w1.getNodes().iterator();
    15621594        Node w1N1 = iter1.next();
     1595        List<Node> w2Nodes = w2.getNodes();
    15631596        while (iter1.hasNext()) {
    15641597            Node w1N2 = iter1.next();
    1565             Iterator<Node> iter2 = w2.getNodes().iterator();
     1598            Iterator<Node> iter2 = w2Nodes.iterator();
    15661599            Node w2N1 = iter2.next();
    15671600            while (iter2.hasNext()) {
    … …  
    16021635     */
    16031636    public static double getDistanceSegmentSegment(Node ws1Node1, Node ws1Node2, Node ws2Node1, Node ws2Node2) {
    1604         EastNorth enWs1Node1 = ws1Node1.getEastNorth();
    1605         EastNorth enWs1Node2 = ws1Node2.getEastNorth();
    1606         EastNorth enWs2Node1 = ws2Node1.getEastNorth();
    1607         EastNorth enWs2Node2 = ws2Node2.getEastNorth();
    1608         if (enWs1Node1 == null || enWs1Node2 == null || enWs2Node1 == null || enWs2Node2 == null)
     1637        if (!ws1Node1.isLatLonKnown() || !ws1Node2.isLatLonKnown() || !ws2Node1.isLatLonKnown() || !ws2Node2.isLatLonKnown()) {
    16091638            return Double.NaN;
    1610         if (getSegmentSegmentIntersection(enWs1Node1, enWs1Node2, enWs2Node1, enWs2Node2) != null)
     1639        }
     1640        if (getSegmentSegmentIntersection(ws1Node1, ws1Node2, ws2Node1, ws2Node2) != null)
    16111641            return 0;
    16121642
    1613         double dist1sq = getSegmentNodeDistSq(enWs1Node1, enWs1Node2, enWs2Node1);
    1614         double dist2sq = getSegmentNodeDistSq(enWs1Node1, enWs1Node2, enWs2Node2);
    1615         double dist3sq = getSegmentNodeDistSq(enWs2Node1, enWs2Node2, enWs1Node1);
    1616         double dist4sq = getSegmentNodeDistSq(enWs2Node1, enWs2Node2, enWs1Node2);
     1643        double dist1sq = getSegmentNodeDistSq(ws1Node1, ws1Node2, ws2Node1);
     1644        double dist2sq = getSegmentNodeDistSq(ws1Node1, ws1Node2, ws2Node2);
     1645        double dist3sq = getSegmentNodeDistSq(ws2Node1, ws2Node2, ws1Node1);
     1646        double dist4sq = getSegmentNodeDistSq(ws2Node1, ws2Node2, ws1Node2);
    16171647        double smallest = Math.min(Math.min(dist1sq, dist2sq), Math.min(dist3sq, dist4sq));
    16181648        return smallest != Double.MAX_VALUE ? Math.sqrt(smallest) : Double.NaN;
    … …  
    16491679     * @return the square of the euclidean distance from p to the closest point on the segment
    16501680     */
    1651     private static double getSegmentNodeDistSq(EastNorth s1, EastNorth s2, EastNorth p) {
    1652         EastNorth c1 = closestPointTo(s1, s2, p, true);
    1653         return c1.distanceSq(p);
     1681    private static double getSegmentNodeDistSq(ILatLon s1, ILatLon s2, ILatLon p) {
     1682        ILatLon c1 = closestPointTo(s1, s2, p, true);
     1683        return c1.distanceSq(p.lon(), p.lat());
    16541684    }
    16551685}

  • trunk/test/unit/org/openstreetmap/josm/tools/GeometryTest.java

    r18494 r18589  
    1414import java.util.Collections;
    1515import java.util.List;
     16import java.util.stream.Collectors;
    1617import java.util.stream.Stream;
    1718
    … …  
    164165    }
    165166
     167    static Stream<Arguments> testCentroid() {
     168        // The expected values use the BigDecimal calculations
     169        return Stream.of(
     170            Arguments.of(new LatLon(54.10310051693397, 12.094459783282147),
     171                new LatLon[]{
     172                    new LatLon(54.1031207, 12.094513),
     173                    new LatLon(54.1030973, 12.0945423),
     174                    new LatLon(54.1031188, 12.0944413),
     175                    new LatLon(54.1030578, 12.0945178),
     176                    new LatLon(54.1030658, 12.0944275),
     177                    new LatLon(54.1030826, 12.0945434),
     178                    new LatLon(54.1031079, 12.0944243),
     179                    new LatLon(54.1030515, 12.094495),
     180                    new LatLon(54.103094, 12.0944157),
     181                    new LatLon(54.1031257, 12.0944893),
     182                    new LatLon(54.1030687, 12.0945348),
     183                    new LatLon(54.1031251, 12.0944641),
     184                    new LatLon(54.1030792, 12.0944168),
     185                    new LatLon(54.1030508, 12.0944698),
     186                    new LatLon(54.1030559, 12.0944461),
     187                    new LatLon(54.1031107, 12.0945316)
     188                }),
     189            Arguments.of(new LatLon(54.10309639216633, 12.09463150330365),
     190                new LatLon[]{new LatLon(54.1031205, 12.094653),
     191                    new LatLon(54.1030621, 12.0946675),
     192                    new LatLon(54.1030866, 12.0946874),
     193                    new LatLon(54.1030732, 12.0946816),
     194                    new LatLon(54.1030766, 12.0945701),
     195                    new LatLon(54.1031148, 12.0945865),
     196                    new LatLon(54.1031122, 12.0946719),
     197                    new LatLon(54.1030551, 12.0946473),
     198                    new LatLon(54.1031037, 12.0945724),
     199                    new LatLon(54.1031003, 12.094684),
     200                    new LatLon(54.1030647, 12.0945821),
     201                    new LatLon(54.1031219, 12.0946068),
     202                    new LatLon(54.1031239, 12.0946301),
     203                    new LatLon(54.1030903, 12.0945667),
     204                    new LatLon(54.1030564, 12.0946011),
     205                    new LatLon(54.1030531, 12.0946239)
     206                }),
     207                Arguments.of(new LatLon(54.103185854296896, 12.09457804609505),
     208                    new LatLon[] {
     209                        new LatLon(54.1031981, 12.0945501),
     210                        new LatLon(54.1031782, 12.0945501),
     211                        new LatLon(54.1031726, 12.0946082),
     212                        new LatLon(54.1031955, 12.0946015)
     213                    }),
     214                Arguments.of(new LatLon(54.103180913681705, 12.094425831813119),
     215                    new LatLon[] {
     216                        new LatLon(54.1032057, 12.0943903),
     217                        new LatLon(54.1031517, 12.0944053),
     218                        new LatLon(54.1031877, 12.0943743),
     219                        new LatLon(54.1031697, 12.0943743),
     220                        new LatLon(54.1031517, 12.0944353),
     221                        new LatLon(54.1031697, 12.0944663),
     222                        new LatLon(54.1031877, 12.0944663),
     223                        new LatLon(54.1032057, 12.0944363)
     224                    })
     225        );
     226    }
     227
     228    @ParameterizedTest
     229    @MethodSource
     230    void testCentroid(LatLon expected, LatLon... coordinates) {
     231        LatLon actual = ProjectionRegistry.getProjection()
     232                .eastNorth2latlon(Geometry.getCentroid(Stream.of(coordinates).map(Node::new).collect(Collectors.toList())));
     233        assertTrue(expected.equalsEpsilon((ILatLon) actual), "Expected " + expected + " but got " + actual);
     234    }
     235
    166236    /**
    167237     * Test of {@link Geometry#getCentroidEN} method.
    … …  
    172242        EastNorth en2 = new EastNorth(150, 400);
    173243        EastNorth en3 = new EastNorth(200, 200);
    174         assertEquals(en1, Geometry.getCentroidEN(Arrays.asList(en1)));
     244        assertEquals(en1, Geometry.getCentroidEN(Collections.singletonList(en1)));
    175245        assertEquals(new EastNorth(125, 300), Geometry.getCentroidEN(Arrays.asList(en1, en2)));
    176246        assertEquals(new EastNorth(150, 266d + 2d/3d), Geometry.getCentroidEN(Arrays.asList(en1, en2, en3)));
Note: See TracChangeset for help on using the changeset viewer.