算法..查找最接近的相鄰矩形..在所有4個方向上

Question

哪種空間搜索算法將有助於查詢最近的相鄰矩形..對於給定的矩形..在所有4個方向上（即頂部，左側，底部，對）。

1：距離矩形的一邊正交於另一邊的另一邊。

2：矩形實際上代表窗體上的GUI組件。

Answer 1

做這OOP風格在Java中，假設軸從左下角開始，增加：

class Displacement 
{ 
    float top, bottom, left, right; 
    Rectangle r; 

    Displacement(Rectangle r) 
    { 
    this.r = r; 

    top = Math.max(r.y1, r.y2); 
    bottom = Math.min(r.y1, r.y2); 
    left = Math.min(r.x1, r.x2); 
    right = Math.max(r.x1, r.x2); 
    } 

    float minDistance(Displacement d) 
    { 
    float min = 10000.0f; 

    if (Math.abs(top - d.bottom) < min) 
     min = Math.abs(top - d.bottom); 
    if (Math.abs(bottom - d.top) < min) 
     min = Math.abs(bottom - d.top; 
    if (Math.abs(left - d.right) < min) 
     min = Math.abs(left - d.right); 
    if (Math.abs(right - d.left) < min) 
     min = Math.abs(right - d.left); 

    return min; 
    } 
} 

所以，現在你有一個矩形實例化一個對象計算矩形的最小和最大序列跨度，這Displacement目標是能夠找到minDistance(...)

與另一Displacement感謝最小距離現在你可以很容易地做這樣的事情：

class DistanceFinder 
{ 
    ArrayList<Displacement> displs = new ArrayList<Displacement>(); 

    void addRect(Rectangle r) 
    { 
    displs.add(new Displacement(r)); 
    } 

    Rectangle findNearest(Rectangle r) 
    { 
    Displacement current = new Displacement(r); 
    Displacement nearest = null; 
    float min = 10000.0f 

    for (Displacement d : displs) 
    { 
     float curDist = current.minDistance(d); 

     if (curDist < min) 
     { 
     nearest = d; 
     min = curDist; 
     } 
    } 
    return current; 
    } 
} 

我寫在Java中只給一個簡單的例子，但該方法可以在每一種語言相同..

你可以很容易地通過拆分您計算在不同cartinal距離的方式對待不同的方式各個方向方向，所以你可以做同樣的工作，我做了以前的代碼片段，但分裂爲每個軸。