0

我有一组点，我想从这些点创建线/道路网络。首先，我需要确定每个点的最近点。为此，我使用了 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"]

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

下面是结果的可视化： 代码的结果

我想要的： 我想要的

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

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]])

但这会返回错误

IndexError: list index out of range

谁能帮我这个？非常感谢！

4

2 回答 2

0

现在回答全球战略，这是我要做的（粗略的伪算法）：

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

您将获得一个线性图，以“以某种方式”使用最近的邻居连接所有点。不知道能不能满足你的需求。您还可以通过next_point随机获取线性图...

于 2018-11-20T18:21:33.477 回答
0

如果没有关于您想要获得的道路网络类​​型的更多详细信息，很难对您的全球战略发表评论。因此，让我评论您的特定代码并解释为什么会发生“超出范围”错误。我希望这会有所帮助。

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

于 2018-11-20T08:56:33.690 回答