Efficient searching algorithm for finding closest point to a line segment

Question

I have list of points (latitude & longitude) from google API call. Every 5sec interval, I am getting current location of the vehicle. My task is to check if the vehicle has not deviated from the defined path and within permitted tolerance of 100m.

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

Below is my logic to prepare line segment and calculate the distance between line segment and the current location using Haversine formula. This is working fine if the latLngList size is less. But, if the size is more its taking long time to give the result.

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.951480000000002,77.69398000000001","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,77.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.959190000000001,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.64137000000001","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"**

Linear Search Output: (12.955010000000001,77.67874)

KDTree Search Output: (12.956660000000001,77.67534)

Have tried KDTree & QuadTree but not found the suitable implementation for the problem. Can any one have implementation or any other searching mechanism which is suitable for this scenario. Experts please help.

A k-d tree seems to be the right tool for the job. Is your problem that you don't know how to implement a k-d tree, or is your problem that you don't know how to use a k-d tree to solve the task? — Lorenz, Mar 02 '20 at 23:13
@frececroka I am searching for a k-d tree implementation which suits my requirement. — Manu, Mar 03 '20 at 20:09
Does this answer your question? [KDTree Implementation in Java](https://stackoverflow.com/questions/253767/kdtree-implementation-in-java) — Lorenz, Mar 03 '20 at 21:19
@frececroka I am getting different co-ordinate while searching using KDTree algorithm. I have updated my input latlng list and search input. Please suggest. — Manu, Mar 08 '20 at 19:45
I don't have enough information to see why you get the wrong results. Maybe ask a new question with an exact description of how you're using the k-d tree to solve your problem so people can help. — Lorenz, Mar 09 '20 at 12:43
Also note that it is definitely not enough to just search for the nearest vertex of the path. A point can be very far away from all vertices and still be very close to (the middle of a) line segment. — Lorenz, Mar 09 '20 at 12:45
A simple solution that may very well be good enough is to discretize every line segment into multiple points. Then you can use a plain k-d tree to locate the closest of the discretized points, which won't be much farther away than the closest line segment. — Lorenz, Mar 09 '20 at 12:55

Efficient searching algorithm for finding closest point to a line segment

0 Answers0