如何将任意顺序的3D点集匹配到DataFrame中的对应区间集？

我有一个包含3D空间点区间的DataFrame，结构如下：

Point1_X_INTVL | Point1_Y_INTVL | Point1_Z_INTVL | Point2_X_INTVL | Point2_Y_INTVL | Point2_Z_INTVL | ...
   (0.0 - 0.5) |    (0.0 - 0.5) |    (0.0 - 0.5) |    (1.0 - 1.5) |    (1.0 - 1.5) |    (1.0 - 1.5) | ...

每个条目包含多组3D坐标区间，每组对应一个点的允许误差范围。

现在需要用一组3D点（比如[(1.022, 1.222, 1.223), (0.012, 0.111, 0.222)]）匹配DataFrame中的条目，需满足以下规则：

• 点和区间组可任意顺序匹配，比如示例中第一个点匹配DataFrame第二组区间、第二个点匹配第一组区间，就算匹配成功。
• 同一个点不能重复匹配同一组区间，比如[(1.022, 1.222, 1.223), (1.022, 1.222, 1.223)]不能匹配包含两组不同区间的条目。
• 只有当所有点都找到对应区间组，且所有区间组都被匹配（点数量与条目内区间组数量完全一致）时，才算条目匹配成功。
• 实际场景中点的数量约十几个，DataFrame条目内的区间组数量可能与查询点数量不同，仅当数量一致且满足上述规则时才返回匹配条目。

第一步：数据重构 #

先把原DataFrame的区间数据拆分为易处理的结构，每个条目存储为区间组列表，每个区间组包含X/Y/Z的上下限元组。比如原DataFrame第一行可转换为：

[((0.0,0.5), (0.0,0.5), (0.0,0.5)), ((1.0,1.5), (1.0,1.5), (1.0,1.5))]

第二步：匹配逻辑实现 #

核心思路：先检查条目内区间组数量与查询点数量是否一致，不一致直接跳过；一致则验证是否存在点的排列，使得每个点都落在对应区间组内。

代码示例（Python）

import pandas as pd
from itertools import permutations

# 解析区间字符串为(min, max)元组
def parse_interval(interval_str):
    num_str = interval_str.strip('()').split(' - ')
    return (float(num_str[0]), float(num_str[1]))

# 构造示例DataFrame
df = pd.DataFrame({
    'Point1_X_INTVL': ['(0.0 - 0.5)'],
    'Point1_Y_INTVL': ['(0.0 - 0.5)'],
    'Point1_Z_INTVL': ['(0.0 - 0.5)'],
    'Point2_X_INTVL': ['(1.0 - 1.5)'],
    'Point2_Y_INTVL': ['(1.0 - 1.5)'],
    'Point2_Z_INTVL': ['(1.0 - 1.5)']
})

# 将DataFrame行转换为区间组列表
def row_to_interval_groups(row):
    interval_groups = []
    point_count = len([col for col in row.index if col.startswith('Point')]) // 3
    for i in range(1, point_count+1):
        x_int = parse_interval(row[f'Point{i}_X_INTVL'])
        y_int = parse_interval(row[f'Point{i}_Y_INTVL'])
        z_int = parse_interval(row[f'Point{i}_Z_INTVL'])
        interval_groups.append((x_int, y_int, z_int))
    return interval_groups

df['interval_groups'] = df.apply(row_to_interval_groups, axis=1)

# 判断单个点是否在区间组内
def point_in_interval(point, interval_group):
    x, y, z = point
    (x_min, x_max), (y_min, y_max), (z_min, z_max) = interval_group
    return (x_min <= x <= x_max) and (y_min <= y <= y_max) and (z_min <= z <= z_max)

# 判断条目是否匹配查询点集
def match_entry(entry_intervals, query_points):
    if len(entry_intervals) != len(query_points):
        return False
    # 遍历点的所有排列，检查是否存在完美匹配
    for point_perm in permutations(query_points):
        all_match = True
        for p, interval in zip(point_perm, entry_intervals):
            if not point_in_interval(p, interval):
                all_match = False
                break
        if all_match:
            return True
    return False

# 执行匹配
query_points = [(1.022, 1.222, 1.223), (0.012, 0.111, 0.222)]
matched_entries = df[df['interval_groups'].apply(lambda x: match_entry(x, query_points))]
print(matched_entries)

性能优化提示 #

当点数量较多（如十几个）时，全排列的计算量会指数级增长，此时可改用二分图完美匹配算法（如匈牙利算法），无需生成所有排列即可快速判断是否存在有效匹配，大幅提升性能。也可提前计算区间组中心点，通过距离过滤不可能匹配的条目，减少后续计算量。

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