How to sort a list of points in clockwise/anti-clockwise in Python?

Question

I got a list of coordinate points, and I would like to sort them in either clockwise/anti-clockwise.

This is the list I mentioned:
[(985, 268), (112, 316), (998, 448), (1018, 453), (1279, 577), (1196, 477), (1161, 443), (986, 0), (830, 0), (983, 230), (998, 425), (998, 255)]

These coordinate points will help me to draw the line segments of an object. Below is an image for illustration. As you can see, I have marked down all the points in the list in this image.

And my goal is to sort these coordinate points in order to create several line segments. Therefore, my expected result would be as follow:
Anti-Clockwise Direction: [(985, 268), (998, 425), (112, 316), (998, 448), (1018, 453), (1279, 577), (1196, 477), (1161, 443), (998, 255), (986, 0), (983, 230), (830, 0)]

Clockwise Direction: [(985, 268), (830, 0),(983, 230), (986, 0), (998, 255), (1161, 443), (1196, 477), (1279, 577), (1018, 453), (998, 448), (112, 316), (998, 425)]

So far, I have taken a website, https://www.baeldung.com/cs/sort-points-clockwise, as ref and written the following codes but it does not work:

def getDistance(pt1 , pt2):
    x = pt1[0] - pt2[0]
    y = pt1[1] - pt2[1]
    return math.sqrt(x*x+y*y)

def getAngle(pt_center, pt):
    x = pt[0] - pt_center[0]
    y = pt[1] - pt_center[1]
    angle = math.atan2(y,x)

    if angle <= 0:
        angle = 2*math.pi + angle

    return angle

def comparePoints(pt_center, pt1, pt2):
    angle1 = getAngle(pt_center, pt1)
    angle2 = getAngle(pt_center, pt2)

    if angle1 < angle2:
        return True

    d1 = getDistance(pt_center, pt1)
    d2 = getDistance(pt_center, pt2)

    if angle1 == angle2 and d1 < d2:
        return True

    return False

final_concave_points_list = []
for items in final_concave_points:
    final_concave_points_list.append([])
    for points in items:
        final_concave_points_list[-1].append(list(points))

pt_center = [0,0]
point = []
points = final_concave_points_list[0]
for pt in points:
    pt_center[0] = pt_center[0] + pt[0]
    pt_center[1] = pt_center[1] + pt[1]

pt_center[0] = pt_center[0] / len(points)
pt_center[1] = pt_center[1] / len(points)

for pt in points:
    pt[0] = pt[0] - pt_center[0]
    pt[1] = pt[1] - pt_center[1]
    point.append((pt[0], pt[1]))
print(point)

'''
[(23.0, -56.333333333333314), (-850.0, -8.333333333333314), (36.0, 123.66666666666669), (56.0, 128.66666666666669), (317.0, 252.66666666666669), (234.0, 152.66666666666669), (199.0, 118.66666666666669), (24.0, -324.3333333333333), (-132.0, -324.3333333333333), (21.0, -94.33333333333331), (36.0, 100.66666666666669), (36.0, -69.33333333333331)]
'''

points = scaled_point_list[0]
angle_list = []
for concave in points:
    angle = getAngle((0,0), concave)
    angle_list.append(angle)
print(angle_list)

'''
[5.102097551727555, 3.15100414040828, 1.2882413743253092, 1.1612360403462985, 0.6735857636846376, 0.5790742693677309, 0.5389402114087971, 4.78632801804263, 4.325513262653661, 4.932184051908722, 1.2283997388640362, 5.193276260580025]
'''

zipped_list = zip(angle_list, points)
sorted_zipped_lists = sorted(zipped_list)
sorted_list1 = [element for _, element in sorted_zipped_lists]
print(sorted_list1)

'''
[(199, 119), (234, 153), (317, 253), (56, 129), (36, 101), (36, 124), (-850, -8), (-132, -324), (24, -324), (21, -94), (23, -56), (36, -69)]
'''

Although I add back the center point (962, 324) to each of the above points, they are still not the desired result.

Thanks a lot.

