如何在Python中按顺时针/逆时针方向对点列表进行排序？

Question

我有一个坐标点的列表，我想把它们按顺时针方向/逆时针方向排序。

这就是我提到的清单：

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

这些坐标点将帮助我绘制物体的直线段。下面是一幅插图的图片。正如你所看到的，我在这张图片中把列表中的所有点都记下来了。

​

​

我的目标是对这些坐标点进行排序，以创建几个直线段。因此，我的预期结果如下：

逆时针方向：[(985, 268), (998, 425), (112, 316), (998, 448), (1018, 453), (1279, 577), (1196, 477), (1161, 443), (998, 255), (986, 0), (983, 230), (830, 0)]

顺时针方向：[(985, 268), (830, 0),(983, 230), (986, 0), (998, 255), (1161, 443), (1196, 477), (1279, 577), (1018, 453), (998, 448), (112, 316), (998, 425)]

到目前为止，我使用了一个名为https://www.baeldung.com/cs/sort-points-clockwise的网站作为参考，并编写了以下代码，但它不起作用：

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)]
'''

虽然我将中心点(962,324)加回上述每个点，但它们仍然不是期望的结果。

非常感谢。

Answer 1

试着看看这个代码片段是否对你有帮助。(不过，这是，而不是直接回答)

这种算法被称为格雷厄姆扫描。该算法求出沿边界排列的凸包的所有顶点。希望你能适应你的需要。

Notes scipy有一些很好的库。你也可以调查一下。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()

Answer 2

我已经在评论中链接了7个相关/重复的问题。这些问题有几种不同的方法有有趣的答案。两种主要的方法是“计算凸包”方法和“围绕中心”方法。

由于丹尼尔浩已经发布了一个凸包方法的答案，让我给一个中间的方法的答案。

基本算法如下：

• 定义了一个新的点C，称为中心；C可能是任何东西，C的准确选择将影响结果，特别是如果由点定义的多边形不是凸的。C的一个简单选择是取点列表的重心(即取列表中坐标的平均值)，
• 对列表中的每一个点P，计算x轴和矢量CP之间的定向角alpha_P。
• 按其相关联的角度对点列表进行排序；按逆时针方向的递增顺序，或顺时针方向按递减顺序排列。

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

我强烈鼓励你们使用不同的中心坐标值，看看这是如何影响点的最终顺序的。

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()

​

​