удаление элементов из списка, которые похожи - PullRequest
Новая
       8

удаление элементов из списка, которые похожи

0 голосов
/ 18 октября 2018

Начиная со списка кортежей, которые содержат координаты x и y точек на графике;Я хотел бы удалить дубликаты точек в списке;однако для моих целей баллы, которые находятся на расстоянии до 10, я считаю дубликатами.

Я написал функцию, которая, кажется, выполняет эту работу, но я держу пари, что есть лучший способ.В приведенных ниже примерах данных: точки 1, 2 и 5 являются дубликатами (на расстоянии 10 друг от друга).Мне все равно, какой из этих трех пунктов пережить процесс исключения.Я ожидаю, что обработаю не более 100 баллов, причем около 50% из них будут устранены.Спасибо! 

def is_close(pointA, pointB, closeness):
    x1, y1  = pointA
    x2, y2 = pointB
    distance = int(((x2-x1)**2 + (y2-y1)**2)**0.5) # distance formula
    if distance < closeness:
        return True
    return False

def remove_close_duplicated(data, closeness):
    if len(data) < 2: # can't have duplicates if there aren't at least 2 points
        return data
    new_list_points = []
    for i, point in enumerate(data):
        if i == 0:
            new_list_points.append(point)
            continue
        close = False
        for new_point in new_list_points:
            if is_close(new_point, point, closeness):
                close = True
                break 
        if close == False:
            new_list_points.append(point)
    return new_list_points

sample_data =[
    (600, 400), # 1
    (601, 401), # 2
    (725, 300), # 3
    (800, 900), # 4
    (601, 400), # 5
]

closeness = 10                  
print(remove_close_duplicated(sample_data, closeness))
'''
output is:
[(600, 400), (725, 300), (800, 900)]
'''

1 Ответ

0 голосов
/ 19 октября 2018

Это две части: нахождение близких пар и нахождение хорошо разделенных множеств (классы эквивалентности транзитивного замыкания отношения ближнего соседа или связанные компоненты графа ближнего соседа).

Только в 100 точках вы можете позволить себе выполнить первую часть методом грубой силы, но эффективный выбор включает группирование в ячейки 10 на одной стороне, так что все ближайшие соседи точки должны находиться в ее ячейке или рядомодин, или сохранение точек в чем-то вроде k - d дерева.

Для второй части, одно стандартное решение состоит в создании леса с непересекающимися множествами,применение операции объединения между каждой соседней парой (произвольный выбор точки для сохранения в (новом) корне).Точки, связанные с корнями в конце, являются желаемым уменьшенным набором.

...