如何在Python中判断旋转/坐标顺序变化的两个2D几何图形是否相同

问题背景 #

需要判断两个2D几何图形是否本质相同，已知其中一个图形经过旋转，且两者的节点输入顺序存在打乱（包括循环移位、方向反转）。原有的三个判断条件（节点数相同、连续节点距离相同、首节点到各节点距离相同）无法得到正确结果，需寻求Python实现的正确方法。

坐标数据 #

# 第一个几何图形坐标
X1 = [0.0, 0.87, 1.37, 1.87, 2.73, 3.6, 4.46, 4.96, 5.46, 4.6, 3.73, 2.87, 2.0, 1.5, 1.0, 0.5, 2.37, 3.23, 4.1]
Y1 = [0.0, 0.5, -0.37, -1.23, -0.73, -0.23, 0.27, -0.6, -1.46, -1.96, -2.46, -2.96, -3.46, -2.6, -1.73, -0.87, -2.1, -1.6, -1.1]

# 第二个几何图形坐标
X2 = [2, 4, 4, 2, 3, 2, 4, 3, 1, 3, 4, 3, 1, 2, 0, 3, 4, 2, 0]
Y2 = [3, 4, 2, 1, 3, 2, 1, 0, 0, 2, 3, 4, 1, 4, 0, 1, 0, 0, 1]

原尝试方法及问题 #

原方法通过三个条件判断，但因未处理旋转、节点循环移位/反转的情况，导致结果不准确：

条件1：节点数相同 #

#---------------------------CONDITION: 1------------------------------------------------#
# Condition: Number of nodes in both geometries should be same
node_number1 = df_1['node_number'].tolist()                        # converting 'node number' column from first dataframe to a list 
node_number2 = df_2['node_number'].tolist()                        # converting 'X_coordinate' column from second dataframe to a list

条件2：连续节点间的距离相同 #

#---------------------------CONDITION: 2------------------------------------------------#
# Condition: Distance between two successive nodes must be 1.
x_shift1 = df_1['New_X_coordinate_reformed'].shift(-1)                          # In first dataframe shift the index by (-1) from X_coordinate values
y_shift1 = df_1['New_Y_coordinate_reformed'].shift(-1)                          # In first dataframe shift the index by (-1) from Y_coordinate values

# Finding a distance between two coordinates (nodes)
# General formula for this: square root of [(x2 - x1)^2 - (y2 - y1)^2]
nodal_dist_df_1 = np.sqrt((x_shift1 - df_1['New_X_coordinate_reformed'])**2 + (y_shift1 - df_1['New_Y_coordinate_reformed'])**2).dropna().to_list()
nodal_dist_df_1 = [round(num,2) for num in nodal_dist_df_1]       # rounding a obtained values in 'nodal_dist_df1' by 2 decimals 
  
x_shift2 = df_2['New_X_coordinate_reformed'].shift(-1)                          # In second dataframe shift the index by (-1) from X_coordinate values
y_shift2 = df_2['New_Y_coordinate_reformed'].shift(-1)                          # In second dataframe shift the index by (-1) from Y_coordinate values

# Finding a distance between two coordinates (nodes)
# General formula for this: square root of [(x2 - x1)^2 - (y2 - y1)^2]
nodal_dist_df_2 = np.sqrt((x_shift2 - df_2['New_X_coordinate_reformed'])**2 + (y_shift2 - df_2['New_Y_coordinate_reformed'])**2).dropna().to_list()
nodal_dist_df_2 = [round(num,2) for num in nodal_dist_df_2]       # rounding a obtained values in 'nodal_dist_df1' by 2 decimals 

条件3：首节点到所有其他节点的距离相同 #

#---------------------------CONDITION: 3------------------------------------------------#
# Condition: Distances between first node to each node should be same in both geometries.

i=0
dist_from_N1_1 = []                                                # For first dataframe initializng a blank list
for i in range(len(df_1['New_X_coordinate_reformed'])-1): 
    
    # Finding a distance between two coordinates (nodes) in first dataframe
    # General formula for this: square root of [(x2 - x1)^2 - (y2 - y1)^2] where x1 and y1 will be constant and second coordinate will vary from x2 to x15
    d = np.sqrt((df_1['New_X_coordinate_reformed'][i+1]-df_1['New_X_coordinate_reformed'][0])**2 + (df_1['New_Y_coordinate_reformed'][i+1]-df_1['New_Y_coordinate_reformed'][0])**2)
    dist_from_N1_1.append(d)                                       # appending a distance value in a list initialized before 'for' loop
    i = i+1
dist_from_N1_1 = [round(num,2) for num in dist_from_N1_1]       # rounding a obtained values in 'nodal_dist_df1' by 2 decimals 

