1

How do you check if points are sorted in circular order (regardless of clockwise or counter-) (assuming they don't exactly form one whole circle, what matters is the points are sorted in a circular order)?

enter image description here

tjvg1991
  • 356
  • Presumably the points all lie on a common circle? – Travis Willse Apr 30 '15 at 08:35
  • 1
    Also, how are the points specified? Do you have, say, $(x, y)$ coordinates for each of them? – Travis Willse Apr 30 '15 at 08:36
  • yes, there are (x,y) coordinates for each of them. They don't have to lie on a common circle. @Travis – tjvg1991 May 04 '15 at 04:04
  • If they don't lie on a common circle, what defines the reference point for determining circular order? Different choices of reference point will, in general, lead to different orders. – Travis Willse May 04 '15 at 04:27
  • NB if the vertices are the vertices of a convex polygon (i.e., none of the points is in the interior of the convex hull of the remaining points), as is the case in the picture, then the order is the same for any reference point inside the polygon, but this is a strong restriction on the configurations of points. – Travis Willse May 04 '15 at 04:29
  • @tjvg1991 That the points are specified by coordinates , seems to be an important point. Can you add it to your post? Also request you to address the answer below. Thank you. – Sarvesh Ravichandran Iyer May 06 '21 at 19:19

1 Answers1

1

Let $c$ be the barycenter of the points $p_1,p_2,\dots,p_n$. Then the points are sorted in circular order when $ccw(c,p_i,p_{i+1}) > 0 $ for all $i$, with $p_{n+1}=p_1$. Here $ccw$ is the standard geometric primitive.

Any point in the convex hull works as a center $c$. For instance, the lowest point among the given points.

lhf
  • 216,483