如何在坐标列表中找到起点和终点？

Question

我正在寻求算法方面的帮助。

我按照以下过程创建了一个随机数据集“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坐标的多个坐标动态链接到每个块（链）是非常困难的。

查看图 2 的顶部，我试图将重复的 x 坐标的坐标放入每个列表中，然后将它们动态连接回每个块（链），但这种行为很难实现。

我希望通过此行为实现的结果如图 2 的下半部分所示。

但是，当我重新思考这个问题时，我发现我不需要这些坐标的所有分类，我只需要每个块（链）的起点和终点的坐标（如图问题设计所示） 1).

所以，我想知道您是否可以向我推荐任何算法？

Answer 1

我使用DFS解决这个问题

这是我的代码。

def dfsChaining(coords_list, visited, start_idx):
chain = []
stack = [start_idx] 
visited[start_idx] = True

while stack:
    current_idx = stack.pop()
    chain.append(coords_list[current_idx])
    
    for neighbor_idx, neighbor in enumerate(coords_list):
        if not visited[neighbor_idx] : 
            if isNeighbor(coords_list[current_idx], neighbor): 
                stack.append(neighbor_idx)
                visited[neighbor_idx] = True

return chain

def isNeighbor(coord1, coord2): 
condition = abs(coord1[0] - coord2[0]) <= 103 and abs(coord1[1] - coord2[1]) <= 103
return condition

visited = [False] * len(coords_list)
chains = []

for i in range(len(coords_list)):
if not visited[i]: # if visited[i] is False
    chain = dfsChaining(coords_list, visited, i)
    chains.append(chain)

chain_start_end_coords = [(chain[0], chain[-1]) for chain in chains]

for i, (start, end) in enumerate(chain_start_end_coords):
print(f"Chain {i + 1}: Start {start}, End {end}")