Quote:> Hi all,

> I am looking for an algorithm which places some given points in order, to

> make a smooth curve.

> For example consider the following points:

> (1,3), (2,2), (1,1), (2,0)

> If they are given in a random order, how can they be brought to above order.

> The way which comes to my mind is to start with the top most point and then

> find its nearest point and so on. They will in some cases leave some points,

> like in the following set

> (1,4), (1,3), (3,3), (3,2), (1,2), (1,0)

> two points (3,3), (3,2) will be left unconnected.

> Is there some better and more efficient way?

> Regards,

A random point cloud can hardly be brought into just one reasonable

order. Now lets assume, the points belong originally to a continuous

path, but they are unordered and affected by random deviations.

Furtheron lets assume that they can be brought into an order which

LOOKS reasonably. It doesnt matter if LOCALLY a different sequence

seems to be possible - important is the GLOBAL sequence.

This can probably be done in 2D by nearest neighbour search, under the

above assumptions.

The angle between line segments shouldnt be used for the search, because

random deviations can cause "sharp" edges.

If the point sequence forms a closed polygon, then a Fourier series

delivers all kinds of smooth averaged paths, by ignoring higher har-

monics.

Now the polyline: we can CLOSE the polyline by a Bzier curve. This

curve adds a smooth connection between the ends of the polyline with C0

and C1 continuity. Therefore the content of higher harmonics is not

increased.

The smoothing of polylines was often discussed here. The Bzier/Fourier

method was not mentioned, as far as I know.

Some examples are here (preliminary doc, 120kB):

http://www.fho-emden.de/~hoffmann/softpoly23062003.pdf

A general solution (unordered point cloud) cannot be expected. A little

a priori knowledge about the generation of the points would be helpful.

Best regards --Gernot Hoffmann