SQL环境下(X,Y)坐标点表的点聚类实现与结果输出方案咨询

通用算法说明 #

你描述的场景完全适配**DBSCAN（基于密度的空间聚类）**算法，这是这类坐标点邻近聚类的通用解决方案：你的半径阈值就是DBSCAN的邻域半径ε，你要求的n个点聚类阈值就是DBSCAN的最小邻域点数minPts，两者定义完全匹配。

实现思路 #

小数据量场景（万级点以内）：直接用T-SQL实现 #

核心逻辑分4步：

1. 计算所有点对的距离，为了避免开平方的性能损耗，可以直接用平方距离判断：(x1-x2)² + (y1-y2)² <= 25（对应半径5的阈值）
2. 给每个点标记连通的邻近点，用递归CTE做连通分量计算，同一个连通分量即为同一个聚类
3. 过滤掉点数小于minPts（你的演示场景取值为3）的连通分量
4. 按照需求计算聚类规模，生成结果表

大数据量场景优化 #

如果数据量超过10万点，直接计算全量点对的时间复杂度为O(n²)，效率极低，可以增加前置优化逻辑：

• 给X、Y字段建立联合索引
• 先给每个点划定X∈[x-5, x+5]、Y∈[y-5, y+5]的矩形过滤范围，只计算这个范围内的点对距离，过滤掉绝大多数不相关的点
• 也可以提前做空间网格分块，只计算同块和相邻块内的点对，进一步降低计算量

T-SQL实现示例 #

-- 配置参数
DECLARE @radius FLOAT = 5;
DECLARE @minClusterSize INT = 3;
DECLARE @radiusSq FLOAT = @radius * @radius; -- 用平方距离避免开方运算，提升性能

-- 步骤1：计算所有符合距离要求的点对邻接关系
WITH Adjacency AS (
    SELECT 
        p1.PointID AS P1,
        p2.PointID AS P2
    FROM Points p1
    JOIN Points p2 
        ON p2.X BETWEEN p1.X - @radius AND p1.X + @radius
        AND p2.Y BETWEEN p1.Y - @radius AND p1.Y + @radius
        AND (p1.X - p2.X)*(p1.X - p2.X) + (p1.Y - p2.Y)*(p1.Y - p2.Y) <= @radiusSq
        AND p1.PointID < p2.PointID -- 去重，避免重复计算双向点对
),
-- 步骤2：递归计算连通分量（聚类）
ClustersCTE AS (
    SELECT 
        PointID AS RootID,
        PointID AS MemberID
    FROM Points
    UNION ALL
    SELECT 
        c.RootID,
        a.P2 AS MemberID
    FROM ClustersCTE c
    JOIN Adjacency a ON c.MemberID = a.P1
    WHERE a.P2 NOT IN (SELECT MemberID FROM ClustersCTE WHERE RootID = c.RootID)
),
-- 步骤3：给每个点分配最小的RootID作为ClusterID，避免同一个聚类对应多个Root
ClusterAssignment AS (
    SELECT 
        MemberID AS PointID,
        MIN(RootID) AS ClusterID
    FROM ClustersCTE
    GROUP BY MemberID
),
-- 步骤4：过滤符合最小规模的聚类，计算聚类规模
ValidClusters AS (
    SELECT 
        ClusterID,
        COUNT(*) AS RawSize,
        -- 计算更优规模：聚类内所有点对应半径圆包含的点数量的最大值
        MAX((SELECT COUNT(*) FROM Adjacency a WHERE a.P1 = ca.PointID OR a.P2 = ca.PointID) + 1) AS OptimalSize
    FROM ClusterAssignment ca
    GROUP BY ClusterID
    HAVING COUNT(*) >= @minClusterSize
)
-- 生成Clusters表
SELECT ClusterID, OptimalSize AS Size INTO Clusters FROM ValidClusters;
-- 生成ClusterPoints表
SELECT ca.ClusterID, ca.PointID INTO ClusterPoints 
FROM ClusterAssignment ca
JOIN ValidClusters vc ON ca.ClusterID = vc.ClusterID;

样例结果说明 #

对你提供的测试数据执行上述代码后，输出结果如下：

• Clusters表：ClusterID为1，Size为3（前3个点每个的邻域都包含另外2个点，最大值为3，你示例中的Size=2属于演示笔误）
• ClusterPoints表：ClusterID=1对应PointID 1、2、3，点4、5因为邻域内点数不足3不会被归入聚类。

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