求二维数组中非重叠区域间最小欧氏距离的高效算法

问题背景 #

• 存在二维数组Map[Height][Width]，每个单元格存储bool值
• 有两个非重叠区域RegionA和RegionB，均由唯一的相邻整数坐标组成
• 两个区域的坐标数量分别为m和n，且区域间的坐标在水平/垂直方向上均不相邻（互不接触）
• 区域的边界框可能重叠，区域内部可能存在孔洞，且一个区域可能包围另一个区域
• 坐标(X,Y)属于某区域时，Map[Y][X] == 1，否则为0

问题描述 #

需要找到分别属于RegionA和RegionB的两个坐标点A和B，使得它们之间的欧氏距离最小。暴力解法的时间复杂度为O(mn)，求时间效率更优（优于O(mn)）的算法，包括算法名称、描述或代码实现。

区域生成示例代码（仅用于生成测试数据，与问题无关） #

#include <cstdlib>
#include <cstring>
#include <vector>
#include <cstdio>
#include <map>
#include <ctime>
#include <cmath>

constexpr int Width = 150;
constexpr int Height = 37;
bool Map[Height][Width];

struct coord {
    int X, Y;
    coord(int X, int Y): X(X), Y(Y) {}
    bool operator==(const coord& Other) {
        return Other.X == X && Other.Y == Y;
    }
    bool IsAdjacentTo(const coord& Other){
        int ManhattanDistance = abs(X - Other.X) + abs(Y - Other.Y);
        return ManhattanDistance == 1;
    }
    bool IsOnMapEdge(){
        return X == 0 || Y == 0 || X == Width - 1 || Y == Height - 1;
    }
};

using region = std::vector<coord>;

void ClearMap(){
    std::memset(Map, 0, sizeof Map);
}
bool& GetMapBool(coord Coord) {
    return Map[Coord.Y][Coord.X];
}

int RandInt(int LowerBound, int UpperBound){
    return std::rand() % (UpperBound - LowerBound + 1) + LowerBound;
}

region CreateRegion(){
    std::puts("Creating Region");
    ClearMap();
    region Region;
    int RegionSize = RandInt(50, Width * Height / 2);
    Region.reserve(RegionSize);
    while (true){
        Region.emplace_back(
            RandInt(1, Width - 1), 
            RandInt(1, Height - 1)
        );
        if (!Region[0].IsOnMapEdge())
            break;
        else 
            Region.pop_back();
    }
    GetMapBool(Region[0]) = 1;
    while (Region.size() != RegionSize){
        coord Member = Region[RandInt(0, Region.size() - 1)];
        coord NeighbourToMakeAMember {
            RandInt(-1, 1) + Member.X,
            RandInt(-1, 1) + Member.Y
        };
        if (!Member.IsOnMapEdge() && !GetMapBool(NeighbourToMakeAMember) && Member.IsAdjacentTo(NeighbourToMakeAMember)){
            GetMapBool(NeighbourToMakeAMember) = 1;
            Region.push_back(NeighbourToMakeAMember);
        };
    }
    std::puts("Created Region");
    return Region;      
}

std::pair<region, region> CreateTwoRegions(){
    bool RegionsOverlap;
    std::pair<region, region> Regions;
    do {
        Regions.first = CreateRegion();
        Regions.second = CreateRegion();
        ClearMap();
        for (coord Member : Regions.first){
            GetMapBool(Member) = 1;
        }
        RegionsOverlap = 0;
        for (coord Member : Regions.second){
            if (GetMapBool(Member)){
                ClearMap();
                std::puts("Regions Overlap/Touch");
                RegionsOverlap = 1;
                break;
            } else {
                GetMapBool(Member) = 1;
            }
        }
    } while (RegionsOverlap);
    return Regions;
}

void DisplayMap(){
    for (int Y = 0; Y < Height; ++Y){
        for (int X = 0; X < Width; ++X)
            std::printf("%c", (Map[Y][X] ? '1' : '-'));
        std::puts("");
    }
}

int main(){
    int Seed = time(NULL);
    std::srand(Seed);
    ClearMap();
    auto[RegionA, RegionB] = CreateTwoRegions();
    DisplayMap();
}

