Add new functions to Geometry.java to find distances between primitives

[taylor.smock]

Add functions to Geometry.java to

• Get the closest distance between osm primitives
• Get the furthest distance between osm primitives while not going around the world
• Sub-functions for the above

See ​https://github.com/KaartGroup/highwayNameModificationJOSMPlugin/blob/master/src/com/kaart/highwaynamemodification/GeometryCustom.java for a partial implementation. I'll post a patch as soon as I can.

[taylor.smock]

Add functions to get distances between OsmPrimitives to Geometry.java, refactor GPXDistance.java to use the methods, and deprecate the methods used in GPXDIstance.java.

[taylor.smock]

Add tests for added functions

[GerdP]

I think getFurthestPrimitive() doesn't work. It will always return the last primitive with a distance > Double.MIN_VALUE.
Please also change the unit test to make sure it detects this.
SonarLint doesn't like the variable name D in getDistanceSegmentSegment: Rename this local variable to match the regular expression '^{[a-z][a-zA-Z0-9]*$'.}

[taylor.smock]

Add an additional test for getting the furthest distance and fix the method for it.

[GerdP]

Forgot to ask: Do you really mean Double.MIN_VALUE and not Double.NEGATIVE_INFINITY? If all primitives have a distance of 0 you'll get null as a result.

[taylor.smock]

Replace Double.MIN_VALUE with Double.NEGATIVE_INFINITY and add a test to ensure that the furthest primitive can be at 0 distance.

[taylor.smock]

Replying to GerdP:

Forgot to ask: Do you really mean Double.MIN_VALUE and not Double.NEGATIVE_INFINITY? If all primitives have a distance of 0 you'll get null as a result.

No, I assumed that Integer.MIN_VALUE and Double.MIN_VALUE were functionally similar.

[GerdP]

OK, I also had to look twice ;)
Reg. performance: I think I read somewhere that there are problems.

• Do you know the index for WaySegments used in CrossingWays? Maybe getDistanceWayWay() should use something like that?
• If these methods are called often it might be better to avoid all the WaySegment instances created in getWaySegments() method.

[taylor.smock]

Replying to GerdP:

OK, I also had to look twice ;)
Reg. performance: I think I read somewhere that there are problems.

• Do you know the index for WaySegments used in CrossingWays? Maybe getDistanceWayWay() should use something like that?
• If these methods are called often it might be better to avoid all the WaySegment instances created in getWaySegments() method.

It looks like it stores computed WaySegments in a HashMap (cellSegments) with 2D points. I'm not certain how it is getting the WaySegments.

    public static List<List<WaySegment>> getSegments(Map<Point2D, List<WaySegment>> cellSegments, EastNorth n1, EastNorth n2) {
        List<List<WaySegment>> cells = new ArrayList<>();
// OK, get cells in which to find the segments
        for (Point2D cell : ValUtil.getSegmentCells(n1, n2, OsmValidator.getGridDetail())) {
// Wait, what? Where do the segments come from? There is just a new (empty) list?
            cells.add(cellSegments.computeIfAbsent(cell, k -> new ArrayList<>()));
        }
        return cells;
    }

Alternatively, Geometry.java could be extended to have a static map which stores WaySegments with their Ways.
E.g.,

    static final HashMap<Way, List<WaySegment>> waySegments = new HashMap<>();

    /**
     * Get the way segments of a way
     * @param way The way to get the way segments of
     * @return A list of {@code WaySegment}s
     * @since xxx
     */
    public static List<WaySegment> getWaySegments(Way way) {
        // way.isModified() is run since we don't know if the way has had nodes added or not.
        if (waySegments.containsKey(way) && !way.isModified())
            return waySegments.get(way);

        List<WaySegment> segments = new ArrayList<>();
        int i = 0;
        do {
            segments.add(new WaySegment(way, i));
            i++;
        } while (i < way.getNodesCount() - 2);
        waySegments.put(way, segments);
        return segments;
    }

    /**
     * Call to clear cached way segments for performance
     * @since xxx
     */
    public static void clearCachedWaySegments() {
        waySegments.clear();
    }

    /**
     * Clear the cached way segments of a way
     * @param ways The ways to remove from the cached way segments
     * @since xxx
     */
    public static void clearCachedWaySegments(Way... ways) {
        for (Way way : ways) {
            waySegments.remove(way);
        }
    }

Extraneous information:

