這看起來像是一個重復的問題，但我嘗試了已經存在的解決方案，但到目前為止似乎沒有一個對我有用。.這個解決方案給出了一個提示，但它只適用于常規(guī)幾何。我有一個相當復雜的幾何圖形，我從中提取了未排序的邊界點。下面是我從幾何圖形中提取的幾何圖形和邊界頂點的圖片。在邊界頂點數據中，我們可以看到點是無序的。有沒有辦法可以順時針/逆時針排列點，以便這些點在連續(xù)連接時形成閉合環(huán)？我的目標是創(chuàng)建一個多邊形或線性環(huán)，如here所述，然后查找任意歐幾里得點是否位于多邊形/環(huán)內
1 回答
人到中年有點甜
TA貢獻1895條經驗 獲得超7個贊
方法一：
定義一個中心點，計算每個坐標和中心點之間的角度，然后按角度排序：
import pandas as pd
# Define function to compute angle between vectors
import math
def clockwiseangle_and_distance(point, origin = [0,0], refvec = [1,0]):
# Vector between point and the origin: v = p - o
vector = [point[0]-origin[0], point[1]-origin[1]]
# Length of vector: ||v||
lenvector = math.hypot(vector[0], vector[1])
# If length is zero there is no angle
if lenvector == 0:
return -math.pi, 0
# Normalize vector: v/||v||
normalized = [vector[0]/lenvector, vector[1]/lenvector]
dotprod = normalized[0]*refvec[0] + normalized[1]*refvec[1] # x1*x2 + y1*y2
diffprod = refvec[1]*normalized[0] - refvec[0]*normalized[1] # x1*y2 - y1*x2
angle = math.atan2(diffprod, dotprod)
# Negative angles represent counter-clockwise angles so we need to subtract them
# from 2*pi (360 degrees)
if angle < 0:
return 2*math.pi+angle, lenvector
# I return first the angle because that's the primary sorting criterium
# but if two vectors have the same angle then the shorter distance should come first.
return angle, lenvector
import pandas as pd
# Compute the center point
center = pts.mean(axis=0)
angle = []
for i in range(len(pts)):
ang, dist = clockwiseangle_and_distance(pts[i,:] - center, origin=[0,0], refvec=[1,0])
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 points
plt.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():
plt.gca().annotate('{:.0f}'.format(row['clockwise_order']), (row[0], row[1]),
ha='center', va='center_baseline', fontsize=6, color='k', fontweight='bold')
plt.gca().annotate('Center', center,
ha='center', va='center')
如果這種順時針順序不能滿足您的需求，請嘗試方法 2。
方法二：
要按順時針順序對給定幾何的點進行排序，使它們形成一個封閉的環(huán)，您可以執(zhí)行以下操作：
將數據集劃分為象限
選擇一個中心點，使象限的其余點位于以中心點為中心的圓弧上
按順時針角度對每個象限進行排序
按順時針順序放置每個象限
# Compute the center point
center = pts.mean(axis=0)
df = pd.DataFrame(pts)
# Group points into quadrants
df['quadrant'] = 0
df.loc[(df[0] > center[0]) & (df[1] > center[1]), 'quadrant'] = 0
df.loc[(df[0] > center[0]) & (df[1] < center[1]), 'quadrant'] = 1
df.loc[(df[0] < center[0]) & (df[1] < center[1]), 'quadrant'] = 2
df.loc[(df[0] < center[0]) & (df[1] > center[1]), 'quadrant'] = 3
quadrant = {}
for i in range(4):
quadrant[i] = df[df.quadrant == i]
# Intelligently choose the quadrant centers
x = 35
y = 5
subcenter = [[ x, y],
[ x, -y],
[-x, -y],
[-x, y]]
# Compute the angle between each quadrant and respective center point
angle = {}
points = {}
df_sub = {}
for j in range(len(quadrant)):
angle[j] = []
points[j] = quadrant[j][[0,1]]
for i in range(len(points[j])):
ang, dist = clockwiseangle_and_distance(points[j].values[i,:] - subcenter[j], origin=[0,0], refvec=[1,0])
angle[j].append(ang)
df_sub[j] = quadrant[j]
df_sub[j]['angle'] = np.degrees(angle[j])
df_sub[j] = df_sub[j].sort_values(by='angle')
# Combine the data frames
df = pd.concat(df_sub)
df['clockwise_order'] = np.arange(len(df))
# Plot the points by clockwise order
import matplotlib.pyplot as plt
# Create plot to show the ordering of the points
fig, 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():
plt.gca().annotate('{:.0f}'.format(row['clockwise_order']), (row[0], row[1]),
ha='center', va='center_baseline', fontsize=6, color='k', fontweight='bold')
plt.gca().annotate('Center', center,
ha='center', va='center')
for i in range(len(subcenter)):
plt.scatter(subcenter[i][0], subcenter[i][1], alpha=0.5, s=80, marker='s')
plt.gca().annotate('Quadrant \n'+str(i)+'\n', subcenter[i],
ha='center', va='center_baseline', color='k', fontsize=8)
# Plot with axis equally-spaced
df2 = 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')
如果這不能滿足您的需求，您可能必須手動訂購坐標。
添加回答
舉報
0/150
提交
取消