Best algorithm to find near moving objects

I’m making an app for delivery in which a client can look for near cars for transportation, if I use a single channel the client will be listening to all available cars even the ones not near him, I thought of a solution in which each car transmits its position in a region (channel), when the car moves it should switch of region and channel, this way when a client looks for a near car it will only look for regions (channels) that are near him, can you suggest a better solution?

1 Like

Hello @boriscy, your description seems pretty vague. Could you describe it better and with some examples?

I’d go for your regional approach, but you need to add a mechanism to ensure that clients and cars near the region-borders on different sides thereof are still able to comunicate/see each other.

Another way is to use a k-dimensional tree, and query for items in certain distances to each other and send targeted messages. To have this work as best as possible though you need to hold the tree completely in memory or find an external database which does give similar or better runtimes for inserts and lookups. But when implementing the tree by yourself be aware of the fact, that every update of the tree involves copying it completely, so I think inmem is only capable for a small number of updates per time.

What about relying on a database to handle this for you and use a geospatial query?

2 Likes

For example I have a business (client) that sells food and I want to deliver something to a client, I make a search and look for the cars that are near me and ask for transportation, the cars should have an app that transmits their position, the client should be able to track the position of the cars, this requires a query in the server that returns the cars near me but should update every time since cars are moving, this could become heavy if there are many clients searching for cars.

Other way would be to broadcast the position of all cars and let the client (app) calculate the ones near him, but it seems it’s not a good approach, I would like to divide in regions (channels) and each region would broadcast only the cars inside of it, if a client asks for a car it checks for the position of the client and just subscribes to the channels near it.

I think it could be very heavy on the database, to many updates for each car movement.

I do think that there are databases available which are specialised in those scenarios. They may be packaged or bundled in fully fledged fleet management software though.

Since you are talking about cars on streets in a city, you should use Manhattan Distance. Then use a distance threshold to limit the results.

PostgreSQL has a fantastic geospatial engine, could easily do it via its queries.

2 Likes

Pro tip: Square the distance threshold and compare it with the squared magnitude instead of Pythagoras. Eliminates the incredibly expensive square root.

1 Like

Technically having the threshold as squared and comparing it, is still pythagoreas :wink:

2 Likes

This is a great tip that not enough developers know about. In a more general sense: Square roots (or divisions, or other expensive computations) can often be avoided if you’re only interested in if something exceeds a certain threshold (and thus the ‘end result’ such as in this case the actual distance is not needed).

3 Likes

https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-geo-distance-query.html