# Note that "getSegments" is only ever called with "cellSegments" (checked with different grep command)
$ grep -r "cellSegments" src/org/openstreetmap/josm
src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java:            final Map<Point2D, List<WaySegment>> cellSegments = new HashMap<>(1000);
src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java:                findIntersectingWay(w, cellSegments, problemWays, loop == 1);
src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java:     * @param cellSegments map with already collected way segments
src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java:    private static void findIntersectingWay(Way w, Map<Point2D, List<WaySegment>> cellSegments,
src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java:            for (List<WaySegment> segments : CrossingWays.getSegments(cellSegments, en1, en2)) {
src/org/openstreetmap/josm/data/validation/tests/CrossingWays.java:    private final Map<Point2D, List<WaySegment>> cellSegments = new HashMap<>(1000);
src/org/openstreetmap/josm/data/validation/tests/CrossingWays.java:        cellSegments.clear();
src/org/openstreetmap/josm/data/validation/tests/CrossingWays.java:        cellSegments.clear();
src/org/openstreetmap/josm/data/validation/tests/CrossingWays.java:            cellSegments.clear();
src/org/openstreetmap/josm/data/validation/tests/CrossingWays.java:            for (List<WaySegment> segments : getSegments(cellSegments, en1, en2)) {
src/org/openstreetmap/josm/data/validation/tests/CrossingWays.java:     * @param cellSegments map with already collected way segments
src/org/openstreetmap/josm/data/validation/tests/CrossingWays.java:    public static List<List<WaySegment>> getSegments(Map<Point2D, List<WaySegment>> cellSegments, EastNorth n1, EastNorth n2) {
src/org/openstreetmap/josm/data/validation/tests/CrossingWays.java:            cells.add(cellSegments.computeIfAbsent(cell, k -> new ArrayList<>()));

[taylor.smock]

Store calculated WaySegments

[GerdP]

Hmm, that's not what I meant and it would require some syncs to make it thread safe.
The index in CrossingWays is quite tricky, and maybe you can't use it for these methods because it is meant to find segments which are close to a given segment.

[taylor.smock]

I'll be honest, I don't understand how CrossingWays is getting the WaySegments -- I'm not seeing anything that is actually adding segments, but that just means I'm missing something somewhere.

As far as making the current code thread safe, I did think about essentially copying what UndoRedoHandler was doing with its getInstance(), but it doesn't look like it is particularly thread safe, so I've just added synchronized (waySegments) around the operations where the waySegments variable is being directly modified.

[taylor.smock]

Add synchronized statements for waySegments to avoid thread safety issues. Even if something clears waySegments, the user should still get data.

[GerdP]

What I tried to point out is that I don't see a need for the WaySegment instances. I think you can simply iterate over the nodes of the way instead of first creating list of WaySegments and then iterating over them.

[taylor.smock]

Get the closest nodes for ways and then make a list of the WaySegments surrounding the closest node, and find the nearest WaySegment from that list. Also make the getFurthestPrimitive/getClosestPrimitive generic, so they always return the type of primitive that is sent in the collection (OsmPrimitive if nothing more specific is passed).

[taylor.smock]

Replying to GerdP:

What I tried to point out is that I don't see a need for the WaySegment instances. I think you can simply iterate over the nodes of the way instead of first creating list of WaySegments and then iterating over them.

You are right, that would be faster.

Instead of effectively looking at each node twice, only look at them once to find the closest nodes and then find the closest WaySegment from that should be a bit more efficient. This means that I skip creating a bunch of WaySegments I don't need (thus freeing memory) and I don't iterate through every node at least twice.

I also modified the public static OsmPrimitive getFurthestPrimitive(OsmPrimitive osm, Collection<OsmPrimitive> primitives) to public static <T extends OsmPrimitive> T getFurthestPrimitive(OsmPrimitive osm, Collection<T> primitives) in order to simplify some methods. Example, instead of Node closestNode = (Node) getClosestPrimitive(primitive, new HashSet<OsmPrimitive>(way.getNodes())) I can just do Node closestNode = getClosestPrimitive(primitive, way.getNodes()).

There is also a new method to build WaySegments from a Way and a Node (getSurroundingSegments) since it was something that I ended up doing several times.

[GerdP]

This cannot work. You can't find the closest segment by looking only at the closest node. Try this

    @Test
    public void testGetClosestWaySegment() {
        Node node1 = new Node(new LatLon(0, 0));
        Node node2 = new Node(new LatLon(0, 1));
        Node node3 = new Node(new LatLon(0.3, 0.5));
        Node node4 = new Node(new LatLon(0, 0));
        Way way1 = TestUtils.newWay("", node1, node2, node3, node4);


        Way closestSegment = Geometry.getClosestWaySegment(way1, new Node(new LatLon(0.1, 0.5))).toWay();
        Assert.assertTrue(closestSegment.containsNode(node1));
        Assert.assertTrue(closestSegment.containsNode(node2));
    }

[GerdP]

Some more hints

• For the unit tests I'd prefer ways where no segment is horizontal or vertical. This helps to find issues where bounding boxes are relevant.
• were a distance is returned you should document the unit
• document what happens when multiple objects with the same distance exist.

[taylor.smock]

Use Pair<Node, Node> instead of WaySegments for some calculations, add units (and why it is those units) to the javadocs, modify tests to not be horizontal so bounding boxes aren't exactly the line (the methods don't use bounding boxes, but may be refactored in the future), document that the get(CLOSTEST/FURTHEST)Primitive may return a different result each time (it shouldn't, since the underlying collection is currently a TreeSet, but that may end up being changed in the future).

[GerdP]

Way.getNodePairs() checks if the way is incomplete. This case is not handled in the new code in Geometry. Any ideas what should happen?

[taylor.smock]

Replying to GerdP:

Way.getNodePairs() checks if the way is incomplete. This case is not handled in the new code in Geometry. Any ideas what should happen?

I have no idea. Based off of my reading of the javadocs, nothing really changes (the javadocs seem to imply that an OsmPrimitive should only ever be incomplete if we only know its type and its id, which means that we don't have any nodes for the way anyway).

Option 1) Download the incomplete way. It also means that the way is probably part of a relation. This is probably a bad idea, since we would be downloading stuff in the background when the user doesn't want that to happen.

Option 2) Ignore incomplete Ways/Nodes (we don't have any information on their location, so we can't get its distance) even when looking at the distance to a relation.

Option 3) Remove if (isIncomplete()) return chunkSet; from Way.java. It looks like if there is only one node or if there are no nodes (i.e., if it is incomplete), then it will still return an empty chunkSet.

Option 4) Add a boolean to the statement, e.g. if (isIncomplete() && careAboutIncomplete) return chunkSet; and overload the method.

[GerdP]

You can also have incomplete relations where some ways or nodes are known but not all. Question is if it makes sense to handle this in Geometry. I'd say it should be handled by the caller and the methods in Geometry should be able to handle the case that an object has no position, maybe by returning null or throwing an exception?

[taylor.smock]

Return Double.NaN when a primitive is incomplete and modify docs to specify that the OsmPrimitives should be fully downloaded for accuracy.

[GerdP]

@taylor: I wanted to commit the patch but it no longer applies without conflicts. Can you please provide a new patch?

[GerdP]

The method testGetDistanceSegmentSegment() doesn't work for this case:

    /**
     * Test of {@link Geometry#getDistanceSegmentSegment} method
     */
    @Test
    public void testGetDistanceSegmentSegment() {
        Node node1 = new Node(new LatLon(2.0, 2.0));
        Node node2 = new Node(new LatLon(2.0, 3.0));
        Node node3 = new Node(new LatLon(2.3, 2.5));
        assertEquals(0.0, Geometry.getDistanceSegmentSegment(node1, node2, node3, node1), 0.0000001);
    }

[GerdP]

It seems you copied most of the implementation for getDistanceSegmentSegment from here:
​http://geomalgorithms.com/a07-_distance.html
If we use it we have to include the copyright comment:

// Copyright 2001 softSurfer, 2012 Dan Sunday
// This code may be freely used, distributed and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.

[GerdP]

It also fails for crossing segments. My understanding is that it should return 0:

    public void testGetDistanceSegmentSegment() {
        Node node1 = new Node(new LatLon(2.0, 2.0));
        Node node2 = new Node(new LatLon(2.0, 3.0));
        Node node3 = new Node(new LatLon(2.3, 2.5));

        // crossing segments
        Node node6 = new Node(new LatLon(1.8, 2.05));
        assertEquals(0.0, Geometry.getDistanceSegmentSegment(node1, node2, node3, node6), 0.000001);
    }

[GerdP]

adapted to r15031, additional unit test and alternative simpler but slower implementation for getDistanceSegmentSegment()

[taylor.smock]

Take unit tests from 17616-v9.patch, switch to a slower implementation for the getDeistanceSegmentSegment, update to newest version of the JOSM code for merging

[taylor.smock]

I didn't see your patch until I had switched to a slower implementation for the getDistanceSegmentSegment(). (Is the JOSM mailserver sending out emails for patches?)

[taylor.smock]

Take unit tests from 17616-v9.patch, switch to a slower implementation for the getDistanceSegmentSegment, update to newest version of the JOSM code for merging

[GerdP]

Please review, 17616_v10.2.patch and 17616_v10.patch are identical

[GerdP]

Please review v11. Changes:

• calculate squared distances while comparing, return sqrt for final result
• don't create Pair instances when iterating over nodes
• return Double.NaN when result is Double.MAX_VALUE

Throughput is ~twice as fast.
I've probably not found all places where Double.MAX_VALUE is returned, but I've no more time today.

[taylor.smock]

I meant to replace the initial 17616_v10.patch since I had accidentally misspelled a word in my comment (I've noticed that trac replaces comments when you replace the file with a different comment).

• I can see how not computing the actual distance for comparisons speeds up the process (condensing multiple sqrt statements to one)
• I've assumed in the past that WaySegments were cached as part of the Way object, and I did the same for the Pair instances. Now that I've looked at the code, it looks like it iterates through all the nodes and builds a Pair object, so it isn't as efficient as I thought.
• I've gone through the code and added Double.NaN returns where Double.MAX_VALUE would be returned, and I changed the return value for one of the methods to return null if the shortest distance was Double.NaN.

Looking through your changes in 17616-v11.patch,

• Reduced the code reuse in getDistance by calling itself for one of the relation if statements (this removes the code that was duplicated)
• Removed a method to get the distance between a node and set of nodes describing a way (I like your solution -- its simpler than what I had)
• You explained the complexity of a method (I should go through and add that where necessary)
• Quite a bit of variable renaming (I don't have any objections to the renaming, since most of the renaming was internal to the function or better described the incoming variable).

[taylor.smock]

Add more checks for Double.MAX_VALUE to ensure that we don't return it and instead return Double.NaN, which is "larger" than Double.MAX_VALUE according to javadocs. Also, return null from a statement where the smallest distance was Double.MAX_VALUE. Double.MAX_VALUE is significantly larger than the world is around (in km), so we should never see it, even with squared distances.

[GerdP]

In 15035/josm:

fix #17616: Add new functions to Geometry.java to find distances between primitives
Patch 17616_v12.patch by taylor.smock

[GerdP]

Unit test GpxDistanceTest fails.
I think testGetDistanceEastNorth expects a completely wrong result (old code was wrong), but testGetDistanceWay() is a bit surprising.
My understanding is that the distance between latlon point (0.0, 0.0) and (1.0, 0.0) should be less than that between (0.0, 0.0) and (0.0, 1.0). Seems the distortion for the projection is kicking in here. Maybe it is not a good idea to use the east/north space to do these calculations?

[GerdP]

In 15036/josm:

see #17616: fix findbugs issues FE_FLOATING_POINT_EQUALITY

[taylor.smock]

Replying to GerdP:

Unit test GpxDistanceTest fails.
I think testGetDistanceEastNorth expects a completely wrong result (old code was wrong), but testGetDistanceWay() is a bit surprising.
My understanding is that the distance between latlon point (0.0, 0.0) and (1.0, 0.0) should be less than that between (0.0, 0.0) and (0.0, 1.0). Seems the distortion for the projection is kicking in here. Maybe it is not a good idea to use the east/north space to do these calculations?

I've added some tests for different projections (won't work if we get the expected result in the test, but will work if it is hard-coded).

If we switch to LatLon, we will be getting the distance in LatLon space. We can't convert LatLon units to km/miles, since the units are variable distance.

I honestly don't know what the best method forward would be. We could specify that the result is dependent upon the coordinate system or we could find a projection that is designed for measurements and hardcode the methods to use that particular projection (probably not the best of ideas).

[taylor.smock]

Additional tests in different projections (3 projections + default projection, if different). Two tests currently fail.

[GerdP]

What about the tests in GpxDistanceTest? Should I GpxDistanceTest?

[taylor.smock]

Correct GpxDistanceTest error

[taylor.smock]

Replying to GerdP:

What about the tests in GpxDistanceTest? Should I GpxDistanceTest?

I thought about removing the methods in GpxDistance since I had effectively moved them to Geometry, but I ended up marking them @Deprecated and pointing people towards the new Geometry methods (just in case someone is already using the methods).

[GerdP]

In 15038/josm:

see #17616: adapt unit test

[GerdP]

In 15039/josm:

see #17616: remove unit test which only tests deprecated methods

[Don-vip]

Is this ticket fixed?

[GerdP]

Yes, I think so.