algorithm to sort a bunch of points which form a closed contour

algorithm to sort a bunch of points which form a closed contour

Post by tejas » Fri, 05 Mar 2004 18:48:45


Hi,

I have a bunch of points which represents a closed contour but the
points are not sorted. So when I use my display algorithm to draw a
line between consecutive points obviously it fails.

Q) Is there an algorithm I could use to sort the points in either
clockwise or anticlockwise direction ?

Thanks in advance,

Tejas
 
 
 

algorithm to sort a bunch of points which form a closed contour

Post by Robin Tuck » Fri, 05 Mar 2004 20:42:21

Here is my naive suggestion:

Find the centroid of the contour (add up all the points and divide by the
number of points!),
Choose an point in the set,
For the rest of the points,
Calculate the angle between the vector from point to centroid and the
vector from each point to the centroid.

Sort the points by the smallest angle first, place the initial chosen point
at the start.

I'm no expert - I have no idea if this will work. It certainly won't work
when you have a contour shared by two peaks (an 8 shape for instance). I
guess it will only work on vaugely circular contours.

 
 
 

algorithm to sort a bunch of points which form a closed contour

Post by Hans-Bernh » Sat, 06 Mar 2004 00:07:50


That very much depends on the allowed shapes of that contour. If it's
known to be convex, it's trivial. If not, it's an ill-defined
problem, because there are quite a lot of polygons you can build from
a given cloud of vertices, and you don't provide any hint which of
them might be the right one.

Your best bet is to re-investigate where those points came from: do
you really have *no* idea which pairs of those are neighbours along
the contour line?

--
Hans-Bernhard Broeker ( XXXX@XXXXX.COM )
Even if all the snow were burnt, ashes would remain.
 
 
 

algorithm to sort a bunch of points which form a closed contour

Post by Robin Tuck » Sat, 06 Mar 2004 00:46:12

Ahh yes, I remember now. There is a paper in Graphics Gems I concerning
reconstruction of surfaces from contour data. However, I can't remember if
the paper referred to assumes the contours are already ordered.

http://www.yqcomputer.com/
 
 
 

algorithm to sort a bunch of points which form a closed contour

Post by hoffman » Sat, 06 Mar 2004 03:26:34


Very reasonable, IMO, for many practical tasks.
The atan2 angles -pi..+pi should be mapped into the range 0..2*pi.
The method is not restricted to convex contours.
E.g. it would work for an ordinary toothed wheel (for which the tooth
width is not smaller at the basis of the tooth).

I suspect the wanted contour has the shortest total "arc" length
(once we have chosen a direction cw or ccw ).

A direct comparison of the sum of the squares of segment lengths by
trying all possible connections is possible, though not economical.

Eventually Bellman Dynamic Programming can solve this task with
less calculations.

Best regards --Gernot Hoffmann
 
 
 

algorithm to sort a bunch of points which form a closed contour

Post by David Epps » Sat, 06 Mar 2004 03:38:20

In article < XXXX@XXXXX.COM >,



Try http://www.yqcomputer.com/

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

algorithm to sort a bunch of points which form a closed contour

Post by tejas » Mon, 08 Mar 2004 09:30:36

Thank you all for you reply. Sorting the angle wrt the centre works pretty well.

Thanks again,
Tejas