如何在二维平面中高效查找指定半径内的点_网络技术

如何在二维平面中高效查找指定半径内的点

发布时间 - 2026-01-20 00:00:00 点击率：次

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

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

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

粗筛（O(1) per point）：以目标点 (cx, cy) 为中心，构建边长为 2r 的正方形包围盒（即 x ∈ [cx−r, cx+r]，y ∈ [cy−r, cy+r]）。该操作仅需两次浮点比较，可瞬间过滤掉绝大多数远离区域的点。
精筛（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))
避免常见误区：不要尝试用极坐标或角度划分，二维平面中矩形剪枝已是理论最优的低成本预判方式；也不必过早引入复杂算法——对数百至数千点，上述两阶段法已足够高效。

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

# mysql # php # red # 算法 # sqlite # postgresql # 数据库 # 低成本 # 进阶 # 浮点 # 中心点 # 两次 # 适用于 # 落在 # 已是 # 更快 # 数百

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：如何为多个相似图片元素编写通用XPath定位器

下一篇：解构赋值在javascript中怎么用_它能带来什么便利【教

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：如何为多个相似图片元素编写通用XPath定位器

下一篇：解构赋值在javascript中怎么用_它能带来什么便利【教