如何获取三维点列表中直线段的端点索引？

问题描述 #

给定三维空间点的列表，需要找出其中连续构成直线段的两个端点索引。输入特点为：遍历列表时仅单个坐标轴的数值发生变化，直线段由同一坐标轴上连续变化的点组成，当变化的坐标轴切换时，代表前一段直线结束、新的直线段开始。

测试用例1：

三维点列表：

[45,45,45]
[45,45,42]
[45,45,39]
[45,42,39]
[45,39,39]
[45,36,39]
[45,33,39]

预期输出：(0,2),(3,6)
原因：索引0-2的点仅z轴变化，构成直线段；索引3-6的点仅y轴变化，构成直线段。

测试用例2：

三维点列表：

[30,24,42]
[30,21,42]
[27,21,42]
[27,21,45]
[27,21,48]
[27,21,51]

预期输出：(0,1),(2,5)

解决方案思路 #

利用输入仅单轴变化的特性，通过遍历点序列跟踪当前直线段的变化轴，当变化轴切换时，记录前一段的首尾索引，具体步骤：

1. 初始化直线段的起始索引为0。
2. 从第二个点开始，对比当前点与前一个点，确定当前的变化坐标轴（x/y/z对应索引0/1/2）。
3. 持续跟踪当前线段的变化轴，若遇到下一个点的变化轴与当前不一致，则标记当前线段结束，记录(起始索引, 当前前一个点的索引)，并更新起始索引为当前点。
4. 遍历结束后，处理最后一段未记录的直线段。

代码实现（Python） #

def find_line_segment_endpoints(points):
    if len(points) < 2:
        return []
    
    segments = []
    start_idx = 0
    # 获取第一段的变化轴
    prev_point = points[0]
    curr_point = points[1]
    change_axis = None
    for i in range(3):
        if prev_point[i] != curr_point[i]:
            change_axis = i
            break
    
    # 从第三个点开始遍历
    for idx in range(2, len(points)):
        prev_p = points[idx-1]
        curr_p = points[idx]
        # 找当前点对的变化轴
        curr_change_axis = None
        for i in range(3):
            if prev_p[i] != curr_p[i]:
                curr_change_axis = i
                break
        # 如果变化轴不同，说明前一段结束
        if curr_change_axis != change_axis:
            segments.append((start_idx, idx-1))
            start_idx = idx
            change_axis = curr_change_axis
    
    # 处理最后一段
    segments.append((start_idx, len(points)-1))
    
    # 格式化为要求的字符串输出
    return ','.join([f'({s},{e})' for s,e in segments])

# 测试用例1
test1_points = [
    [45,45,45],
    [45,45,42],
    [45,45,39],
    [45,42,39],
    [45,39,39],
    [45,36,39],
    [45,33,39]
]
print(find_line_segment_endpoints(test1_points))  # 输出：(0,2),(3,6)

# 测试用例2
test2_points = [
    [30,24,42],
    [30,21,42],
    [27,21,42],
    [27,21,45],
    [27,21,48],
    [27,21,51]
]
print(find_line_segment_endpoints(test2_points))  # 输出：(0,1),(2,5)

代码说明 #

• 首先处理边界情况：点列表长度不足2时直接返回空。
• 第一段直线的变化轴通过前两个点对比确定。
• 遍历过程中，每次对比当前点与前一个点的变化轴，若与当前线段的变化轴不同，则分割线段。
• 遍历结束后必须补充记录最后一段线段，避免遗漏。
• 最终将结果格式化为要求的字符串形式。

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