My suggestions would be simply to abandon the approach of using the Google API for everything. Undoubtedly, it's the best navigation tool, and it's for this reason it's that expensive. So, I'd suggest to use some other method for the geocoding that's not through Google, especially if you're only looking for big cities (as is appears in your example). There's some 'free' APIs that already exist (in truth, they're usually never really free) - I'd only suggest this if you're serverless. In that case, I'd go with Nominatim - it has no limit caps (kind of, see operations.osmfoundation.org/policies/nominatim - you can spam it, but it's discouraged), no API keys, and is completely free - the only issue, of course, is that as you mentioned you'd have to go through each point and make a request to an API, which would take a lot of time. However, I'd do:
let zoom = 12; // Adjust to your needs: see nominatim.org/release-docs/develop/api/Reverse. Higher numbers will result in more places being matched, while lower numbers will result in faster execution.
let coords = [];
const stepList = [];
Array.from(googleResponse.routes[0].legs).forEach(leg => {
stepList.push(...leg.steps);
});
stepList.forEach(e => {
coords.push([e.endLocation.lat, e.endLocation.long]);
});
coords.push([legList[0].startLocation.lat, legList[0].startLocation.long]);
let arr = [];
let promises = [];
let bboxes = [];
const loopOn = (i, cb) => {
const coord = coords[i];
const nextLoop = () => {
i+1 < coords.length? loopOn(i+1, cb) : cb();
}
let makeRequest = true;
for (let bbox of bboxes) {
if (coord[0] >= bbox[0]
&& coord[0] <= bbox[1]
&& coord[1] >= bbox[2]
&& coord[1] <= bbox[3]){ // If it is within a bounding box we've already seen
makeRequest = false; // there's no need to geocode it, since we already roughly know it's in an area we have already saved.
break;
}
}
if (makeRequest){
var request = $.ajax({
url: `https://nominatim.openstreetmap.org/reverse?format=jsonv2&lat=${coord[0]}&lon=${coord[1]}&zoom=${zoom}`,
type:'GET',
dataType: 'jsonp',
success: resp => {
thisPlace = resp.address.city || resp.address.town || resp.address.village;
thisPlace && arr.indexOf(thisPlace) === -1 && arr.push(thisPlace);
bboxes.push(resp.boundingbox);
nextLoop();
}
});
} else {
nextLoop();
}
};
loopOn(0, () => {
/*The rest of your code*/
});
This code simply goes through each leg (where I'm assuming googleResponse is the unfiltered but JSONified response from the Directions API, and requests it from Nominatim. I've made it a tad bit more efficient using Nominatim's bounding boxes, which return the rectangle around each city/village area, so we don't need to make a request if an instruction/step is literally simply to turn a corner in the same square/suburb/city district/city (this can be defined using the zoom variable).
The problem with this is that Nominatim, being free and quite unoptimised, is obviously not the fastest API out there. Even if Google's servers ran on a slow connection, they'd still be faster simply because they've optimised their product to run faster, using some low-level code. Meanwhile, Nominatim simply does a basic lookup from a file (no rainbow hashing, etc.), so it has to manually narrow down the area.
The solution would be to use a custom dataset. Obviously, this would require a backend to store it on, since downloading the entire CSV to the frontend with each load would take literal hours (and on every reload!). All you'd really need to do for this is replace the AJAX API request with a call to the csv-parser module (or any other parsing function), which works in much the same way regarding promises/async, so you could literally just replace the code with the example on their website:
let resp = [];
fs.createReadStream(<your file here.csv>)
.pipe(csv())
.on('data', (data) => resp.push(data))
.on('end', () => {
results = search(resp, coords);
thisPlace = results.address.city || results.address.town || results.address.village;
thisPlace && arr.indexOf(thisPlace) === -1 && arr.push(thisPlace);
nextLoop();
});
Also, you could remove the bounding-box code, since you don't need to save request time anymore.
However, rearranging it like so would be faster:
let resp = [];
fs.createReadStream(<your file here.csv>)
.pipe(csv())
.on('data', (data) => resp.push(data))
.on('end', () => {
let coords = [];
const stepList = [];
Array.from(googleResponse.routes[0].legs).forEach(leg => {
stepList.push(...leg.steps);
});
stepList.forEach(e => {
coords.push([e.endLocation.lat, e.endLocation.lng]);
});
coords.push([legList[0].startLocation.lat, legList[0].startLocation.lng]);
let arr = [];
let promises = [];
let bboxes = [];
coords.forEach(coord => {
let results = search(coords);
let thisPlace = results.address.city || results.address.town || results.address.village;
thisPlace && arr.indexOf(thisPlace) === -1 && arr.push(thisPlace);
};
/*The rest of your code*/
});
The next thing we need is the actual search function, which is the complicated bit. We need to find something that's quick, but also mostly correct. The actual implementation depends on the format of your file, but here's a quick rundown of what I'd do:
- Create two duplicates of
resp, but sort one (we'll call this array a_o) by longitude and the other one by latitude (a_a). Ensure you don't use var or let or const when defining these arrays, just... define them.
- For each one, remove anything not within a 25km (radius) of the point on the longitude axis in
a_o, and the same but with latitude for a_a
delete both arrays to clear the space they are taking up in the RAM.- Find any item that's in both arrays, and put these in an array called
a_c
- Filter any items which are within 3-4km of each other (make sure to keep one of the points, though, not delete both!)
- Go through each item, and work out the absolute distance to the point (using this algorithm - remember, the earth is a sphere, basic Pythagorean thereom will not work!
- If you find any item with a distance less than 20km, and has a city or village or town attached, break and return the name.
- If you finish, i.e never break, return
undefined.
Other then that, you can go with mostly any CSV which contains:
- The city's name
- The central latitude
- The central longitude
I hope this helps. In conclusion, go with the first, tried-and-tested, premade method if you're only doing 5-6 simple routes an hour. If you've got gajillions of waypoints, download the data and spend half an hour or so making what is essentially your own geocoding system. It'll well be worth the performance bump.
