cjj20 / publictransportbus

1 stars 1 forks source link

Viscinity matching algorithms #3

Open kiselev-dv opened 1 month ago

kiselev-dv commented 1 month ago

Right now code calculates the distances between all the points many times in a nested loops which gets really inefficient as a number of points grow.

I would suggest two things:

  1. To simplify calculations, use projected coordinates: https://wiki.openstreetmap.org/wiki/Mercator that way you can get distances the normal euclidean way (as inverse square of yada yada)
  2. use a spatial index like https://en.wikipedia.org/wiki/Quadtree

That way you can store one set of points in index (let's say OSM stops for example) and later for every GTFS stop find neighboring OSM Stops using index like queryRange(<30m box around gtfs stop>) and process found stops further.

By further processing I mean that just a closest point might not be good enough, we will have to do more check on possible candidates, but let's address that in a separate issue.

cjj20 commented 1 month ago

I will try changing the distance matching algorithm and the use of quad tree. I am still working on figuring out how to handle the bus stop conflicts which may arise due to name issues etc.