Modify

Opened 2 months ago

#17388 new enhancement

[WIP PATCH] gpx_distance() is slow when there are many gpx points

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

Description

I added a bunch of gpx tracks to josm, and then ran a validator.

The total distance covered was in excess of 400 km (so probably about 13,000 gpx points and around 180,000 primitives for around 2,340,000,000 operations per gpx_distance() call) and it was a conglomeration of several different tracks.

I'm thinking that a possible solution would be to make bounding boxes for the gpx tracks and iterate through them to find the closest bounding box (probably find the bounding boxes that overlap with the closest bounding box) and iterate through the bounding boxes.

The reason it is slow is due to an n2 algorithm (for each osm primitive, we have to loop through the gpx tracks at least once).

Workaround: Reduce the number of osmprimitives/gpx points that are loaded at any one time.

I probably should have tested something like this, but I didn't think to do so.

Attachments (2)

GpxDistance_speed.patch (4.6 KB) - added by taylor.smock 2 months ago.
Untested patch that adds a method to get the distance between the centroid of an OsmPrimitive and a Bounds, it also starts work on finding the closest Bounds.
GpxDistance_speed_v2.patch (5.8 KB) - added by taylor.smock 2 months ago.
Working patch (VERY SLOW), but it does cut down on the iterations significantly in many cases (I don't know where the slowdown is).

Download all attachments as: .zip

Change History (2)

Changed 2 months ago by taylor.smock

Attachment: GpxDistance_speed.patch added

Untested patch that adds a method to get the distance between the centroid of an OsmPrimitive and a Bounds, it also starts work on finding the closest Bounds.

Changed 2 months ago by taylor.smock

Attachment: GpxDistance_speed_v2.patch added

Working patch (VERY SLOW), but it does cut down on the iterations significantly in many cases (I don't know where the slowdown is).

Modify Ticket

Change Properties
Set your email in Preferences
Action
as new The owner will remain team.
as The resolution will be set.
to The owner will be changed from team to the specified user.
The owner will change to taylor.smock
as duplicate The resolution will be set to duplicate.The specified ticket will be cross-referenced with this ticket
The owner will be changed from team to anonymous.

Add Comment


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

 
Note: See TracTickets for help on using tickets.