Расчет попарных расстояний маршрутизации между большим количеством GPS-координат

У меня есть веб-приложение, в котором у каждого пользователя также есть координаты GPS (SqlGeography). На данный момент я рассчитываю расстояние между двумя координатами GPS как евклидово расстояние с помощью функции Distance.

Некоторые пользователи попросили меня заменить приблизительное расстояние (в терминах расстояния по воздуху) на более реалистичное расстояние. Я думаю об использовании определенных API-интерфейсов маршрутизации (например, от Google, Here или Azure), чтобы получить более реалистичное расстояние, например, для поездки на автомобиле.

В настоящее время у меня есть около 5000 различных координат GPS, и я хотел бы рассчитать и сохранить парное расстояние для всех этих пар. Это приведет к 5000 * 5000 запросов/запросов, что очень дорого. Есть ли способ уменьшить квадратичную сложность с помощью трюка, о котором я не подумал?


google-maps c# geolocation asp.net sqlgeography
person citronas    schedule 08.08.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Некоторые API имеют возможность добавлять путевые точки/остановки между началом и концом маршрута (например, Sygic web API.

Возможно, Google и компания сделают что-то подобное.

Ответ включает свойство legs, представляющее маршрут/длительность от начала до путевой точки1, wapoint1 до путевой точки N, путевой точки N до конца маршрута и т. д.

{
    "routes": [
        {
            "route": "oupjIa}w|@^ErCUPELEf@@`A[nAjGlBnFfBtERl@~DdNdA~DdBjG|BhKfArELbAd@`EJdFKxF?rBVfKF~BFjH@jEChJC`DMtLCzEApB@bIRdOZlGdAtLr@tErAxGnIj\\fBnIrBxMr@|Gh@fHf@jJPvFDvAHxBBf@X|EA`Br@zLd@|Dz@hF`AzElBhIvClMnA|Ib@dGd@bKb@rYBbBJ|CDxGFjEx@tm@N`ID|CF`PStMI|B[`Hi@vIcA`KkC|PcBtIoBlIaF`RgN~c@oGpTqGrWaFtWyEd\\mAlKcBpQkBbX{@~PcAlYG`CClAEdBAj@KdEe@z`@AlBCjDC|XJ~WTrTh@rWZ`Pf@tUTfK`@fQ|@d]v@|O|BpYhBpOrE`\\bC`RDZf@fEvBlULtBZfFJhBNxCBZn@xQ\\~TZb`@JxQ@jNO~PeAfa@mDzdAo@jOsArSmDx_@eAnK}AlRs@zNg@rRChUB|ENzKZnR~B~tAvBthAv@nUtAdWbCl\\p[zbDrFhh@nDvZdB`Mb@~C|@xGrJ~n@fIzb@pBlJv@lDzAxGrDtOzEnQ|Rdr@|FzU|ArH|DfU~ArLx@xG^dDtBbQb@nDhAtIFf@\\`CZvBDXbAbHDXbBvKv@`E|BfJd@~BVlAJh@tA~Gb@tB\\~AtDbPrB~IxB~IzB`JvCdLzAdGjAvELb@Nn@|@xDR~@r@jDzAjI`@hCT~AhDbVF\\fAjIlBbOrAlKjAtIr@lFz@nG@JJv@v@`G`@|Cd@jDDhAJp@D^TzB@ZBpCStEYfB_@pAeAlCINo@~@oBbBoCrAaFfB_H`BsGhA}Ch@gMrB}Bd@oAR_APyOlCwAV}EdASF]JcErA_BXe@G]w@EsBNu@l@yBZe@j@]f@GjBTx@JXF@kApAc]ImEO_AWq@uAkAgAe@eCyA_CoDm@s@cA[eCM?mIYiBsAcEy@uBcA}A]MeAGu@?e@VsEVw@Ho@JiBHwAEa@SaAKy@Cs@PuAlAc@r@sChE{CjFkA`D}AbGIj@y@bEW`Ai@rAw@tA",
            "eta": 1531834797,
            "duration": {
                "value": 1713,
                "text": "28 minutes 33 seconds"
            },
            "distance": {
                "value": 36430,
                "text": "36.43 km"
            },
            "legs": [
                {
                    "distance": {
                        "value": 36430,
                        "text": "36.43 km"
                    },
                    "duration": {
                        "value": 1713,
                        "text": "28 minutes 33 seconds"
                    },
                    "start_location": {
                        "latitude": 54.32168,
                        "longitude": 10.12193
                    },
                    "end_location": {
                        "latitude": 54.30731,
                        "longitude": 9.66195
                    },
                    "route": "oupjIa}w|@^ErCUPELEf@@`A[nAjGlBnFfBtERl@~DdNdA~DdBjG|BhKfArELbAd@`EJdFKxF?rBVfKF~BFjH@jEChJC`DMtLCzEApB@bIRdOZlGdAtLr@tErAxGnIj\\fBnIrBxMr@|Gh@fHf@jJPvFDvAHxBBf@X|EA`Br@zLd@|Dz@hF`AzElBhIvClMnA|Ib@dGd@bKb@rYBbBJ|CDxGFjEx@tm@N`ID|CF`PStMI|B[`Hi@vIcA`KkC|PcBtIoBlIaF`RgN~c@oGpTqGrWaFtWyEd\\mAlKcBpQkBbX{@~PcAlYG`CClAEdBAj@KdEe@z`@AlBCjDC|XJ~WTrTh@rWZ`Pf@tUTfK`@fQ|@d]v@|O|BpYhBpOrE`\\bC`RDZf@fEvBlULtBZfFJhBNxCBZn@xQ\\~TZb`@JxQ@jNO~PeAfa@mDzdAo@jOsArSmDx_@eAnK}AlRs@zNg@rRChUB|ENzKZnR~B~tAvBthAv@nUtAdWbCl\\p[zbDrFhh@nDvZdB`Mb@~C|@xGrJ~n@fIzb@pBlJv@lDzAxGrDtOzEnQ|Rdr@|FzU|ArH|DfU~ArLx@xG^dDtBbQb@nDhAtIFf@\\`CZvBDXbAbHDXbBvKv@`E|BfJd@~BVlAJh@tA~Gb@tB\\~AtDbPrB~IxB~IzB`JvCdLzAdGjAvELb@Nn@|@xDR~@r@jDzAjI`@hCT~AhDbVF\\fAjIlBbOrAlKjAtIr@lFz@nG@JJv@v@`G`@|Cd@jDDhAJp@D^TzB@ZBpCStEYfB_@pAeAlCINo@~@oBbBoCrAaFfB_H`BsGhA}Ch@gMrB}Bd@oAR_APyOlCwAV}EdASF]JcErA_BXe@G]w@EsBNu@l@yBZe@j@]f@GjBTx@JXF@kApAc]ImEO_AWq@uAkAgAe@eCyA_CoDm@s@cA[eCM?mIYiBsAcEy@uBcA}A]MeAGu@?e@VsEVw@Ho@JiBHwAEa@SaAKy@Cs@PuAlAc@r@sChE{CjFkA`D}AbGIj@y@bEW`Ai@rAw@tA",
                    "eta": 1531834797
                }
            ]
        }
    ],
    "status": "OK",
    "copyright": "© 2018 Sygic a.s."
}
person nilsK    schedule 08.08.2018