python - 如何在Python中顺时针/逆时针对点列表进行排序?
问题描述
我得到了一个坐标点列表,我想按顺时针/逆时针对它们进行排序。
这是我提到的清单:
[(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-顺时针作为参考并编写了以下代码,但它不起作用:
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) 添加到上述每个点,但它们仍然不是预期的结果。
非常感谢。
解决方案
尝试查看此代码段是否对您有所帮助。(虽然这不是一个直接的答案)
该算法称为格雷厄姆扫描。该算法找到沿其边界排序的凸包的所有顶点。希望您可以根据自己的需要进行调整。
[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()
推荐阅读
- c++ - C++ 静态库未在 Mac 上的 xcode 中编译
- ssl - ISPConfig 不接受新证书
- coldfusion - Coldfusion动态列名传递给函数
- r - 从一列/行值等于列名的单元格中提取值
- java - 休眠无法找到具有逻辑名称的列
- lync - UCMA 5.0 - 如果会议由 UCMA 应用程序创建,文件共享将不起作用
- android - ConstraintLayout 内容卡在屏幕中间
- css - Safari 和字体功能设置:“lnum”失败
- mysql - 排除相同的值和特定的规则集查询
- javascript - 为什么此代码不显示文本字段中的 expexres 值