1
$\begingroup$

I have an array of 2 dimensional points describing a path. I want to reduce the number of points needed to describe this path by using line segments that connect multiple points on the same line, allowing for some minimal deviations.

For example, given the points (0,0)-(50,50)-(100,100), the path can be optimized by only specifying (0,0)-(100,100) which will also cover the center point. In case of (0,0)-(49,49)-(100,100) I still want to allow the same line segment of (0,0)-(100,100), as the distance (e.g. euclidian) from the point to the line is small (by a user defined parameter).

What is the minimum number of line segments needed that satisfies the distance condition and how can the segments be determined. Is there a "good" heuristic which is simpler or more efficient while providing comparable results?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

Try polyline simplification.
For heuristics or other simplifications you might want to treat segments as resizeable, but for now objective is not that clear.
Here is demo of RDP.
Try it, merge your answer into question and then explain objective.

There is tradeoff between polyline complexity reduction and number of remaining points. Number of removed points depends on data and $\epsilon$.

If you want to find minimum, you have $N-1$ segments on $N$ points, and exact reduction depends on colinearity of points. Otherwise it is only approximation.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Seems like my intuitive solution described in my answer is exactly what RDP does. $\endgroup$
    – aKzenT
    Commented Sep 10, 2015 at 17:43
  • $\begingroup$ Something like that, but the part with minimal number of segments is confusing. $\endgroup$
    – Evil
    Commented Sep 10, 2015 at 17:48
  • $\begingroup$ What I meant is that at some number $N$ of line segments it will be impossible to create a result path which will not violate the rule of no point having a distance larger than $d$. This would be the "simpliest" polyline that satisfies the constraints. I'm not sure that RDP always produces this result. But this is just curiosity, for my application RDP should be good enough. $\endgroup$
    – aKzenT
    Commented Sep 10, 2015 at 17:58
  • $\begingroup$ Please try this RDP heuristic I think it suits better, and the answer to the best (meaning minimal number of segments) is No. $\endgroup$
    – Evil
    Commented Sep 10, 2015 at 18:51
  • $\begingroup$ For short argument - RDP uses local optimization not global, so it cannot guarantee optimal solution. It is used for simplicity and plausible look. If you are happy with answers given, consider accepting ;) $\endgroup$
    – Evil
    Commented Sep 10, 2015 at 18:54
1
$\begingroup$

You can use dynamic programming. Define $f(i,k)$ to be the "badness" of the best way to cover points $1..i$ using $k$ line segments. Then you can write down a recurrence relation for $f(i,k)$ in terms of $f(i-1,k-1),\dots,f(1,k-1)$, and then apply dynamic programming.

You'll have to fill in the details, because you haven't provided the particular objective function you specified, but I would expect that this approach will work to find an optimal solution.

Improve this answer
$\endgroup$
0
$\begingroup$

Thinking some more about this question, I came up with the following recursive algorithm, which might not produce the minimum, but seems to work very well in practice:

Start by taking the first and last point of the path and treating it as a line segment. Now for each point in between, calculate the distance from this point to the line segment and remember which point has the highest distance. If this distance is smaller than the maximum distance allowed, you are done. Otherwise, split the path at this point by connecting the start and end points to this point and execute the algorithm recursively on the two resulting line segments until all points are within the maximum distance.

I'm happy for better algorithms or thoughts on whether the result is a minimum.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.