Hi! I remember this question having been asked several times, both here on StackOverflow, and over at https://cs.stackexchange.com . There were a lot of interesting answers with several different possible algorithms. — Stef, Sep 08 '21 at 10:19
[lua: Sort points in clockwise order?](https://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order); [How to sort all polygon points by clockwise/ anticlockwise direction?](https://stackoverflow.com/questions/57453943/how-to-sort-all-polygon-points-by-clockwise-anticlockwise-direction); [Sort Four Points in Clockwise Order](https://stackoverflow.com/questions/242404/sort-four-points-in-clockwise-order); [C#: Sort 2d points in a list clockwise](https://stackoverflow.com/questions/22435397/sort-2d-points-in-a-list-clockwise); — Stef, Sep 08 '21 at 10:22
[Sort points in counter-clockwise in javascript](https://stackoverflow.com/questions/45660743/sort-points-in-counter-clockwise-in-javascript); [How to sort vertices of a polygon in counter clockwise order?](https://math.stackexchange.com/questions/978642/how-to-sort-vertices-of-a-polygon-in-counter-clockwise-order); [Sorting array of points in clockwise order](https://gamedev.stackexchange.com/questions/13229/sorting-array-of-points-in-clockwise-order) — Stef, Sep 08 '21 at 10:23
@DanielHao Yes, I would. Would you mind to share the approach — Hang, Sep 08 '21 at 13:08
@Stef Indeed. Maybe I have overlooked some of them, let me read the link you pasted again. Thanks! — Hang, Sep 08 '21 at 13:09
@CheTou - just post below, see if that's helpful... Let me know. — Daniel Hao, Sep 08 '21 at 13:17
Note that you say *"I have [...] written the following codes but it does not work"* in your question. That is not very helpful. "It doesn't work" can mean a lot of different things. How did it not work? How did the result differ from your expectations? See also: [What do you mean it doesn't work?](https://meta.stackexchange.com/questions/147616/what-do-you-mean-it-doesnt-work) — Stef, Sep 08 '21 at 13:41
Do you determine the center point dynamically or it's an static input. Sorting based a specific point is easy. Get the angle of each point and sort them. To find the center point you need to create a bounding box and find the center and then get the closest point. That's more work. — Shiplu Mokaddim, Sep 08 '21 at 14:11
@Stef what I mean it doesn’t work is that the sorting result is not the same as I expected. For example, the result of mine is that [(1161, 443), (1196, 477), (1279, 577), (1018, 453), (948, 425)…..] However, (948, 448) should be the point followed after (1018, 453). I am wondering whether the approach of sorting the angle between the center point and the points is wrong or not. — Hang, Sep 08 '21 at 15:25
@CheTou The centre-point approach is very dependent on the chosen centre-point (I edited my answer with three different centre-points so you can see the different results). That doesn't mean it's "wrong". You say, *"(948, 448) should be the point followed after (1018, 453)"*. How do you know? The problem of sorting points in clockwise order is inherently ill-defined, as illustrated by different approaches or different choices of parameters giving different results. If you have more insight on your problem (and what the "correct" solution "should" be), then [...] — Stef, Sep 08 '21 at 16:48
[...] If you have more insight on your problem, then you should include this insight in your algorithm. If you just pick an arbitrary algorithm and feed it arbitrary parameters (such as an inappropriate centre-point), then there is no reason the solution will satisfy you. Perhaps by choosing an appropriate centre-point, you can find a solution such that (948, 448) ends up after (1018, 453). The fact that you know that you want these two points in this order shows that you know more about your problem than you have said in your question. — Stef, Sep 08 '21 at 16:51
@Stef Thanks for telling me that I should give more insight into my problem. The points in the list I given are some concave points of the object, which is a hair. Beforehand, I got many coordinate points in order to get the contour of the object. And I would like to get a line segment by using two concave points for splitting the coordinate points. For example, (1018, 453) and (948, 448), then I can have a line segment presented in the form of list, like [(1018, 453), ......, (948, 448)]. Thus, there are many points between these two points. I can know all the points of each line segment. — Hang, Sep 09 '21 at 03:33

Daniel Hao · Answer 1 · 2021-09-09T02:23:43.457

Try to see if this code snippet will help you. (it's not a direct answer though)

This algorithm is called the Graham scan. The algorithm finds all vertices of the convex hull ordered along its boundary. Hopefully you can adjust to your needs.

[Notes] scipy has some good lib. that you may look into too. https://docs.scipy.org/doc/scipy/reference/spatial.html

from collections import namedtuple  
import matplotlib.pyplot as plt  

Point = namedtuple('Point', 'x y')


class ConvexHull(object):  
    _points = []
    _hull_points = []

    def __init__(self):
        pass

    def add(self, point):
        self._points.append(point)

    def _get_orientation(self, origin, p1, p2):
        '''
        Returns the orientation of the Point p1 with regards to Point p2 using origin.
        Negative if p1 is clockwise of p2.
        :param p1:
        :param p2:
        :return: integer
        '''
        difference = (
            ((p2.x - origin.x) * (p1.y - origin.y))
            - ((p1.x - origin.x) * (p2.y - origin.y))
        )

        return difference

    def compute_hull(self):
        '''
        Computes the points that make up the convex hull.
        :return:
        '''
        points = self._points

        # get leftmost point
        start = points[0]
        min_x = start.x
        for p in points[1:]:
            if p.x < min_x:
                min_x = p.x
                start = p

        point = start
        self._hull_points.append(start)

        far_point = None
        while far_point is not start:

            # get the first point (initial max) to use to compare with others
            p1 = None
            for p in points:
                if p is point:
                    continue
                else:
                    p1 = p
                    break

            far_point = p1

            for p2 in points:
                # ensure we aren't comparing to self or pivot point
                if p2 is point or p2 is p1:
                    continue
                else:
                    direction = self._get_orientation(point, far_point, p2)
                    if direction > 0:
                        far_point = p2

            self._hull_points.append(far_point)
            point = far_point

    def get_hull_points(self):
        if self._points and not self._hull_points:
            self.compute_hull()

        return self._hull_points

    def display(self):
        # all points
        x = [p.x for p in self._points]
        y = [p.y for p in self._points]
        plt.plot(x, y, marker='D', linestyle='None')

        # hull points
        hx = [p.x for p in self._hull_points]
        hy = [p.y for p in self._hull_points]
        plt.plot(hx, hy)

        plt.title('Convex Hull')
        plt.show()


def main():  
    ch = ConvexHull()
    points = [(985, 268), (112, 316), (998, 448), (1018, 453), (1279, 577), (1196, 477),
              (1161, 443), (986, 0), (830, 0), (983, 230), (998, 425), (998, 255)]
    
    for point_x, point_y in points:        # 
        ch.add(Point(point_x, point_y))

    print("Points on hull:", ch.get_hull_points())
    ch.display()


if __name__ == '__main__':  
    main()

Stef · Answer 2 · 2021-09-08T13:50:27.673

I already linked 7 related/duplicate questions in the comment. These questions have interesting answers with several different approaches. The two main approaches are the "compute the convex hull" approach, and the "around a center" approach.

Since Daniel Hao already posted an answer with a convex hull approach, let me give an answer with a center approach.

The basic algorithm is the following:

Define a new point C called the centre; C might be anything, and the exact choice of C will affect the result, especially if the polygon defined by your points is not convex. A simple choice for C is to take the barycentre of your list of points (i.e., take the average of the coordinates in your list).
For every point P in your list, calculate the oriented angle alpha_P between the x-axis and vector CP.
Sort the list of points by their associated angle; in increasing order for counterclockwise, or in decreasing order for clockwise.

Implementation in python:

import matplotlib.pyplot as plt  # plot, show
import math                      # atan2

points = [(985, 268), (112, 316), (998, 448), (1018, 453), (1279, 577), (1196, 477), (1161, 443), (986, 0), (830, 0), (983, 230), (998, 425), (998, 255)]

def sort_counterclockwise(points, centre = None):
  if centre:
    centre_x, centre_y = centre
  else:
    centre_x, centre_y = sum([x for x,_ in points])/len(points), sum([y for _,y in points])/len(points)
  angles = [math.atan2(y - centre_y, x - centre_x) for x,y in points]
  counterclockwise_indices = sorted(range(len(points)), key=lambda i: angles[i])
  counterclockwise_points = [points[i] for i in counterclockwise_indices]
  return counterclockwise_points

I strongly encourage you to play with different values for the coordinates of the centre, and see how that affects the final order of the points.

points = sort_counterclockwise(points)
plt.plot([x for x,_ in points], [y for _,y in points])
plt.show()

points = sort_counterclockwise(points, (0,0))
plt.plot([x for x,_ in points], [y for _,y in points])
plt.show()

points = sort_counterclockwise(points, (1000, 200))
plt.plot([x for x,_ in points], [y for _,y in points])
plt.show()

How to sort a list of points in clockwise/anti-clockwise in Python?

2 Answers2

Linked