Эффективный алгоритм поиска для нахождения ближайшей точки к отрезку - PullRequest
Новая
       42

Эффективный алгоритм поиска для нахождения ближайшей точки к отрезку

1 голос
/ 02 марта 2020

У меня есть список точек (широта и долгота) от вызова API Google. Каждый 5se c интервал, я получаю текущее местоположение автомобиля. Моя задача состоит в том, чтобы проверить, не отклонился ли транспортное средство от заданного пути и в пределах допустимого допуска 100 м. 

DirectionsResult results = DirectionsApi.getDirections(context, "Source Address", "Destination Address")
                             .mode(TravelMode.DRIVING).await();
 List<LatLng> latLngList = results.routes[0].overviewPolyline.decodePath();

Ниже приведены мои логики c для подготовки сегмента линии и расчета расстояния между отрезком линии и текущее местоположение, используя формула Haversine . Это работает нормально, если размер latLngList меньше. Но, если размер будет больше, потребуется много времени, чтобы получить результат. 

LatLng current = new LatLng(12.95847371672292,77.67890810966492);
for (int i=0; i < latLngList.size()-1; i++) {
    double tolerance = LocationUtil.distanceToLineSegment(latLngList.get(i), 
            latLngList.get(i+1), current);
    if(tolerance < 100){
        message = "Vehicle within permitted tolerance of 100m.";
        break;
    }
}

List latLngList = Arrays.asList ("12.950980000000001,77.69407000000001", "12.951440000000002,77.69417", "12.9514800000000000,77.69398" "12.951550000000001,77.69380000000001", "12.951920000000001,77.69387", "12.95212,77.69392", "12.95217,77.69388000000001", "12.95226,77.69348000000001", "12.95231,77.69299000000001", "12.952580000000001,77.69305", "12.952710000000002,77.69303000000001", "12,95279 , +77,69303000000001" , "12.95293,77.69309000000001", "12.95312,77.69318000000001", "12.95334,77.69324", "12.95354,77.69339000000001", "12.953740000000002,77.69348000000001", "12.95381,77.69354000000001", "12.95387,77.69364", "12.954020000000002,77.69371000000001 », "12.954160000000002,77.69375000000001", "12.95466,77.69376000000001", "12.95536,77.69382", "12.955570000000002,77.69382", "12.955960000000001,77.69389000000001", "12.956130000000002,77.69384000000001", "12.95612,77.69378", "12.955910000000001,77.69271", «12.955770000000001,7 7,69177" , "12.95573,77.69149", "12.955330000000002,77.68949", "12.95513,77.68824000000001", "12.95503,77.68780000000001", "12.954960000000002,77.68728", "12.954920000000001,77.68688", "12.95471,77.68451", "12.954500000000001,77.68231" , "12.95437,77.68066", "12.954400000000001,77.68033000000001", "12.954450000000001,77.68001000000001", "12.954500000000001,77.67986", "12.9547,77.67941", "12.955010000000001,77.67874", "12.956660000000001,77.67534", "12.95715,77.67434",» 12.957600000000001,77.67317000000001" , "12.957720000000002,77.67281000000001", "12.95781,77.67225", "12.957860000000002,77.67190000000001", "12.95795,77.67098", "12.958,77.67043000000001", "12.958050000000002,77.66938", "12.95809,77.66865", "12,95808, 77,66799" , "12.95814,77.66704", "12.958240000000002,77.66639", "12.958440000000001,77.66556", "12.958570000000002,77.66498", "12.958620000000002,77.66463", "12.95889,77.66354000000001", "12.959050000000001,77.66276", "12.95916,77.66222" "12.95926,77.66142", "12.959270000000002,77.66111000000001", "+12,9591900000 00001,77.66057" , "12.959040000000002,77.65978000000001", "12.95903,77.65926", "12.959080000000002,77.65837", "12.95916,77.65768000000001", "12.959190000000001,77.65745000000001", "12.95921,77.65722000000001", "12.959280000000001,77.6558", "12,95931, 77,65489000000001" , "12.95936,77.65365000000001", "12.95939,77.65318", "12.95949,77.65144000000001", "12.95964,77.64983000000001", "12.95968,77.64942", "12.95982,77.64837", "12.960070000000002,77.64599000000001", "12.96025,77.64456000000001" , "12.96039,77.6431", "12.96044,77.64275", "12.96052,77.64193", "12.960360000000001,77.64173000000001", "12.960030000000001,77.64163", "12.95983,77.64159000000001", "12.959600000000002,77.64156000000001", "12.958950000000002,77.64152",» 12.958450000000001,77.64149" , "12.958290000000002,77.64145", "12.958240000000002,77.64142000000001", "12.958150000000002,77.64141000000001", "12.95803,77.6414", "12.957820000000002,77.64138000000001", "12.95733,77.64139", "12.956710000000001,77.64143", "+12,955890000000002, 77,64142000000001" , "12.95471,77.6 4137000000001" , "12.954690000000001,77.64223000000001", "12.95471,77.6423", "12.954690000000001,77.64237", "12.95462,77.64240000000001", "12.954080000000001,77.64254000000001", "12.95404,77.64256", "12.953990000000001,77.64263000000001", "12.95391,77.64279" , "12.953360000000002,77.64264"); 

**Searching nearest neighbor for point: "12.95847371672292,77.67890810966492"**

Вывод линейного поиска: (12.955010000000001,77.67874)

Вывод поиска KDTree: (12.956660000000001,77.67534)

Пробовал KDTree & QuadTree , но не нашел подходящей реализации для этой проблемы. Может ли любой иметь реализацию или любой другой механизм поиска, который подходит для этого сценария. Эксперты, пожалуйста, помогите.

...