从具有边界的最近点创建线网络

Question

我有一组点，我想从这些点创建线/路网。首先，我需要确定每个点的最近点。为此，我使用了 KD 树并开发了如下代码：

def closestPoint(source, X = None, Y = None):

df = pd.DataFrame(source).copy(deep = True) #Ensure source is a dataframe, working on a copy to keep the datasource

if(X is None and Y is None):
    raise ValueError ("Please specify coordinate")
elif(not X in df.keys() and not Y in df.keys()):
    raise ValueError ("X and/or Y is/are not in column names")
else:
    df["coord"] = tuple(zip(df[X],df[Y])) #create a coordinate

if (df["coord"].duplicated):
    uniq = df.drop_duplicates("coord")["coord"]
    uniqval = list(uniq.get_values())
    dupl = df[df["coord"].duplicated()]["coord"]
    duplval = list(dupl.get_values())

    for kq,vq in uniq.items():
        clstu = spatial.KDTree(uniqval).query(vq, k = 3)[1]
        df.at[kq,"coord"] = [vq,uniqval[clstu[1]]]
        if([uniqval[clstu[1]],vq] in list(df["coord"]) ):
            df.at[kq,"coord"] = [vq,uniqval[clstu[2]]]

    for kd,vd in dupl.items():
        clstd = spatial.KDTree(duplval).query(vd,k = 1)[1]
        df.at[kd,"coord"] = [vd,duplval[clstd]]
else:
    val = df["coord"].get_values()
    for k,v in df["coord"].items():
        clst = spatial.KDTree(val).query(vd, k = 3)[1]
        df.at[k,"coord"] = [v,val[clst[1]]]
        if([val[clst[1]],v] in list (df["coord"])):
            df.at[k,"coord"] = [v,val[clst[2]]]

return df["coord"]

代码可以return周围最近的点。但是，我需要确保没有创建双线（例如（x，y）到（x1，y1）和（x1，y1）到（x，y））并且我还需要确保每个点只能是用作线的起点和线的终点，尽管该点距离其他点最近。

下面是结果的可视化： Result of the code

我想要的： What I want

我也尝试过将原点和目标坐标分开并这样做：

df["coord"] = tuple(zip(df[X],df[Y])) #create a coordinate
df["target"] = "" #create a column for target points

count = 2 # create a count iteration
if (df["coord"].duplicated):
  uniq = df.drop_duplicates("coord")["coord"]
  uniqval = list(uniq.get_values())
  for kq,vq in uniq.items():
    clstu = spatial.KDTree(uniqval).query(vq, k = count)[1]
    while not vq in (list(df["target"]) and list(df["coord"])):
        clstu = spatial.KDTree(uniqval).query(vq, k = count)[1]
        df.set_value(kq, "target", uniqval[clstu[count-1]])
    else:
        count += 1
        clstu = spatial.KDTree(uniqval).query(vq, k = count)[1]
        df.set_value(kq, "target", uniqval[clstu[count-1]])

但这return是一个错误

IndexError: list index out of range

谁能帮我解决这个问题？非常感谢！

Answer 1

如果不进一步详细说明您想要获得的道路网络类型，就很难对您的全球战略发表评论。因此，让我只评论您的特定代码并解释 "out of range" 错误发生的原因。希望对您有所帮助。

首先，您是否知道 (list_a 和 list_b) 如果为空则 return list_a，否则 list_b？其次，条件 (vq in list(df["coord"]) 不总是 True 吗？如果是，那么你的 while 循环总是执行 else 语句，并且在 for 循环的最后一次迭代中，( count-1) 将大于（唯一）点的总数。因此您的 KDTree 查询没有 return 足够的点并且 clstu[count-1] 超出范围。

Answer 2

现在回答关于全局策略的问题，这是我会做的（粗略的伪算法）：

current_point = one starting point in uniqval
while (uniqval not empty)
  construct KDTree from uniqval and use it for next line
  next_point = point in uniqval closest to current_point
  record next_point as target for current_point
  remove current_point from uniqval
  current_point = next_point

您将获得一个线性图，使用最近的邻居 "in some way" 连接所有点。不知道能不能满足你的需求。您还可以通过随机取 next_point 来获得线性图...

从具有边界的最近点创建线网络

Create line network from closest points with boundaries

kdtree

while-loop

closest-points