1
\$\begingroup\$

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.

\$\endgroup\$
13
  • \$\begingroup\$ Could you add a link to what answer you're referring to? \$\endgroup\$
    – bummzack
    Commented Aug 27, 2012 at 9:21
  • \$\begingroup\$ 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. \$\endgroup\$
    – aisbaa
    Commented Aug 27, 2012 at 9:40
  • \$\begingroup\$ 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. \$\endgroup\$
    – aisbaa
    Commented Aug 27, 2012 at 9:43
  • \$\begingroup\$ It seems that you are just asking how to sort an array of objects. It is not really gamedev-related. \$\endgroup\$ Commented Aug 27, 2012 at 12:44
  • \$\begingroup\$ @SamHocevar sorting primitives is crucial in developing anything that deals with large multidimensional datasets - especially games. \$\endgroup\$
    – 3Dave
    Commented Aug 27, 2012 at 21:51

2 Answers 2

0
\$\begingroup\$

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!
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Why the downvote? \$\endgroup\$ Commented Aug 28, 2012 at 11:44
  • \$\begingroup\$ I'm guessing its because you tried to answer the question. \$\endgroup\$
    – 3Dave
    Commented Sep 10, 2012 at 23:38
  • \$\begingroup\$ @DavidLively I guess we're in the same boat then. :( \$\endgroup\$ Commented Sep 11, 2012 at 1:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .