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

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.

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.

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.

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/

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/

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

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

Try http://www.yqcomputer.com/

--

David Eppstein http://www.yqcomputer.com/ ~eppstein/

Univ. of California, Irvine, School of Information & Computer Science

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

Thanks again,

Tejas

Thanks again,

Tejas

1. Why does Form-A's instance fire Form-B's event??

2. Printing report b after report a prints using report a's variables

3. using "if" but omitting the #n/a's

4. equation that will filter out #N/A's

6. "Matching" column A's values in column B

8. How do I only get valid "answers" in a VLOOKUP function (no #N/A's

9. 'Send As' messages stay in User A's sent folder.

11. CAnnot type lowercAse 'A's Anymore (solved!)

13. Try Again / VLOOKUP without N/A's

14. Host would occasionally fail to resolve A's rec.Help!

15. regexp for reg language that has an even number of a's and b's

7 post • Page:**1** of **1**