Учитывая список точек (x, y), создайте новый список точек, которые не находятся близко друг к другу

Question

Мне нужна помощь в этом, поскольку я новичок: учитывая список точек x, y

list=  [(788, 117), (788, 118), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330), (568, 338), (788, 117), (788, 118), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330), (568, 338), (418, 112), (418, 113), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330), (568, 338), (418, 112), (418, 113), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330), (568, 338), (418, 112)

Я хочу создать новый список с точками, которые не расположены близко друг к другу.Примеры (788, 117), (788, 118) близки друг к другу.

Эта функция, я считаю, поможет найти евклидово расстояние:

def dist(p, q):
    "Return the Euclidean distance between points p and q."
    return int(math.hypot(p[0] - q[0], p[1] - q[1]))

Заранее спасибо

Обновление:

это то, что я опробовал, и это не сработало так, как мне хотелось бы:

import math

list1 = [(788, 117), (788, 118), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330),
         (568, 338), (788, 117), (788, 118), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329),
         (397, 330), (568, 338), (418, 112), (418, 113), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284),
         (397, 329), (397, 330), (568, 338), (418, 112), (418, 113), (516, 164), (799, 171), (453, 225), (740, 284),
         (741, 284), (397, 329), (397, 330), (568, 338), (418, 112)]
list2 = []


def dist(p, q):
    "Return the Euclidean distance between points p and q."
    return int(math.hypot(p[0] - q[0], p[1] - q[1]))


while True:

    for i in list1:
        for j in list1:
            if i not in list2 and dist(i, j) <= 5:
                list2.append(i)

    print("list1 ", list1)
    print("list2 ", list2)

Результат: с большими списками, не содержащими повторяющихся точек, кажетсячтобы стать более сложной задачей

list1  [(788, 117), (788, 118), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330), (568, 338), (788, 117), (788, 118), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330), (568, 338), (418, 112), (418, 113), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330), (568, 338), (418, 112), (418, 113), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330), (568, 338), (418, 112)]
list2  [(788, 117), (788, 118), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330), (568, 338), (418, 112), (418, 113)]

Список постоянно обновляется, поэтому у меня есть цикл while Что я здесь не так делаю

Обновление:

points =  [(336, 14), (335, 15), (336, 15), (337, 15), (524, 15), (525, 15), (526, 15), (335, 16), (336, 16), (337, 16),
           (525, 16), (526, 16), (336, 17), (706, 19), (705, 20), (706, 20), (707, 20), (705, 21), (706, 21), (707, 21),
           (706, 22), (434, 66), (433, 67), (434, 67), (435, 67), (433, 68), (434, 68), (435, 68), (717, 73), (718, 73),
           (716, 74), (717, 74), (718, 74), (717, 75), (718, 75), (370, 127), (371, 127), (372, 127), (370, 128),
           (371, 128), (372, 128), (371, 129), (600, 129), (601, 129), (602, 129), (601, 130), (602, 130), (485, 140),
           (486, 140), (390, 174), (391, 174), (392, 174), (390, 175), (391, 175), (392, 175), (658, 186), (659, 186),
           (658, 187), (659, 187), (660, 187), (658, 188), (659, 188), (660, 188), (315, 231), (314, 232), (315, 232),
           (316, 232), (314, 233), (315, 233), (316, 233), (485, 240), (486, 240), (487, 240), (485, 241), (486, 241),
           (487, 241), (485, 242), (486, 242), (665, 250), (666, 250), (645, 339), (646, 339), (593, 384), (594, 384),
           (595, 384), (596, 384), (593, 385), (594, 385), (595, 385), (710, 386), (711, 386), (709, 387), (710, 387),
           (711, 387), (712, 387), (709, 388), (710, 388), (711, 388), (712, 388)]

Answer 1

Чтобы сделать это максимально эффективным, вы должны закорочить генерацию комбинации, используя набор точек, которые, как известно, исключаются при их прохождении.Вы также можете использовать квадрат расстояния в качестве критерия, чтобы избежать вычислений квадратного корня.

В вашем примере списка точек я заметил, что у вас много дубликатов.Это означает, что каждая повторяющаяся точка будет исключена, потому что она находится на нулевом расстоянии от другой точки.Обратите внимание, что это проблема как ваших данных, так и вашего алгоритма.Ваш алгоритм проверит расстояние между каждой точкой и самой собой (в результате чего ноль), поэтому все точки будут исключены, несмотря ни на чтоВаш второй цикл for должен соответствовать только точкам j , которые идут после точки i в списке, и должен исключать i и j * 1010.* если они находятся слишком близко друг к другу.

Предполагая, что ваше требование относится к отдельным точкам, которые не находятся близко друг к другу, вот пример того, как вы можете это сделать:

points =  [(788, 117), (788, 118), (516, 164), (799, 171), (453, 225), (740, 284), (741, 284), (397, 329), (397, 330), (568, 338)]
minimumDistance = 5

from itertools import combinations
tooClose = set()
minDistance2 = minimumDistance * minimumDistance
for point,otherPoint in combinations(list(set(points)),2):
    if point in tooClose and otherPoint in tooClose : continue
    dx,dy = (point[0]-otherPoint[0]), (point[1]-otherPoint[1])
    if (dx*dx+dy*dy) <= minDistance2:
        tooClose.add(point)
        tooClose.add(otherPoint)
result = [point for point in points if point not in tooClose]
print(result)

Answer 2

Вы можете использовать itertools.combinations, чтобы найти все возможные пары точек и составить список, чтобы исключить пары, которые находятся слишком близко.Например:

import itertools
min_distance = 1
my_list =  [(788, 117), (788, 118), (516, 164), (799, 171), ...]
print([pair for pair in itertools.combinations(my_list, 2) if dist(*pair) > min_distance])