问题图示 #

高效算法解决方案 #

1. 基于kd-tree的最近邻搜索算法 #

时间复杂度：O((m+n)log k)，其中k是较小区域的点数量（m或n）
原理：

• 将其中一个区域的点集构建为kd-tree（一种空间划分数据结构，适合高维点的最近邻查询）
• 遍历另一个区域的每个点，在kd-tree中执行最近邻查询，记录所有查询中距离最小的点对

优势：适合点集规模较大但远小于网格总容量的场景，比暴力法效率提升明显。

2. 多源Dijkstra算法（网格场景专用） #

时间复杂度：O(Width*Height log(Width*Height))
原理：

• 把RegionA的所有点作为初始节点，放入优先队列（按欧氏距离排序，初始距离为0）
• 维护一个距离矩阵，记录每个网格点到RegionA的最小欧氏距离，同时记录对应的RegionA中的点
• 每次从队列中取出距离最小的点，遍历其8个相邻网格点（欧氏距离考虑斜向），如果该点未被访问或找到更短距离，则更新距离并加入队列
• 当遇到属于RegionB的点时，直接返回该点和对应的RegionA点，这就是距离最小的点对（优先队列保证最先找到最短距离）

C++代码示例：

#include <vector>
#include <queue>
#include <cmath>
#include <climits>
#include <tuple>

using namespace std;

struct coord {
    int X, Y;
    coord(int X = 0, int Y = 0) : X(X), Y(Y) {}
    bool operator==(const coord& other) const {
        return X == other.X && Y == other.Y;
    }
};

using region = vector<coord>;

// 存储距离、当前点、对应的RegionA点
using QueueElement = tuple<double, coord, coord>;

pair<coord, coord> FindClosestPoints(const region& regionA, const region& regionB, int Width, int Height) {
    // 初始化距离矩阵和来源点矩阵
    vector<vector<double>> dist(Height, vector<double>(Width, INT_MAX));
    vector<vector<coord>> source(Height, vector<coord>(Width));
    
    // 优先队列：按距离从小到大排序
    priority_queue<QueueElement, vector<QueueElement>, greater<QueueElement>> pq;
    
    // 将RegionA的所有点加入队列
    for (const auto& a : regionA) {
        dist[a.Y][a.X] = 0.0;
        source[a.Y][a.X] = a;
        pq.emplace(0.0, a, a);
    }
    
    // 8个方向的偏移量
    const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    // 先把RegionB的点存入哈希集合，快速判断
    vector<vector<bool>> isRegionB(Height, vector<bool>(Width, false));
    for (const auto& b : regionB) {
        isRegionB[b.Y][b.X] = true;
    }
    
    while (!pq.empty()) {
        auto [currentDist, currPoint, srcPoint] = pq.top();
        pq.pop();
        
        // 如果当前点属于RegionB，直接返回结果
        if (isRegionB[currPoint.Y][currPoint.X]) {
            return {srcPoint, currPoint};
        }
        
        // 如果当前距离大于已记录的最小距离，跳过
        if (currentDist > dist[currPoint.Y][currPoint.X]) {
            continue;
        }
        
        // 遍历相邻点
        for (int i = 0; i < 8; ++i) {
            int nx = currPoint.X + dx[i];
            int ny = currPoint.Y + dy[i];
            if (nx >= 0 && nx < Width && ny >=0 && ny < Height) {
                double newDist = sqrt(pow(nx - srcPoint.X, 2) + pow(ny - srcPoint.Y, 2));
                if (newDist < dist[ny][nx]) {
                    dist[ny][nx] = newDist;
                    source[ny][nx] = srcPoint;
                    pq.emplace(newDist, coord(nx, ny), srcPoint);
                }
            }
        }
    }
    
    // 理论上不会走到这里，因为两个区域不重叠且存在
    return {coord(), coord()};
}

优势：适合网格规模不大的场景，无需额外处理点集的空间划分，逻辑直观，且能直接找到最小距离点对。

内容的提问来源于stack exchange，提问作者timmy george