How to simplify / optimize a 3D path?

Question

I have a bunch of points in 3d (an array that contains objects with properties x, y, z).

My problem is that there are many unnecessary points, as shown in the image below:

_{(source: lifesine.eu )}

How can I clear this path?

At the moment, the first thing that comes to mind is

• create an array for an optimized path
• Circle all the points, starting at index 1 instead of 0, and get the "direction" for the path. If the direction changes, add the last of the two points (current, not previous) to the optimized array.

The advantage is that the points are stored in drawing order, so they represent a path, and not just random (not sorted) points.

Note. I am using ActionScript 3, but I can understand the syntax in other languages ​​or pseudo-code.

Thanks!

Answer 1

Check the Ramer-Douglas-Picker algorithm

Answer 2

although all points starting at index 1 instead of 0 get a "direction" for the path. If the direction changes, add the last of the two points (current, not previous) to the optimized array.

If you think this will help, you should think that the Earth is flat ,-)

Try this: if the path changes a little, skip every second point, thus getting half the points. If the path changes noticeably, keep the nodes as they are. Then repeat with half the threshold that “a little (your lengths are doubled, so your sensitivity should increase) until you make any changes after the run.

Answer 3

I would go with your suggestion, but keep the current and previous point when the direction changes.

Thus, you get the first and last point of each line segment.

Answer 4

I think your initial idea is great. I would add / change two things:

1) I would choose the distance threshold in your algorithm: only when the current test point is at some minimum distance from your last "good" point, you should check it. Depending on the data source of your path (perhaps a magnetic tracker?), Stationarity may reflect poorly on your source data due to measurement noise. This can lead to relatively large changes in direction in a very small area, which essentially do not make sense.

2) When you find a sufficiently large change, do not add the current test point (as you said), but the previous one. Otherwise, you may end up distorting the path. Example (in 2D): a path consisting of (0,0) → (1,0) → (2,0) → (3,0) → (4,0) → (5,5) will end as (0, 0) → (5.5) using your methods, which I would not consider a good representation of the path. It would be better (0, 0) → (4.0) → (5.5).