## Problem related to sorting

### Problem related to sorting

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,
--
Ishtiaq Rasool Khan
The University of Kitakyushu

### Problem related to sorting

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?

http://www.cis.ohio-state.edu/~tamaldey/curverecon.htm

--
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science

### Problem related to sorting

Quote:> 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.

This is a heavily under-specified problem.  You say you want to make
"a smooth curve", but what you really get is a closed polyline, which
is anything else but smooth by definition --- it has undifferentiable
corners.

Next problem is that there are very many closed polylines that could
be drawn to connect any given set of more than 3 vertices in the
plane.  You need a computable criterion to decide which of those to
prefer, and (for yourself) a good explanation why that's the right
criterion to use.  Nearest-neighborship may be usable, but the turn
angles at vertices may be better.  Or maybe you need the sagitta
(deviation of vertex B in a triplet ABC of consequtive polyline
vertices from the line AC).  And you'll need a method to combine these
"non-smoothness" measures at all corners into a single number.

Do you want to allow the polyline to intersect itself?  More than
once?  If so, what's the penalty per self-intersection, so the
algorithm would favour non self-intersecting solutions?

--

Even if all the snow were burnt, ashes would remain.

### Problem related to sorting

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

### Problem related to sorting

Thanks guys for your help. As I am new to this field (and not a native
english speaker), I perhaps used the word smooth in error.

I get some range images of an object from different sides. Then I combine
them (something similar to ICP) and get a complete 3D model. Now I want a
layer of points, say at height y, in x-z plane. I can get the layer but
points are not in order. Obviously the curve I want will not intersect
itself, neither it should leave any point unconnected. Nearesrt neighbour
works fine in most of the cases but if the object has very sharp curves,
then it fails some times to connect all the points.

Thanks to your replies I have got some good ideas, and I hope I will be able
to solve the problem. The idea coming to my mind is to connect the points
using nearest neighbour algorithm and then take the non-connected points and
insert them next to their nearest neighbours.

Best regards,
Ishtiaq.

### Problem related to sorting

Quote:> I get some range images of an object from different sides. Then I combine
> them (something similar to ICP) and get a complete 3D model. Now I want a
> layer of points, say at height y, in x-z plane. I can get the layer but
> points are not in order.

AFAICS that means you either didn't actually have a 3D model in the
first place, or your method of extracting the cross-section at
constant y neglects crucial information contained in that model.
Fixing the broken output of your method is not a very good plan, then
--- you should fix the method that produce that cross-section,
--

Even if all the snow were burnt, ashes would remain.

Hi,
I created a program that reads in 3D triangles from a RAW file, and displays
them on the screen.

I now want to sort these triangles, based on their Average Z distance.  Here's
my structure:

typedef struct {
float x, y, z;        // Points in 3-space
float sx,sy;  // 3-space points converted for screen display.
} Vertex;

typedef struct {
Vertex p1,p2,p3;      // Three vertices
float AverageZ;       // Average Z distance of this triangle.
} Triangle;

I then declare a bunch of triangles like so (not efficient, but this is a test):

Triangle t[1000];

I am using qsort() to sort these triangles, but what I want to sort the average Z
values, which are computed by taking the Z value of each Point (p1,p2,p3),
adding them up and dividing them by 3.

How do I sort these?  I know how to sort regular arrays, but how do I do this?

BTW, I know this is a C/C++ question, but I have reasons for posting here
(stupid reason, that is).

Thanks for taking the time!
Bye!

****************************************************