algorithm - 在 3D 数组中搜索满足特定谓词的最近点

Question

我正在寻找一种枚举算法来搜索围绕给定起点“球形”的 3D 数组。

给定一个大小为 NxNxN 的数组 a，其中对于某些 ，每个 N 是 2^k k，以及该数组中的一个点p。我正在寻找的算法应该执行以下操作:如果 a[p] 满足某个谓词，则算法停止并返回 p。否则，检查下一个点 q，其中 q 是数组中距离 p 最近且尚未访问过的另一个点。如果两者都不匹配，则检查下一个q'，依此类推，直到在最坏的情况下搜索整个数组。

这里所说的“最接近”，完美的解决方案是与 p 具有最小欧几里德距离的点 q。由于只需考虑离散点，也许一些聪明的枚举算法可以使之成为可能。然而，如果这变得太复杂，最小的曼哈顿距离也可以。如果有多个最近的点，那么接下来考虑哪一个并不重要。

是否已有可用于此任务的算法？

Answer 1

您可以搜索增加的平方距离，这样您就不会错过任何一点。这段 python 代码应该清楚地说明了这一点:

import math
import itertools

# Calculates all points at a certain distance.
# Coordinate constraint: z <= y <= x
def get_points_at_squared_euclidean_distance(d):
    result = []
    x = int(math.floor(math.sqrt(d)))
    while 0 <= x:
        y = x
        while 0 <= y:
            target = d - x*x - y*y
            lower = 0
            upper = y + 1
            while lower < upper:
                middle = (lower + upper) / 2
                current = middle * middle
                if current == target:
                    result.append((x, y, middle))
                    break
                if current < target:
                    lower = middle + 1
                else:
                    upper = middle
            y -= 1
        x -= 1
    return result

# Creates all possible reflections of a point
def get_point_reflections(point):
    result = set()
    for p in itertools.permutations(point):
        for n in range(8):
            result.add((
                p[0] * (1 if n % 8 < 4 else -1),
                p[1] * (1 if n % 4 < 2 else -1),
                p[2] * (1 if n % 2 < 1 else -1),
            ))
    return sorted(result)

# Enumerates all points around a center, in increasing distance
def get_next_point_near(center):
    d = 0
    points_at_d = []
    while True:
        while not points_at_d:
            d += 1
            points_at_d = get_points_at_squared_euclidean_distance(d)
        point = points_at_d.pop()
        for reflection in get_point_reflections(point):
            yield (
                center[0] + reflection[0],
                center[1] + reflection[1],
                center[2] + reflection[2],
            )

# The function you asked for
def get_nearest_point(center, predicate):
    for point in get_next_point_near(center):
        if predicate(point):
            return point

# Example usage
print get_nearest_point((1,2,3), lambda p: sum(p) == 10)

基本上，您会消耗生成器中的点，直到其中一个点满足您的谓词。