以顺时针/逆时针方式对复杂的 2d 欧几里得点集合进行排序以形成闭合环

Question

这看起来像是一个重复的问题，但我尝试了已经存在的解决方案，但到目前为止似乎没有一个对我有用。.

这个解决方案给出了一个提示，但它只适用于常规几何。我有一个相当复杂的几何图形，我从中提取了未排序的边界点。

下面是我从几何图形中提取的几何图形和边界顶点的图片。

在边界顶点数据中，我们可以看到点是无序的。有没有办法可以顺时针/逆时针排列点，以便这些点在连续连接时形成闭合环？

我的目标是创建一个多边形或线性环，如here所述，然后查找任意欧几里得点是否位于多边形/环内

Answer 1

方法一：定义一个中心点，计算每个坐标和中心点之间的角度，然后按角度排序：import pandas as pd# Define function to compute angle between vectorsimport mathdef clockwiseangle_and_distance(point, origin = [0,0], refvec = [1,0]):&nbsp; &nbsp; # Vector between point and the origin: v = p - o&nbsp; &nbsp; vector = [point[0]-origin[0], point[1]-origin[1]]&nbsp; &nbsp; # Length of vector: ||v||&nbsp; &nbsp; lenvector = math.hypot(vector[0], vector[1])&nbsp; &nbsp; # If length is zero there is no angle&nbsp; &nbsp; if lenvector == 0:&nbsp; &nbsp; &nbsp; &nbsp; return -math.pi, 0&nbsp; &nbsp; # Normalize vector: v/||v||&nbsp; &nbsp; normalized = [vector[0]/lenvector, vector[1]/lenvector]&nbsp; &nbsp; dotprod&nbsp; = normalized[0]*refvec[0] + normalized[1]*refvec[1]&nbsp; &nbsp; &nbsp;# x1*x2 + y1*y2&nbsp; &nbsp; diffprod = refvec[1]*normalized[0] - refvec[0]*normalized[1]&nbsp; &nbsp; &nbsp;# x1*y2 - y1*x2&nbsp; &nbsp; angle = math.atan2(diffprod, dotprod)&nbsp; &nbsp; # Negative angles represent counter-clockwise angles so we need to subtract them&nbsp;&nbsp; &nbsp; # from 2*pi (360 degrees)&nbsp; &nbsp; if angle < 0:&nbsp; &nbsp; &nbsp; &nbsp; return 2*math.pi+angle, lenvector&nbsp; &nbsp; # I return first the angle because that's the primary sorting criterium&nbsp; &nbsp; # but if two vectors have the same angle then the shorter distance should come first.&nbsp; &nbsp; return angle, lenvectorimport pandas as pd# Compute the center pointcenter = pts.mean(axis=0)angle = []for i in range(len(pts)):&nbsp; &nbsp; ang, dist = clockwiseangle_and_distance(pts[i,:] - center, origin=[0,0], refvec=[1,0])&nbsp; &nbsp; angle.append(ang)df = pd.DataFrame(pts)df['angle'] = np.degrees(angle)df = df.sort_values(by='angle')df['clockwise_order'] = np.arange(len(df))import matplotlib.pyplot as plt# Create plot to show the ordering of the pointsplt.figure()df.plot(kind='scatter', x=0, y=1, s=100, alpha=0.5)plt.title('Points by clockwise order')for idx, row in df.iterrows():&nbsp; &nbsp; plt.gca().annotate('{:.0f}'.format(row['clockwise_order']), (row[0], row[1]),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ha='center', va='center_baseline', fontsize=6, color='k', fontweight='bold')plt.gca().annotate('Center', center,&nbsp; &nbsp; &nbsp; &nbsp; ha='center', va='center')如果这种顺时针顺序不能满足您的需求，请尝试方法 2。方法二：要按顺时针顺序对给定几何的点进行排序，使它们形成一个封闭的环，您可以执行以下操作：将数据集划分为象限选择一个中心点，使象限的其余点位于以中心点为中心的圆弧上按顺时针角度对每个象限进行排序按顺时针顺序放置每个象限# Compute the center pointcenter = pts.mean(axis=0)df = pd.DataFrame(pts)# Group points into quadrantsdf['quadrant'] = 0df.loc[(df[0] > center[0]) & (df[1] > center[1]), 'quadrant'] = 0df.loc[(df[0] > center[0]) & (df[1] < center[1]), 'quadrant'] = 1df.loc[(df[0] < center[0]) & (df[1] < center[1]), 'quadrant'] = 2df.loc[(df[0] < center[0]) & (df[1] > center[1]), 'quadrant'] = 3quadrant = {}for i in range(4):&nbsp; &nbsp; quadrant[i] = df[df.quadrant == i]# Intelligently choose the quadrant centersx = 35y = 5subcenter = [[ x,&nbsp; y],&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[ x, -y],&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[-x, -y],&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[-x,&nbsp; y]]# Compute the angle between each quadrant and respective center pointangle = {}points = {}df_sub = {}for j in range(len(quadrant)):&nbsp; &nbsp; angle[j] = []&nbsp; &nbsp; points[j] = quadrant[j][[0,1]]&nbsp; &nbsp; for i in range(len(points[j])):&nbsp; &nbsp; &nbsp; &nbsp; ang, dist = clockwiseangle_and_distance(points[j].values[i,:] - subcenter[j], origin=[0,0], refvec=[1,0])&nbsp; &nbsp; &nbsp; &nbsp; angle[j].append(ang)&nbsp; &nbsp; df_sub[j] = quadrant[j]&nbsp; &nbsp; df_sub[j]['angle'] = np.degrees(angle[j])&nbsp; &nbsp; df_sub[j] = df_sub[j].sort_values(by='angle')# Combine the data framesdf = pd.concat(df_sub)df['clockwise_order'] = np.arange(len(df))# Plot the points by clockwise orderimport matplotlib.pyplot as plt# Create plot to show the ordering of the pointsfig, axis = plt.subplots()df[[0,1]].plot(x=0, y=1, ax=axis, c='lightblue', legend=False, clip_on=False)df.plot(kind='scatter', x=0, y=1, s=100, ax=axis, c='lightblue', clip_on=False)plt.title('Points by quadrant in clockwise order')plt.axis('off')for idx, row in df.iterrows():&nbsp; &nbsp; plt.gca().annotate('{:.0f}'.format(row['clockwise_order']), (row[0], row[1]),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ha='center', va='center_baseline', fontsize=6, color='k', fontweight='bold')plt.gca().annotate('Center', center,&nbsp; &nbsp; &nbsp; &nbsp; ha='center', va='center')for i in range(len(subcenter)):&nbsp; &nbsp; plt.scatter(subcenter[i][0], subcenter[i][1], alpha=0.5, s=80, marker='s')&nbsp; &nbsp; plt.gca().annotate('Quadrant \n'+str(i)+'\n', subcenter[i],&nbsp; &nbsp; &nbsp; &nbsp; ha='center', va='center_baseline', color='k', fontsize=8)# Plot with axis equally-spaceddf2 = df[[0,1]].reset_index(drop=True)df2.loc[len(df2),:] = df2.loc[0,:]df2.plot(x=0, y=1, c='k', legend=False, clip_on=False)plt.axis('equal')plt.axis('off')如果这不能满足您的需求，您可能必须手动订购坐标。