Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I happened to see an answer to "Sort array of points in clockwise", could you please elaborate the 4th point of that answer:

  • sort points relative to their a value, using qsort for instance.

How do I do the above step?

I'm looking for an algorithm to sort list of points in counter-clockwise.

share|improve this question
    
Could you add a link to what answer you're referring to? –  bummzack Aug 27 '12 at 9:21
    
I guess points are two dimensional data. So you could calculate angle between center and point. And since angle is one dimensional data now you can sort it using qsort. –  aisbaa Aug 27 '12 at 9:40
    
Sorting requires comparison (<, ==, >), its not obvious how to compare two dimensional data, that's why I suggest you to get angles between point centre and x or y axis. –  aisbaa Aug 27 '12 at 9:43
    
It seems that you are just asking how to sort an array of objects. It is not really gamedev-related. –  Sam Hocevar Aug 27 '12 at 12:44
    
@SamHocevar sorting primitives is crucial in developing anything that deals with large multidimensional datasets - especially games. –  David Lively Aug 27 '12 at 21:51
show 8 more comments

2 Answers

up vote 0 down vote accepted

Not familiar with the referenced article, but what I would do is:

  1. Find the center of the point cloud
  2. Use atan2 with the difference between each point and the center to find the angle each makes with the center
  3. Sort by angle. You can either store the angle calculated in step 2 with each point (a Z value in a 3d coordinate created from each 2d coordinate is a convenient way to do this) or just skip step 2 and recalculate the angle in your sort comparer
  4. Done!
share|improve this answer
add comment

The full quote from that answer is (I added the numbers for easy reference):

  1. let P[0], P[1], ... P[n-1] be the list of points to sort
  2. let M be the barycenter of all points
  3. compute a[0], a[1], ... a[n-1] such that a[i] = atan2(P[i].y - M.y, P[i].x - M.x);
  4. sort points relative to their a value, using qsort for instance.

The "a value" part of step 4 is referencing step 3. So, in step 4 it's saying "sort the points array based on the values in the array you made in step 3 (using something like quick sort)."

Now, if sorting that array of values will get you the clockwise order of points, then sorting it in reverse order will give you the points in a counter-/anti-clockwise direction.

Hopefully that clears it up a bit for you.

share|improve this answer
1  
Why the downvote? –  Richard Marskell - Drackir Aug 28 '12 at 11:44
    
I'm guessing its because you tried to answer the question. –  David Lively Sep 10 '12 at 23:38
    
@DavidLively I guess we're in the same boat then. :( –  Richard Marskell - Drackir Sep 11 '12 at 1:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.