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

Question

这看起来像是一个重复的问题，但我尝试了已经存在的解决方案，但到目前为止似乎没有一个对我有用。.这个解决方案给出了一个提示，但它只适用于常规几何。我有一个相当复杂的几何图形，我从中提取了未排序的边界点。下面是我从几何图形中提取的几何图形和边界顶点的图片。在边界顶点数据中，我们可以看到点是无序的。有没有办法可以顺时针/逆时针排列点，以便这些点在连续连接时形成闭合环？我的目标是创建一个多边形或线性环，如here所述，然后查找任意欧几里得点是否位于多边形/环内

Answer 1

方法一：

定义一个中心点，计算每个坐标和中心点之间的角度，然后按角度排序：

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。

方法二：

要按顺时针顺序对给定几何的点进行排序，使它们形成一个封闭的环，您可以执行以下操作：

将数据集划分为象限

选择一个中心点，使象限的其余点位于以中心点为中心的圆弧上

按顺时针角度对每个象限进行排序

按顺时针顺序放置每个象限

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

如果这不能满足您的需求，您可能必须手动订购坐标。