i=0
dist_from_N1_2 = []                                                # For second dataframe initializng a blank list
for i in range(len(df_2['New_X_coordinate_reformed'])-1):
    
    # Finding a distance between two coordinates (nodes) in second dataframe
    # General formula for this: square root of [(x2 - x1)^2 - (y2 - y1)^2] where x1 and y1 will be constant and second coordinate will vary from x2 to x15
    d_N2 = np.sqrt((df_2['New_X_coordinate_reformed'][i+1]-df_2['New_X_coordinate_reformed'][0])**2 + (df_2['New_Y_coordinate_reformed'][i+1]-df_2['New_Y_coordinate_reformed'][0])**2)
    dist_from_N1_2.append(d_N2)
    i = i+1
dist_from_N1_2 = [round(num,2) for num in dist_from_N1_2]       # rounding a obtained values in 'nodal_dist_df1' by 2 decimals 

原判断逻辑 #

#---------------------------Checking of all three condition-----------------------------#
if (len(node_number2) == len(node_number1) and (nodal_dist_df_1 == nodal_dist_df_2) and dist_from_N1_1 == dist_from_N1_2):
    print('All three conditions are satisfied.')
    print('Hence Yes, two geometries are same.')
else:
    print('No, two geometries are not same.')

正确实现思路及代码 #

核心思路是通过归一化消除平移、旋转的影响，再处理节点序列的循环移位和反转问题，最后进行匹配：

1. 平移归一化：将图形的重心移至坐标原点，消除位置差异。
2. 旋转归一化：使用主成分分析（PCA）找到图形的主方向，将图形旋转至主方向与X轴对齐，消除旋转差异。
3. 序列匹配：生成其中一个图形的所有可能循环移位和反转后的序列，与另一个归一化后的序列进行匹配，允许浮点误差。

完整Python代码 #

import numpy as np
from sklearn.decomposition import PCA

def normalize_geometry(x, y):
    """将几何图形归一化：平移到重心原点，旋转到主方向对齐X轴"""
    # 转换为numpy数组
    points = np.array(list(zip(x, y)))
    
    # 平移归一化：重心移到原点
    centroid = np.mean(points, axis=0)
    points_centered = points - centroid
    
    # 旋转归一化：用PCA找主方向，旋转到X轴
    pca = PCA(n_components=2)
    pca.fit(points_centered)
    # 获取主成分方向向量
    main_dir = pca.components_[0]
    # 计算旋转角度：主方向与X轴的夹角
    angle = np.arctan2(main_dir[1], main_dir[0])
    # 旋转矩阵：将主方向转到X轴
    rotation_matrix = np.array([
        [np.cos(-angle), -np.sin(-angle)],
        [np.sin(-angle), np.cos(-angle)]
    ])
    points_normalized = points_centered @ rotation_matrix
    
    return points_normalized

def generate_all_sequences(points):
    """生成所有可能的循环移位和反转序列"""
    n = len(points)
    sequences = []
    # 生成所有循环移位
    for i in range(n):
        shifted = np.roll(points, i, axis=0)
        sequences.append(shifted)
        # 生成反转后的循环移位
        reversed_shifted = np.roll(np.flip(points, axis=0), i, axis=0)
        sequences.append(reversed_shifted)
    return sequences

def are_geometries_equal(x1, y1, x2, y2, tolerance=1e-2):
    # 检查节点数是否相同
    if len(x1) != len(x2):
        return False
    
    # 归一化两个图形
    norm1 = normalize_geometry(x1, y1)
    norm2 = normalize_geometry(x2, y2)
    
    # 生成norm1的所有可能序列
    all_seq1 = generate_all_sequences(norm1)
    
    # 检查是否有序列与norm2匹配
    for seq in all_seq1:
        # 计算所有点的距离平方和，判断是否在容差内
        diff = np.sum((seq - norm2)**2)
        if diff < tolerance * len(seq):
            return True
    return False

# 测试
X1 = [0.0, 0.87, 1.37, 1.87, 2.73, 3.6, 4.46, 4.96, 5.46, 4.6, 3.73, 2.87, 2.0, 1.5, 1.0, 0.5, 2.37, 3.23, 4.1]
Y1 = [0.0, 0.5, -0.37, -1.23, -0.73, -0.23, 0.27, -0.6, -1.46, -1.96, -2.46, -2.96, -3.46, -2.6, -1.73, -0.87, -2.1, -1.6, -1.1]
X2 = [2, 4, 4, 2, 3, 2, 4, 3, 1, 3, 4, 3, 1, 2, 0, 3, 4, 2, 0]
Y2 = [3, 4, 2, 1, 3, 2, 1, 0, 0, 2, 3, 4, 1, 4, 0, 1, 0, 0, 1]

if are_geometries_equal(X1, Y1, X2, Y2):
    print("两个几何图形本质相同")
else:
    print("两个几何图形不相同")

代码说明 #

• normalize_geometry：完成平移和旋转归一化，确保两个相同的图形在归一化后处于同一坐标系。
• generate_all_sequences：生成所有可能的节点循环移位和反转序列，覆盖节点顺序打乱的所有情况。
• are_geometries_equal：先检查节点数，再归一化，最后遍历所有可能序列进行匹配，通过容差处理浮点精度问题。

内容的提问来源于stack exchange，提问作者Urvesh