I have some polyline data that represents a navigation route generated using Dijkstra's algorithm. Along this route I would like to calculate anytime a turn is required. Ideally, this would be some threshold where the route would require a turn greater than X amount.

Given a polyline, what are some techniques to calculate a turn and it's direction?

I am not using road data from anything like OSM. The data is custom captured coordinates for a traveled path. This means I can't use something that consumes road networks like from OSM data.

I am looking for mathematical techniques to calculate the turns in my custom data. For example, I am currently using two segments of my path. Point1 -> Point2 and then Point2 -> Point3. With these two vectors I am trying to determine if there is an angle in direction change that could be considered a "turn". I am not sure of all the variables I need to take into account here with heading/bearing, etc. Any explanation of what to consider would help.

Current Attempt:

  1. Converting the lat,long data into cartesian coordinate values
  2. Creating two vectors p1->p2 and p2->p3.
  3. Normalizing those vectors
  4. Taking the cross product of those vectors
  5. Cross product > 0 turn right, less than 0 turn left, otherwise straight.
  • I have added a tag for algorithm and removed your request for code samples. For code requests you need to include a code snippet that illustrates what you have tried and where you are stuck. – PolyGeo Sep 16 '17 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.