I'm doing a Python simulation of a vehicle, driving along a specified path. I generate dummy GPS readings, that fetch the current position of the vehicle, with some randomized error added. After a track is complete, I obtain a set of collected GPS points, that looks like this:

Fig.1. Depiction of exemplary collection of track points, together with the real road driven (red line)

Assuming that we have no knowledge on how the physical path looks like (for performance reasons, we do not want to have anything to do with the map), and that we only know these points, I would like to detect the turns of this track. I want to do this, so that later, I can group these points by linear segments, and then construct a convex hull for each of them separately, like this:

Depiction of the intended convex hull deployment

One idea that I already had, is, given a set of data points, construct a piecewise linear approximation of these points, and then extract the coordinates of the resulting line. However, it is still somehow problematic, because I would have to look for the closest existing point from the dataset, which seems to be time-consuming. The best outcome for me would be to identify right away the specific point (or points) at which the turn occurs. Every track has a list of its recorded points, and I have to cut it into pieces somehow, but to do that, I need to know at which points it turns.

more exact convex hull problem definition Maybe this approach is wrong in general, maybe there is a much easier way, to find a convex hull without large empty areas for a group of points right away?

Additional information: The points are NOT an ordinary point cloud, they are stored as a list, which means that they are ORDERED.

  • 1
    Your problem is under-specified. There exist a large number of solutions that achieve a total area of zero for the convex hulls: simply connect the points in any arbitrary order, giving n-1 turns for n points. This shows that either the number of turns needs to be prescribed in advance or some penalty needs to be included to limit the number of turns. For an interesting and powerful approach to a similar problem--which might suggest some ways to attack this one--check out stats.stackexchange.com/a/34287/919. – whuber May 27 '14 at 15:47
  • Okay, maybe I shouldn't have used the minimum area term. I take that back. My goal is to achieve what is depicted on the 2nd figure. I'd like to find a convex hull for a route-like set of points, but I'd like to avoid large empty areas (which would occur if I simply calculated the bounding box for the entire route). This is why I need the partition. – user3619725 May 27 '14 at 20:48
  • 1
    Such hulls can be found in various ways, such as alpha shapes, but their appropriateness for this application would be questionable absent some clearer idea of how you plan to use or interpret those hulls. It is also curious that you seem not to be using the temporal information implicit in these data: the collection time imparts an intrinsic order to the points, suggesting they should be considered as vertices of a directed polyline rather than a mere point cloud. – whuber May 27 '14 at 20:50
  • These hulls are necessary, since in further development I'd like to record another trach to an existing route. Meaning, that I have a set of user's usual routes, and when a user drives the same route again, I need to query the database, identify on which route I am, and display it. And that's why I need those hulls, I need some polygon that will represent a user's route, and the only information I can use to build that polygon are track points from user's older routes. – user3619725 May 27 '14 at 20:54
  • And that corridor will have the least erroneous shape, if we build straight segment by straight segment, and then merge them, like on the 2nd figure. – user3619725 May 27 '14 at 20:56

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.