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?
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
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-
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
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):
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