17370845950

本文介绍在二维直角坐标系中，通过“边界矩形预筛选 + 欧氏距离精筛”策略，快速定位某参考点指定半径内的所有邻近点，显著减少计算量，适用于php等通用编程环境。

在处理大量二维点（如 800×800 像素画布上的坐标数据）时，若对每个点都与其他全部点计算欧氏距离（时间复杂度 O(n²)），性能会随点数增长急剧下降。为提升效率，关键在于缩小候选集范围——即先用低成本操作快速排除明显超距的点，再对剩余少量候选点执行精确距离判断。

✅ 核心思想：两阶段筛选法

1. 粗筛（O(1) per point）：以目标点 (cx, cy) 为中心，构建边长为 2r 的正方形包围盒（即 x ∈ [cx−r, cx+r]，y ∈ [cy−r, cy+r]）。该操作仅需两次浮点比较，可瞬间过滤掉绝大多数远离区域的点。
2. 精筛（O(1) per candidate）：对落在包围盒内的点，再计算其到中心点的欧氏距离平方（避免开方运算）：
   dist² = (x − cx)² + (y − cy)²
   若 dist² ≤ r²，则该点确实在圆内。

⚠️ 注意：直接比较 dist² 与 r² 而非 dist ≤

r，可完全规避耗时的 sqrt() 运算，进一步提升性能。

? PHP 实现示例

function findPointsInRadius($points, $centerX, $centerY, $radius) {
    $rSquared = $radius * $radius;
    $candidates = [];

    // 阶段一：矩形预筛选（快速排除）
    foreach ($points as $point) {
        $dx = $point['x'] - $centerX;
        $dy = $point['y'] - $centerY;

        // 若超出正方形边界，跳过（绝对值比较比平方更快）
        if (abs($dx) > $radius || abs($dy) > $radius) {
            continue;
        }

        // 阶段二：欧氏距离平方精筛
        $distSquared = $dx * $dx + $dy * $dy;
        if ($distSquared <= $rSquared) {
            $candidates[] = $point;
        }
    }

    return $candidates;
}

// 使用示例
$points = [
    ['x' => 100, 'y' => 100],
    ['x' => 120, 'y' => 230],
    ['x' => 240, 'y' => 680],
    ['x' => 700, 'y' => 140],
];
$result = findPointsInRadius($points, 110, 105, 20); // 查找 (110,105) 半径20内的点
print_r($result);

? 进阶建议（当数据规模持续增大时）

• 空间索引优化：若点集静态或更新不频繁，可预构建四叉树（Quadtree） 或使用 R-Tree 索引（如通过 SQLite R*Tree 扩展或 PostGIS），将查询复杂度降至接近 O(log n)。
• 数据库层优化：若点存于 MySQL/PostgreSQL，可利用 WHERE x BETWEEN ? AND ? AND y BETWEEN ? AND ? 先走索引过滤，再用 SQRT(POW(x-?,2)+POW(y-?,2))
• 避免常见误区：不要尝试用极坐标或角度划分，二维平面中矩形剪枝已是理论最优的低成本预判方式；也不必过早引入复杂算法——对数百至数千点，上述两阶段法已足够高效。

该方法兼顾简洁性、可读性与实用性，是二维平面邻域查询的经典工程解法。