如何从坐标列表coords_list中识别各链状区块的起止点？

我通过以下Python代码生成了随机数据集coords_list：

import matplotlib.pyplot as plt
import numpy as np

x = np.linspace(0, 10000, 100)
x = x.astype(int)

x1 = x[(x > 3000)]
y1 = x1 + 3000
points1 = list(zip(x1, y1))

x2 = x[((x > 3000) & (x < 5000)) | ((x > 6000) & (x < 8000))]
y2 = x2 + 2000
points2 = list(zip(x2, y2))

x3 = x[((x > 4000) & (x < 6000)) | ((x > 7000) & (x < 8000))]
y3 = x3 + 1000
points3 = list(zip(x3, y3))

x4 = x[(x > 2000) & (x < 7000)]
y4 = x4
points4 = list(zip(x4, y4))

coords_list = points1 + points2 + points3 + points4
coords_list = sorted(coords_list)

我希望仅借助coords_list的信息，编写函数找出每个链状区块的起止点。最初打算按x坐标排序读取所有坐标，将每个坐标按区块存入不同列表，再取列表首尾元素作为起止点，但动态关联同x坐标的多个坐标到对应区块的实现难度很大。后来意识到无需对所有坐标分类，仅需获取各链状区块的起止点，请问有合适的算法可以推荐吗？

核心思路：基于x分组的连续链追踪 #

因为coords_list已经按x排序，我们可以按x值分组，通过相邻x组的y值匹配追踪每条链的连续区间，最终提取起止点。具体步骤如下：

1. 按x坐标分组：把所有点按x值归类，得到每个x对应的y值集合（用字典x_to_ys，键为x，值为该x下所有y的列表）。
2. 追踪每条链的连续区间：
   • 初始化active_chains字典，键为当前链的末尾y值，值为链的起始x。
   • 按x从小到大遍历每个分组：
     • 对当前x的每个y值，检查上一个x分组中是否存在y-1（因为你的链是y = x + k形式，相邻x的y差固定为1）。
     • 若匹配到，说明是已有链的延续：移除旧末尾y，将当前y作为新键存入active_chains，保留原起始x。
     • 若没匹配到，说明是新链开始：将当前y作为键，当前x作为起始x存入active_chains。
     • 清理active_chains中未延续的链：这些链已结束，记录其起止点（起始x对应的起始y、上一个x对应的末尾y）。
3. 处理剩余活跃链：遍历结束后，记录active_chains中剩余链的起止点。

代码实现示例 #

def find_chain_endpoints(coords_list):
    # 按x分组，整理每个x对应的y列表
    x_to_ys = {}
    for x, y in coords_list:
        if x not in x_to_ys:
            x_to_ys[x] = []
        x_to_ys[x].append(y)
    # 按x排序
    sorted_xs = sorted(x_to_ys.keys())
    
    active_chains = {}  # key: 当前链的末尾y, value: 链的起始x
    endpoints = []
    
    for i in range(len(sorted_xs)):
        current_x = sorted_xs[i]
        current_ys = x_to_ys[current_x]
        prev_x = sorted_xs[i-1] if i > 0 else None
        prev_ys = x_to_ys.get(prev_x, []) if prev_x else []
        
        new_active = {}
        # 处理链的延续或新链启动
        for y in current_ys:
            # 检查是否延续上一个活跃链
            if (y - 1) in active_chains:
                start_x = active_chains.pop(y - 1)
                new_active[y] = start_x
            elif (y - 1) in prev_ys:
                # 从相邻x的点启动新链
                new_active[y] = current_x
            else:
                # 全新链启动
                new_active[y] = current_x
        
        # 记录已中断的链的起止点
        for end_y, start_x in active_chains.items():
            start_y = start_x + (end_y - prev_x)
            endpoints.append( ((start_x, start_y), (prev_x, end_y)) )
        
        active_chains = new_active
    
    # 记录最后剩余的活跃链的起止点
    for end_y, start_x in active_chains.items():
        start_y = start_x + (end_y - start_x)
        endpoints.append( ((start_x, start_y), (current_x, end_y)) )
    
    return endpoints

算法优势 #

• 无需全量分类存储点，仅追踪活跃链状态，内存占用低。
• 基于已排序的x序列，遍历一次即可完成提取，时间复杂度为O(N)（N为点的数量）。
• 针对你生成的线性链特性，匹配逻辑简单高效，无需复杂计算。

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