0
\$\begingroup\$

I have 2 lists of coordinates in C# one as of coordinates of Drivers and the other as of coordinates of cafes. I am looking for an efficient way of populating a static Dictionary with its key as of a Driver from the first list and its associated values of all Cafes in 500 meters radius. Number of cafes can be up to 100000 and number of Drivers are dynamic from 1 to 100000

public void ManageList() {
GlobalList.Clear();
foreach (var driver in driverList)
    {
        var driverCoords = new GeoCoordinate(driver.Latitude, driver.Longitude);
        List<Cafe> matchedCafes = new List<Cafe>();

        foreach (var cafe in cafeList)
        {
            var cafeCoords = new GeoCoordinate(cafe.Latitude, cafe.Longitude);

            if (cafeCoords.GetDistanceTo(driverCoords) <= 500) {
                matchedCafes.Add(cafeCoords);
            }
        }

        GlobalList.Add(driverCoords, matchedCafes);
    }
}

the above works fine as long as drivers are not movable objects. If I want to send the driver's coordinates every 5 seconds and update the GlobalList per driver the above algorithm fails as I am basically clearing the whole list and populate it again.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'm voting to close this question because it is a cross-post of a question on stack overflow. Cross-posting is not allowed on StackExchange sites. \$\endgroup\$ Commented Mar 22, 2018 at 0:03

1 Answer 1

Reset to default
0
\$\begingroup\$

The algorithm can be optimized by including a broad phase, this uses a less complicated algorithm and it narrows down the possible candidates as much as possible.

In this case I would use an AABB square with a side length of 1000 units, this contains the circle completely.

This works fine until you get to the 100000 cafes and 100000 drivers scenario. I don't think there's an efficient enough algorithm to handle that, but there are definitely better solutions, than simply brute-forcing your way through the cafes for every driver.

Try dividing the world into squares, possibly 500 by 500 squares and place the cafes into these based on their locations. When you need to find the cafes closer, than 500 metres, you first need to get the square the driver is in (this can be done with a simple (floar(x/500), floar(y/500)), where x and y are the driver's position and the resulting pair is the position of the square, then only check the cafes in that square and the 8 neighbouring ones.

\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.