查找另一点距离内所有点的算法

Question

我在一份工作的入职测试中遇到了这个问题。我没有通过测试。为了尊重公司，我掩饰了这个问题。

假设您有 N 个人在 A X B 空间的公园中。如果一个人在50英尺内没有其他人，他就享有自己的隐私。否则，侵犯了他的个人空间。给定一组 (x, y)，有多少人的空间会被侵犯？

例如，用 Python 给出这个列表:

人 = [(0,0), (1,1), (1000, 1000)]

我们会发现 2 个人的空间受到侵犯:1、2。

我们不需要找到所有的人；只是唯一身份的总数。

你不能用暴力的方法来解决问题。换句话说，您不能在数组中使用简单数组。

几周来我一直在断断续续地研究这个问题，虽然我得到的解决方案比 n^2 快，但还没有提出可扩展的问题。

我认为解决这个问题的唯一正确方法是使用 Fortune 的算法？

这是我在 Python 中的内容(未使用 Fortune 的算法):

import math
import random
random.seed(1)  # Setting random number generator seed for repeatability
TEST = True

NUM_PEOPLE = 10000
PARK_SIZE = 128000  # Meters.
CONFLICT_RADIUS = 500  # Meters.

def _get_distance(x1, y1, x2, y2):
    """
    require: x1, y1, x2, y2: all integers
    return: a distance as a float
    """
    distance = math.sqrt(math.pow((x1 - x2), 2) + math.pow((y1 - y2),2))
    return distance

def check_real_distance(people1, people2, conflict_radius):
    """
    determine if two people are too close

    """
    if people2[1] - people1[1] > conflict_radius:
        return False
    d = _get_distance(people1[0], people1[1], people2[0], people2[1])
    if d >= conflict_radius:
        return False
    return True

def check_for_conflicts(peoples, conflict_radius):
    # sort  people
    def sort_func1(the_tuple):
        return the_tuple[0]
    _peoples = []
    index = 0
    for people in peoples:
        _peoples.append((people[0], people[1], index))
        index += 1
    peoples = _peoples
    peoples = sorted(peoples, key = sort_func1)
    conflicts_dict = {}
    i = 0
    # use a type of sweep strategy
    while i < len(peoples) - 1:
        x_len = peoples[i + 1][0] - peoples[i][0]
        conflict = False
        conflicts_list =[peoples[i]]
        j = i + 1
        while x_len <= conflict_radius and j < len(peoples):
            x_len = peoples[j][0] - peoples[i][0]
            conflict = check_real_distance(peoples[i], peoples[j], conflict_radius)
            if conflict:
                people1 = peoples[i][2]
                people2 = peoples[j][2]
                conflicts_dict[people1] = True
                conflicts_dict[people2] = True
            j += 1
        i += 1
    return len(conflicts_dict.keys())

def gen_coord():
    return int(random.random() * PARK_SIZE)

if __name__ == '__main__':
    people_positions = [[gen_coord(), gen_coord()] for i in range(NUM_PEOPLE)]
    conflicts = check_for_conflicts(people_positions, CONFLICT_RADIUS)
    print("people in conflict: {}".format(conflicts))

Answer 1

从评论中可以看出，有很多方法可以解决这个问题。在面试情况下，您可能希望尽可能多地列出并说明每个人的优点和缺点。

对于上述问题，如果半径固定，最简单的方法可能是 rounding and hashing . k-d 树等是功能强大的数据结构，但它们也相当复杂，如果您不需要重复查询它们或添加和删除对象，它们可能会过大。与 n log n 的空间树相比，哈希可以实现线性时间，尽管它可能取决于点的分布。

要理解散列和舍入，只需将其视为将您的空间划分为边长等于您要检查的半径的正方形网格。每个方 block 都有自己的“邮政编码”，您可以将其用作散列键来存储该方 block 中的值。您可以通过将 x 和 y 坐标除以半径并向下舍入来计算一个点的邮政编码，如下所示:

def get_zip_code(x, y, radius):
    return str(int(math.floor(x/radius))) + "_" + str(int(math.floor(y/radius)))

我使用字符串是因为它很简单，但您可以使用任何东西，只要您为每个方 block 生成唯一的邮政编码即可。

创建一个字典，其中键是邮政编码，值是该邮政编码中所有人的列表。要检查冲突，一次添加一个人，在添加每个人之前，测试与同一邮政编码中的所有人以及该邮政编码的 8 个邻居的冲突。我重复使用了您的方法来跟踪冲突:

def check_for_conflicts(peoples, conflict_radius):

    index = 0
    d = {}
    conflicts_dict = {}
    for person in peoples:  

        # check for conflicts with people in this person's zip code
        # and neighbouring zip codes:
        for offset_x in range(-1, 2):
            for offset_y in range(-1, 2):
                 offset_zip_code = get_zip_code(person[0] + (offset_x * conflict_radius), person[1] + (offset_y * conflict_radius), conflict_radius)

                 if offset_zip_code in d:
                     # get a list of people in this zip:
                     other_people = d[offset_zip_code]
                     # check for conflicts with each of them:
                     for other_person in other_people:
                         conflict = check_real_distance(person, other_person, conflict_radius)
                         if conflict:
                             people1 = index
                             people2 = other_person[2]
                             conflicts_dict[people1] = True
                             conflicts_dict[people2] = True

        # add the new person to their zip code
        zip_code = get_zip_code(person[0], person[1], conflict_radius)
        if not zip_code in d:
            d[zip_code] = []
        d[zip_code].append([person[0], person[1], index])
        index += 1

    return len(conflicts_dict.keys())

这个的时间复杂度取决于几件事。如果你增加人数，但不增加你分配他们的空间的大小，那么它将是 O(N²) 因为冲突的数量将以二次方增加你必须把它们都数一遍。但是，如果随着人数的增加而增加空间，使密度相同，则更接近O(N)。

如果您只计算独特的人数，您可以计算每个邮政编码中有多少人至少有 1 个冲突。如果它等于邮政编码中的每个人，那么在与新人发生第一次冲突后，您可以尽早退出检查给定邮政编码中冲突的循环，因为不会再找到唯一的。您也可以循环两次，在第一个循环中添加所有人，然后在第二个循环中进行测试，当您发现每个人的第一个冲突时跳出循环。