Search code examples
iosswiftgoogle-mapscoordinatesgoogle-polyline

How to divide array of route coordinates, to equal distance parts?

I’m working with Google Maps API on iOS app. I have a route between point A, and point B, This route is encoded to String, which I’ve decoded to array of coordinates, from which, in fact, route is created.

And now the problem occurs: I need divide this route is some way, that let me get coordinates of points, which are away from each other by given distance, let’s say 20 kilometers. I know that points are not appear regular on distance, so it must be +/- 20 km, depends how densely points are in section of the road. For example:

let decodedPolylinePoints = 
[(22.3456, 23.3232), (32.3232, 32.3332), (33.4555,34.466), ….]

And after calculations, the result is an array, in which next elements have +/- 20km from each other.



Any ideas? I’m implementing Swift app, but language is free to choose. It’s all about the algorithm.

route with all coordinate markers

screen of route with zoomed points

Solution

  • Assuming you want the sum of point-to-point distances to be the same:

    Convert the array of tuples to an array of CLLocation objects.

    Map the array of CLLocation objects to an array of structures where each struct contains the start and end point of a pair of points (A-B, B-C, C-D, D-E, etc) and the calculated distance between those points (Using the CLLocation distance(from:) method.) Call that a Segment.

    Define a type PolyLine that is an array of Segment objects.

    Now define a type that is of type array of PolyLines. (Call The array of Polylines a Route.

    Instantiate an empty Route variable (trip). (var trip = Route()) Create an empty PolyLine var currentPolyLine. (var currentPolyLine = Polyline().)

    Now loop through the big source array of segments. If the sum of the distances in the current polyline, plus the new segment, is ≤ your desired threshold, add the segment to currentPolyLine. If the new segment would make the current PolyLine too long, add currentPolyLine to the Route, empty out currentPolyLine and replace it with the new segment. When you run out of Segments, add the last remaining PolyLine to the Route.

    That should give you an array of PolyLines that are ≤ your desired distance. The last PolyLine may be shorter than all the rest.

    If you want to accept PolyLines that might be a little longer or a little shorter than your desired distance it gets more complicated.

    Assuming your Segments are short enough, and your desired PolyLines distance is long enough, you should get PolyLines that are about the same length. As your longest Segment length gets closer to your PolyLine length the variation in PolyLine length will get greater.