Создать линейную сеть из ближайших точек с границами - PullRequest
Новая
       6

Создать линейную сеть из ближайших точек с границами

0 голосов
/ 20 ноября 2018

У меня есть набор точек, и я хочу создать линию / сеть дорог из этих точек. Во-первых, мне нужно определить ближайшую точку из каждой из точек. Для этого я использовал KD Tree и разработал такой код: 

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

Может кто-нибудь помочь мне с этим? Большое спасибо!

Ответы [ 2 ]

0 голосов
/ 20 ноября 2018

Отвечая теперь о глобальной стратегии, вот что я бы сделал (грубый псевдоалгоритм): 

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 в случайном порядке ...

0 голосов
/ 20 ноября 2018

Трудно прокомментировать вашу глобальную стратегию без дополнительной информации о том, какую сеть дорог вы хотите получить. Итак, позвольте мне прокомментировать ваш конкретный код и объяснить, почему происходит ошибка «вне диапазона». Я надеюсь, что это может помочь.

Во-первых, знаете ли вы, что (list_a и list_b) вернет list_a, если он пуст, иначе list_b? Во-вторых, разве условие (vq в списке (df ["координирует]]) не всегда истинно? Если да, то ваш цикл while просто всегда выполняет оператор else, и на последней итерации цикла for (count- 1) будет больше, чем общее количество (уникальных) точек. Следовательно, ваш запрос KDTree не возвращает достаточно точек, и clstu [count-1] находится вне диапазона.

...