CODEWITHSUNDEEP
algorithmoptimizationpath
George Profenza
George Profenza

Reputation: 51867

How to simplify/optimize a 3d path?

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

My problem is that there are a lot of unnecessary points as illustrated in the image bellow:

3d path
(source: lifesine.eu)

How can I cleanup this path ?

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

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

Note: I am using actionscript 3, but I can understand syntax in other languages or pseudo code.

Thank you!

Upvotes: 4

Views: 1006

Answers (4)

P Shved
P Shved

Reputation: 99374

loop though all the points starting with index 1 instead of 0, and get the 'direction' for the path. If the direction changes, add the last of the two points( the current, not the previous ) to the optimized array.

If you think it's going to help, you should either think that the Earth is flat ;-)

Try this: if the path changes slightly, then skip every second point, thus finishing with twice as less points. If path changes appreciably, keep nodes as is. Then repeat with half of the threshold of what "slightly is (your lengths are doubled, so your sensitivity must increase) until you make no changes after a run.

Upvotes: 1

Andreas F
Andreas F

Reputation: 404

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

1) I would throw in a distance threshold into your algorithm: Only when the currently tested point is some minimum distance away from your last 'good' point, should you even test it. Depending on the source of your path data (a magnetic tracker perhaps?), stationarity may not be reflected well in your raw data, due to measurement noise. This might lead to relatively large directional changes in a very small area that are essentially meaningless.

2) When you detect a large enough change, do not add the currently tested point (as you suggested), but the previous one. Otherwise you may end up misrepresenting the path. An example (in 2D): the path consisting of (0,0)->(1,0)->(2,0)->(3,0)->(4,0)->(5,5) would end up as (0,0)->(5,5) using your methods, which I wouldn't consider a good representation of the path. Better would be (0, 0)->(4,0)->(5,5).

Upvotes: 0

Stephen Nutt
Stephen Nutt

Reputation: 3306

Check out Ramer-Douglas-Peucker algorithm

Upvotes: 7

mbeckish
mbeckish

Reputation: 10579

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

That way, you end up with the first and last point of each line segment.

Upvotes: 0

Related Questions