Modify

Opened 6 months ago

Closed 5 months ago

#17616 closed enhancement (fixed)

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

Reported by: taylor.smock Owned by: team
Priority: normal Milestone: 19.05
Component: Core Version:
Keywords: Cc:

Description

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.

Attachments (16)

17616.patch (16.4 KB) - added by taylor.smock 6 months ago.
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.
17616.2.patch (22.5 KB) - added by taylor.smock 6 months ago.
Add tests for added functions
17616_v2.patch (22.7 KB) - added by taylor.smock 6 months ago.
Add an additional test for getting the furthest distance and fix the method for it.
17616_v3.patch (22.8 KB) - added by taylor.smock 6 months ago.
Replace Double.MIN_VALUE with Double.NEGATIVE_INFINITY and add a test to ensure that the furthest primitive can be at 0 distance.
17616_v4.patch (24.0 KB) - added by taylor.smock 6 months ago.
Store calculated WaySegments
17616_v5.patch (24.2 KB) - added by taylor.smock 6 months ago.
Add synchronized statements for waySegments to avoid thread safety issues. Even if something clears waySegments, the user should still get data.
17616_v6.patch (24.1 KB) - added by taylor.smock 6 months ago.
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).
17616_v7.patch (25.5 KB) - added by taylor.smock 6 months ago.
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).
17616_v8.patch (26.7 KB) - added by taylor.smock 6 months ago.
Return Double.NaN when a primitive is incomplete and modify docs to specify that the OsmPrimitives should be fully downloaded for accuracy.
17616-v9.patch (30.5 KB) - added by GerdP 6 months ago.
adapted to r15031, additional unit test and alternative simpler but slower implementation for getDistanceSegmentSegment()
17616_v10.patch (28.6 KB) - added by taylor.smock 6 months ago.
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
17616_v10.2.patch (28.6 KB) - added by taylor.smock 6 months ago.
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
17616-v11.patch (28.1 KB) - added by GerdP 6 months ago.
17616_v12.patch (29.3 KB) - added by taylor.smock 6 months ago.
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.
projectionTests.patch (5.6 KB) - added by taylor.smock 6 months ago.
Additional tests in different projections (3 projections + default projection, if different). Two tests currently fail.
projectionTests.2.patch (5.3 KB) - added by taylor.smock 6 months ago.
Correct GpxDistanceTest error

Download all attachments as: .zip

Change History (52)

Changed 6 months ago by taylor.smock

Attachment: 17616.patch added

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.

comment:1 Changed 6 months ago by taylor.smock

Owner: taylor.smock deleted
Status: assignednew

comment:2 Changed 6 months ago by taylor.smock

Owner: set to team

Changed 6 months ago by taylor.smock

Attachment: 17616.2.patch added

Add tests for added functions

comment:3 Changed 6 months ago by Don-vip

Milestone: 19.04

comment:4 Changed 6 months ago by 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]*$'.

Changed 6 months ago by taylor.smock

Attachment: 17616_v2.patch added

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

comment:5 Changed 6 months ago by 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.

Changed 6 months ago by taylor.smock

Attachment: 17616_v3.patch added

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

comment:6 in reply to:  5 Changed 6 months ago by 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.

comment:7 Changed 6 months ago by 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.

comment:8 in reply to:  7 Changed 6 months ago by 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<>()));

Changed 6 months ago by taylor.smock

Attachment: 17616_v4.patch added

Store calculated WaySegments

comment:9 Changed 6 months ago by 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.

comment:10 Changed 6 months ago by 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.

Changed 6 months ago by taylor.smock

Attachment: 17616_v5.patch added

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

comment:11 Changed 6 months ago by 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.

Changed 6 months ago by taylor.smock

Attachment: 17616_v6.patch added

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).

comment:12 in reply to:  11 Changed 6 months ago by 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.

comment:13 Changed 6 months ago by 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));
    }

comment:14 Changed 6 months ago by 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.

Changed 6 months ago by taylor.smock

Attachment: 17616_v7.patch added

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).

comment:15 Changed 6 months ago by 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?

comment:16 in reply to:  15 Changed 6 months ago by 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.

comment:17 Changed 6 months ago by 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?

Changed 6 months ago by taylor.smock

Attachment: 17616_v8.patch added

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

comment:18 Changed 6 months ago by Don-vip

Milestone: 19.0419.05

comment:19 Changed 6 months ago by GerdP

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

comment:20 Changed 6 months ago by 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);
    }

comment:21 Changed 6 months ago by 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.

comment:22 Changed 6 months ago by 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);
    }

Changed 6 months ago by GerdP

Attachment: 17616-v9.patch added

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

Changed 6 months ago by taylor.smock

Attachment: 17616_v10.patch added

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

comment:23 Changed 6 months ago by 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?)

Changed 6 months ago by taylor.smock

Attachment: 17616_v10.2.patch added

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

comment:24 Changed 6 months ago by GerdP

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

Changed 6 months ago by GerdP

Attachment: 17616-v11.patch added

comment:25 Changed 6 months ago by 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.

comment:26 in reply to:  24 Changed 6 months ago by 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).

Changed 6 months ago by taylor.smock

Attachment: 17616_v12.patch added

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.

comment:27 Changed 6 months ago by GerdP

Resolution: fixed
Status: newclosed

In 15035/josm:

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

comment:28 Changed 6 months ago by GerdP

Resolution: fixed
Status: closedreopened

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?

comment:29 Changed 6 months ago by GerdP

In 15036/josm:

see #17616: fix findbugs issues FE_FLOATING_POINT_EQUALITY

comment:30 in reply to:  28 Changed 6 months ago by 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).

Changed 6 months ago by taylor.smock

Attachment: projectionTests.patch added

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

comment:31 Changed 6 months ago by GerdP

What about the tests in GpxDistanceTest? Should I GpxDistanceTest?

Changed 6 months ago by taylor.smock

Attachment: projectionTests.2.patch added

Correct GpxDistanceTest error

comment:32 in reply to:  31 Changed 6 months ago by 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).

comment:33 Changed 6 months ago by GerdP

In 15038/josm:

see #17616: adapt unit test

comment:34 Changed 6 months ago by GerdP

In 15039/josm:

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

comment:35 Changed 5 months ago by Don-vip

Is this ticket fixed?

comment:36 Changed 5 months ago by GerdP

Resolution: fixed
Status: reopenedclosed

Yes, I think so.

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain team.
as The resolution will be set.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.