在3D陣列中搜索滿足某個謂詞的最近點

Question

我正在尋找枚舉算法來搜索圍繞給定起點的3D陣列「sphering」。

給定一個數組大小NxNxN其中每個N是2^k一些k的a，並且陣列中的點p。我正在查找的算法應執行以下操作：如果a[p]滿足某個謂詞，則算法停止並返回p。否則，將檢查下一個點q，其中q是陣列中最接近p且尚未訪問的另一點。如果兩者都不匹配，則檢查下一個q'，直到在最壞的情況下整個數組已被搜索。

通過「最接近」這裏完美的解決方案將是點q具有最小的歐幾里得距離p。由於只有離散點必須被考慮，所以也許一些聰明的枚舉算法可以實現這一點。但是，如果這太複雜了，那麼最小的曼哈頓距離也可以。如果有幾個最近的點，下一個考慮哪一個並不重要。

是否已有可用於此任務的算法？

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) 

基本上你消耗從發電機點，直到其中一個滿足您謂語。

Answer 2

這是一個簡單算法的僞代碼，該算法將在增加半徑的球形外殼中搜索，直到找到一個點或它用完陣列。讓我們假設condition返回true或false，並先後獲得了X，Y，Z座標進行測試和陣列本身，出界外返回false（而不是爆炸）座標：

def find_from_center(center, max_radius, condition) returns a point 
    let radius = 0 
    while radius < max_radius, 
    let point = find_in_spherical_husk(center, radius, condition) 
    if (point != null) return point 
    radius ++ 
    return null 

難度部分在find_in_spherical_husk之內。我們有興趣檢查出這樣的點

dist(center, p) >= radius AND dist(center, p) < radius+1 

這將是我們的穀殼操作定義。我們可以在O（n^3）中遍歷整個3D數組尋找這些數據，但是這在時間上會非常昂貴。更好的僞代碼如下：

def find_in_spherical_husk(center, radius, condition) 
    let z = center.z - radius // current slice height 
    let r = 0 // current circle radius; maxes at equator, then decreases 
    while z <= center + radius, 
    let z_center = (z, center.x, point.y) 
    let point = find_in_z_circle(z_center, r) 
    if (point != null) return point 
    // prepare for next z-sliced cirle 
    z ++ 
    r = sqrt(radius*radius - (z-center.z)*(z-center.z)) 

這裏的想法是給每個殼切成沿Z軸（任意軸都可以）圈，然後看看每個切片分別。如果你在看地球，而兩極是z軸，那麼你會從北向南切片。最後，您將執行find_in_z_circle(z_center, r, condition)來查看每個圓圈的圓周。您可以使用Bresenham circle-drawing algorithm來避免一些數學問題;但我認爲與檢查condition相比，節省的費用可以忽略不計。