前段时间处理一批道路网数据时我一开始图省事直接对线段端点做 K-Means 聚类。结果很狼狈一条连续道路上相邻的两段线段端点坐标明明很接近却因为走向差了 90 度被算法硬生生划到了两个簇里而真正应该合并成同一条道路结构的若干平行线段又因为位置远近差异被拆散。后来我在一些工程代码里看到 “kmines” 这个写法再配合“类聚”“线段算法”这些词一搜才意识到这其实就是在 K-Means 思想之上针对线段对象做聚类的一套改造版思路。这篇文章就围绕“基于 kmines 类聚线段算法”展开把我自己踩过的坑、调过的参数、以及本地图中点和线段之间的几何处理逻辑都整理出来。无论你是做地图路网提取、CAD 图层自动分组、图像边缘线分组还是激光点云里的直线段聚合这套思路应该都能直接落地。1. 为什么点聚类处理不了线段一次失败实验的复盘1.1 线段与点之间差着“方向”这个维度先说那次失败的实验。原始数据是几十万根道路短线段每条线段都有起点坐标和终点坐标。我当时图省事把每条线段的中点、起点、终点全部堆进一个特征矩阵然后跑 K-Means。结果就是开头说的那个状态中点相近但方向不同的线段被分到同一组方向一致但位置偏远的线段又被分到不同组。问题出在哪K-Means 的本质是“在特征空间里按距离归堆”。如果把线段拆成端点坐标再喂进去算法只看到位置分布完全不知道“这是一根朝向 30 度的线段”还是“这是一根朝向 120 度的线段”。聚类结果自然和线段本身的几何语义无关。线段是带方向的几何对象它除了“位置”还有“走向”和“长度”。聚类时如果不把这些信息揉进距离度量里结果一定跑偏。这就是 kmines 这类“线段聚类”算法存在的意义它不是把线段降维成点而是把线段作为基本聚类对象在距离函数里同时考虑空间距离和方向差异。1.2 线段聚类到底能用在哪些场景这类算法的适用面其实很广我简单列几个遇到过的高频场景矢量地图路网整理从原始测绘数据里提取出大量短线需要把属于同一条道路的线段归组再做拟合变成完整道路。CAD 图纸图层自动分离一张图纸里混杂墙体线、门窗线、标注线位置相近但方向各异靠人工图层管理太耗时。图像边缘线段分组边缘检测之后得到一大堆短线段需要把同一轮廓上的线段聚拢为后续轮廓重建做准备。激光点云中的直线段聚合把点云拟合出的小线段按墙面、地面、边缘等语义归并。这些场景有一个共同点线段本身已经是“有意义的局部几何单元”下一步需要的是把局部单元组合成整体结构。这时候再去做点聚类就是绕远路。1.3 “kmines” 这个名字是怎么回事先说清楚kmines 并不是一个严格统一的算法名。我查过一些工程仓库和讨论它更像是 K-Means或者某个变体在“线段聚类”场景里的民间拼写有人写成 kmines有人写 kmeans-line-segment也有人直接叫 K-Segments。核心思路都是同一套初始化 K 个代表线段反复执行“分配—更新—再分配”的迭代过程直到代表线段稳定。所以下面讨论的内容你可以认为是“基于 K-Means 思想的线段聚类算法”。如果一时搜不到完全叫 kmines 的标准库也没关系用手写实现也不复杂。2. 距离度量设计线段聚类的核心几何问题2.1 点到线段的距离投影要分三种情况既然聚类对象是线段第一步先得定义“一条线段到另一条线段有多远”。大多数实现都会依赖一个基础函数点到线段的距离。这个距离不是简单的“点到直线距离”因为线段有端点约束。设线段端点为 a、b点为 p先计算投影参数 tt dot(p - a, b - a) / dot(b - a, b - a)然后把 t 限制到 [0, 1] 区间得到投影点 qt 在 [0, 1] 内q 是 p 在线段所在直线上的垂足距离是垂直距离t 小于 0q 等于 a距离是 p 到 a 的欧氏距离t 大于 1q 等于 b距离是 p 到 b 的欧氏距离。这么做的道理很直观一条线段不是无限长直线它的影响范围只在两个端点之间。如果 p 在线段延长线的正上方但离端点很远你仍把“垂线距离”当作距离就会把明显不相干的几何对象拉近。聚类初始化时最容易出现这种误差第一次迭代就可能把簇给带偏。2.2 方向差异怎么量化别忘了线段是无向的线段的方向不是向量方向而是“直线方向”也就是 0 度和 180 度其实是同一条直线。所以方向差异不能直接取 abs(theta1 - theta2)否则两条明显平行的线段会因为一条从左上到右下、一条从右下到左上被误判成“方向相差 180 度”。正确做法是先做无向化diff abs(theta1 - theta2) mod pi direction_diff min(diff, pi - diff)这样两条方向分别为 10 度和 190 度的线段方向差是 0属于完全平行。而一条 10 度和一条 100 度的线段方向差是 90 度属于正交。有些实现会把这个差值再除以 pi/2归一化到 0 到 1 之间方便和位置距离做加权组合。这个归一化不是必须的但强烈建议做一下不然角度量纲和坐标量纲混在一起时调参会很痛苦。2.3 组合距离公式位置、方向都要有但权重怎么给有了点到线段距离和方向差异之后一条线段 L 到代表线段 C 的距离可以写成D(L, C) w_p * point_segment_distance(L.midpoint, C) w_a * L_scale * direction_diff_normalized其中L.midpoint 是当前线段的中点point_segment_distance 是点到线段距离函数direction_diff_normalized 是归一化后的方向差异范围 0 到 1L_scale 是“特征长度”一般取当前数据集中线段的平均长度或者该簇内线段的平均长度w_p 是位置权重w_a 是方向权重。为什么要乘 L_scale因为 direction_diff_normalized 是无量纲的 0 到 1 值直接和坐标距离相加没有意义。乘以一个特征长度后相当于把“方向差 90 度”换算成“几何上大概偏离多少个长度单位”这样位置项和方向项才能在同一个量纲下比较。我自己常用的初始化参数是 w_p 1.0、w_a 0.3 到 0.5。这个比例适合大多数按坐标单位度量、线段长度在 1 到 10 个单位的场景。如果数据里的线段长度普遍是几百米L_scale 也要相应放大w_a 可以适当再调小。2.4 簇中心线段怎么更新K-Means 里簇中心是簇内所有点的平均值。线段聚类里簇中心也要是一条线段但“平均线段”没有唯一解。工程上比较稳妥的做法是分别算中点、方向和长度中心点簇内所有线段中点的加权平均值方向先把每条线段的方向角乘 2转成单位向量后求平均再把平均向量转回角度。为什么要乘 2因为 0 度和 180 度是同一个方向直接平均角度会出现“一条 10 度、一条 170 度平均成 90 度”的荒谬结果。乘 2 之后10 度变成 20 度170 度变成 340 度这两个向量的平均值指向 0 度方向正好是两条线段共同的主方向长度簇内所有线段长度的加权平均。最后以中心点为中心沿平均方向伸展一半平均长度就得到了新的代表线段。这个更新规则不是唯一方案但胜在稳定、直观、容易实现。我在项目里用过一段时间没有出现方向震荡或中心点漂移的问题。3. 算法主体流程分配与更新的完整拆解3.1 初始化K 值怎么定初始线段怎么挑线段聚类的整体流程和 K-Means 几乎一样。第一步是确定 K也就是希望把线段分成多少组。K 的选择没有万能公式通常结合场景来定如果是道路提取可以先做一次方向直方图统计估算大概有几个主方向再结合路网连通性确定 K如果是图层分离可以先人工看几张图估计图层数。确定 K 之后初始代表线段的选择会影响最终结果。最简单的做法是从数据里随机抽 K 条线段作为初始代表线段。但我建议用类似 K-Means 的做法先随机抽第一条然后每次选一条“离已有代表线段距离最远”的线段作为下一个初始种子。这样能显著减少收敛到局部最优的概率。3.2 分配步骤每条线段归属到哪一个簇分配阶段遍历所有线段对每条线段分别计算它到 K 个代表线段的组合距离 D选择距离最小的代表线段作为归属簇。这一步最核心的就是 2.3 节里的距离公式。如果位置权重和方向权重设置得不合理分配结果会在前几轮出现剧烈震荡。例如两条相距很近但方向垂直的线段如果方向权重太低它们可能被分到同一个簇等簇中心更新之后其中一条线段又会因为方向差异太大被踢出去来回反复迭代难以收敛。3.3 更新步骤重新计算代表线段所有线段完成分配后每个簇得到一组线段。接下来按 2.4 节的规则重新计算每个簇的代表线段作为下一轮分配的依据。这一步有个容易被忽略的小细节更新代表线段时应当只使用“位置权重”或“长度权重”来决定中点位置不要把方向信息混进位置计算。否则代表线段的位置会被方向奇异的短线段拉偏导致整个簇中心偏移。3.4 收敛判定及其稳定性迭代什么时候停常见判据有三个分配结果不再变化簇的成员集合稳定所有线段到其所属簇中心的距离总和变化小于某个阈值达到最大迭代次数比如 100 轮。我建议同时启用前两个判据。原则上 K-Means 类算法在有限次迭代后一定会收敛但可能收敛到局部最优所以不能只跑一次。实际工程里我会用 5 到 10 组随机初始化分别跑完整迭代最后选择“总距离最小”的那一次结果作为最终聚类。虽然多花点时间但结果稳定性好很多。3.5 一个可核对的迭代实例为了让你对流程有更直观的感觉我构造一个小例子。假设有 7 条线段编号起点终点长度方向角S1(0, 1)(3, 1)3.00°S2(1, 2)(4, 2)3.00°S3(8, 1)(11, 1.2)3.0约2°S4(5, 5)(5, 8)3.090°S5(6, 6)(6, 9)3.090°S6(1, 8)(1, 10)2.090°S7(0, 5)(0, 8)3.090°肉眼能看出这些线段大致分为两组一组是水平方向的 S1、S2、S3一组是垂直方向的 S4、S5、S6、S7。假设 K2初始代表线段选取 S1 和 S4。第一轮分配时S2 离 S1 很近方向也一致归到 A 簇S3 虽然水平位置偏右但它方向是 0 度左右距离 S1 的代表线段的组合距离比距离垂直的 S4 更小所以也归到 A 簇。S5、S6、S7 方向垂直归到 B 簇。第一轮更新之后A 簇代表线段大约在 (4, 1.4) 附近、方向接近 0 度B 簇代表线段大约在 (3.5, 7.5) 附近、方向接近 90 度。第二轮分配时所有线段归属不变迭代收敛。这个简单例子说明只要距离度量里同时包含位置和方向算法就能很自然地根据“方向主成分”把线段分开。4. 工程实现中最容易踩的坑4.1 线段长度差异太大导致聚类漂移我最早跑真实数据时发现一个问题数据里有一条特别长的线段比如几百米其他线段都是几米。聚类时这条长线段直接被选为初始代表线段更新簇中心后它的中点几乎决定了整个簇的位置周围较短但方向一致的线段反而被甩出去。根源在于组合距离公式里位置项用的是“线段中点”到代表线段的距离而长线段方向对中点的约束太强。处理办法有两种一是做长度归一化预处理。把特别长的线段按固定长度切分比如每 50 米一段保证参与聚类的对象尺度相近。二是更新代表线段时按线段长度加权长度越长的线段对簇中心和方向的贡献越大但超过一定阈值后权重不再线性增加避免单条线段一家独大。4.2 相交线段的方向歧义道路交叉口是最典型的例子。一条横路和一条竖路在空间上共用同一个区域甚至端点都相近。如果位置权重 w_p 太大聚类时很容易把这两条正交线段分到同一个簇导致后续拟合出来的“道路中心线”变成了一个 L 形拐角完全不符合实际路网结构。应对方案有两个方向。第一种是提高方向权重让算法宁可牺牲一点空间紧密度也要保证簇内方向一致。第二种是采用两阶段策略先按方向把线段分成几个大桶比如每 30 度一个桶再在每个桶内做空间聚类。这样交叉路口的横线、竖线在一开始就被分开了后续不容易互相污染。4.3 空簇与退化簇迭代过程中某个簇可能一个成员都没有分配到于是代表线段无法更新。空簇出现时常见策略是保留上一次迭代的代表线段或者重新选一条“距离其他代表线段最远”的线段作为新种子。后者更推荐因为它能把聚类从局部最优里拉出来。退化簇指的是簇内线段数量很少比如只有 1 到 2 条而且彼此位置相距很远。这种情况通常是 K 值设得太大或者局部最优导致的。可以先跑一次完整的聚类然后统计每个簇的成员数量把成员数小于阈值的簇合并到最近的邻居簇里再做一轮微调。4.4 性能优化大数据量下不能硬算线段聚类的每轮迭代都要计算 N 乘 K 次点到线段距离。N 是几万条时还能扛N 到几百万时就会很慢。我的优化经验是从两个方向下手一是空间索引。用 R 树或网格索引先把代表线段的位置信息建起来分配阶段只需对每条线段查找邻近的几个簇不需要遍历全部 K 个簇。这个优化在 K 比较大时特别明显。二是方向分桶加速。在分配之前把线段按方向角分桶每条线段只需要和“方向相近”的那几个桶里的代表线段计算距离。实现时要注意边界处理比如一条方向 170 度的线段也要去 0 度附近的桶里找候选。5. 效果评测与参数调试心得5.1 评价指标不能只看簇内距离只用“簇内点到代表线段的平均距离”来评价聚类结果很容易出现假象方向一致的线段被聚成一簇但簇与簇之间在空间上重叠严重。所以我会同时看两个指标位置误差每条线段的中点到簇代表线段的垂直距离平均值反映空间紧密度方向误差簇内线段方向角的标准差反映方向一致性。如果位置误差小、方向误差大说明方向权重不够簇内混入了方向杂乱的线段。反过来方向误差小、位置误差大说明位置权重偏弱或者 K 值太小不同位置的同向线段被强行合并。5.2 K 值选择肘部法则之外的实用技巧肘部法则在所有聚类算法里都适用线段聚类也不例外。连续跑 K2 到 K10把“所有线段到簇中心的总距离”画成曲线找一个拐点。但更实用的办法是结合业务。例如道路提取目标是获得 20 条完整道路那 K 就可以初始设成 40因为每条道路可能会被切分成两段。跑完聚类后再对每个簇内的线段做一次合并把合并后的条数压到目标值。这样既减少了 K 值的敏感性又给后续处理留了余地。5.3 权重调参的经验法则w_p 和 w_a 的调参没有标准答案但我总结了一套可复用的经验先把 w_p 固定为 1.0w_a 设为 0.3跑一遍完整聚类用上一节的指标做一次评估如果同一个簇里出现明显正交或大角度交叉的线段说明 w_a 太小把 w_a 调到 0.5 或 0.8 再跑如果不同簇之间出现空间重叠说明 w_a 太大把 w_a 调回 0.2 附近数据里线段的平均长度变化很大时优先调整 L_scale而不是频繁动 w_p 和 w_a。另外强烈建议在调试阶段把每轮迭代的中间结果可视化出来。只看最终结果很难判断是初始化太差、距离度量不对、还是 K 值选错了。把每个簇的代表线段画在图上跟着迭代过程看几条基本能一眼定位问题。6. 扩展思路从“聚类线段”到“线段合并与结构化”6.1 与 DBSCAN、HDBSCAN 的对比线段聚类也不是只有 K-Means 这一条路。DBSCAN 和 HDBSCAN 同样能对线段做聚类只需要把每条线段编码成特征向量比如 [中点 x, 中点 y, 方向角, 长度]再用带噪音的密度聚类。但 DBSCAN 类方法的问题在于它不区分“簇的方向一致性”。两条线段空间上靠近如果它们只是端点碰在一起、方向完全不同DBSCAN 仍然会把它们算作同一个簇除非你把方向编码成足够强的维度并且把 eps 调得很小。这在实际工程里很别扭因为你既要保证空间连通又要保证方向一致eps 很难同时满足两个维度。相比之下K-Means 类线段聚类把距离度量设计成“位置 方向”的加权组合语义更直接。它在处理“规整方向占主导”的数据时优势明显比如道路、建筑轮廓。缺点是簇形状只能是凸的如果目标簇是弯曲的道路一条弧线会被切成多段直线后聚成多个簇这需要在后续做线段合并。6.2 聚完类之后怎么把线段合并成完整结构聚类只是第一步。以道路提取为例每个簇里往往有几十条破碎短线需要拟合成一条长线。最常用的做法是 PCA 主成分分析把簇内所有线段的端点作为点集求协方差矩阵的主方向然后沿主方向做长度范围的投影得到一条合并后的长线段。如果簇内方向高度一致还可以做带约束的最小二乘拟合强行让拟合结果的方向等于簇的主方向。这个做法在 CAD 图层分离里很好用能把同一面墙的缺口补上输出干净的矢量边线。6.3 具体落地的先后顺序建议最后分享一个我在项目里的落地方案。先不急着写完整算法而是分四步走先写一个“点到线段距离”函数用几十条测试数据验证正确性再写“组合距离”函数把位置、方向、长度三个信息都放进去跑通一次完整的“分配—更新”迭代在图上画出前两轮的结果最后加上初始化策略、收敛判据和空簇处理。每一步都能独立验证最后合在一起时问题会少很多。我见过不少同事一上来就把 K-Means 模板套上最后调试距离函数时已经分不清是分配逻辑问题还是更新逻辑问题。先小步跑通再放大规模线段聚类这个算法并没有想象中那么复杂。 
长河君 · 2026/9/9 9:28:17 · 阅读 1.2k kmines类聚线段算法：从距离度量到工程实现
前段时间处理一批道路网数据时我一开始图省事直接对线段端点做 K-Means 聚类。结果很狼狈一条连续道路上相邻的两段线段端点坐标明明很接近却因为走向差了 90 度被算法硬生生划到了两个簇里而真正应该合并成同一条道路结构的若干平行线段又因为位置远近差异被拆散。后来我在一些工程代码里看到 “kmines” 这个写法再配合“类聚”“线段算法”这些词一搜才意识到这其实就是在 K-Means 思想之上针对线段对象做聚类的一套改造版思路。这篇文章就围绕“基于 kmines 类聚线段算法”展开把我自己踩过的坑、调过的参数、以及本地图中点和线段之间的几何处理逻辑都整理出来。无论你是做地图路网提取、CAD 图层自动分组、图像边缘线分组还是激光点云里的直线段聚合这套思路应该都能直接落地。1. 为什么点聚类处理不了线段一次失败实验的复盘1.1 线段与点之间差着“方向”这个维度先说那次失败的实验。原始数据是几十万根道路短线段每条线段都有起点坐标和终点坐标。我当时图省事把每条线段的中点、起点、终点全部堆进一个特征矩阵然后跑 K-Means。结果就是开头说的那个状态中点相近但方向不同的线段被分到同一组方向一致但位置偏远的线段又被分到不同组。问题出在哪K-Means 的本质是“在特征空间里按距离归堆”。如果把线段拆成端点坐标再喂进去算法只看到位置分布完全不知道“这是一根朝向 30 度的线段”还是“这是一根朝向 120 度的线段”。聚类结果自然和线段本身的几何语义无关。线段是带方向的几何对象它除了“位置”还有“走向”和“长度”。聚类时如果不把这些信息揉进距离度量里结果一定跑偏。这就是 kmines 这类“线段聚类”算法存在的意义它不是把线段降维成点而是把线段作为基本聚类对象在距离函数里同时考虑空间距离和方向差异。1.2 线段聚类到底能用在哪些场景这类算法的适用面其实很广我简单列几个遇到过的高频场景矢量地图路网整理从原始测绘数据里提取出大量短线需要把属于同一条道路的线段归组再做拟合变成完整道路。CAD 图纸图层自动分离一张图纸里混杂墙体线、门窗线、标注线位置相近但方向各异靠人工图层管理太耗时。图像边缘线段分组边缘检测之后得到一大堆短线段需要把同一轮廓上的线段聚拢为后续轮廓重建做准备。激光点云中的直线段聚合把点云拟合出的小线段按墙面、地面、边缘等语义归并。这些场景有一个共同点线段本身已经是“有意义的局部几何单元”下一步需要的是把局部单元组合成整体结构。这时候再去做点聚类就是绕远路。1.3 “kmines” 这个名字是怎么回事先说清楚kmines 并不是一个严格统一的算法名。我查过一些工程仓库和讨论它更像是 K-Means或者某个变体在“线段聚类”场景里的民间拼写有人写成 kmines有人写 kmeans-line-segment也有人直接叫 K-Segments。核心思路都是同一套初始化 K 个代表线段反复执行“分配—更新—再分配”的迭代过程直到代表线段稳定。所以下面讨论的内容你可以认为是“基于 K-Means 思想的线段聚类算法”。如果一时搜不到完全叫 kmines 的标准库也没关系用手写实现也不复杂。2. 距离度量设计线段聚类的核心几何问题2.1 点到线段的距离投影要分三种情况既然聚类对象是线段第一步先得定义“一条线段到另一条线段有多远”。大多数实现都会依赖一个基础函数点到线段的距离。这个距离不是简单的“点到直线距离”因为线段有端点约束。设线段端点为 a、b点为 p先计算投影参数 tt dot(p - a, b - a) / dot(b - a, b - a)然后把 t 限制到 [0, 1] 区间得到投影点 qt 在 [0, 1] 内q 是 p 在线段所在直线上的垂足距离是垂直距离t 小于 0q 等于 a距离是 p 到 a 的欧氏距离t 大于 1q 等于 b距离是 p 到 b 的欧氏距离。这么做的道理很直观一条线段不是无限长直线它的影响范围只在两个端点之间。如果 p 在线段延长线的正上方但离端点很远你仍把“垂线距离”当作距离就会把明显不相干的几何对象拉近。聚类初始化时最容易出现这种误差第一次迭代就可能把簇给带偏。2.2 方向差异怎么量化别忘了线段是无向的线段的方向不是向量方向而是“直线方向”也就是 0 度和 180 度其实是同一条直线。所以方向差异不能直接取 abs(theta1 - theta2)否则两条明显平行的线段会因为一条从左上到右下、一条从右下到左上被误判成“方向相差 180 度”。正确做法是先做无向化diff abs(theta1 - theta2) mod pi direction_diff min(diff, pi - diff)这样两条方向分别为 10 度和 190 度的线段方向差是 0属于完全平行。而一条 10 度和一条 100 度的线段方向差是 90 度属于正交。有些实现会把这个差值再除以 pi/2归一化到 0 到 1 之间方便和位置距离做加权组合。这个归一化不是必须的但强烈建议做一下不然角度量纲和坐标量纲混在一起时调参会很痛苦。2.3 组合距离公式位置、方向都要有但权重怎么给有了点到线段距离和方向差异之后一条线段 L 到代表线段 C 的距离可以写成D(L, C) w_p * point_segment_distance(L.midpoint, C) w_a * L_scale * direction_diff_normalized其中L.midpoint 是当前线段的中点point_segment_distance 是点到线段距离函数direction_diff_normalized 是归一化后的方向差异范围 0 到 1L_scale 是“特征长度”一般取当前数据集中线段的平均长度或者该簇内线段的平均长度w_p 是位置权重w_a 是方向权重。为什么要乘 L_scale因为 direction_diff_normalized 是无量纲的 0 到 1 值直接和坐标距离相加没有意义。乘以一个特征长度后相当于把“方向差 90 度”换算成“几何上大概偏离多少个长度单位”这样位置项和方向项才能在同一个量纲下比较。我自己常用的初始化参数是 w_p 1.0、w_a 0.3 到 0.5。这个比例适合大多数按坐标单位度量、线段长度在 1 到 10 个单位的场景。如果数据里的线段长度普遍是几百米L_scale 也要相应放大w_a 可以适当再调小。2.4 簇中心线段怎么更新K-Means 里簇中心是簇内所有点的平均值。线段聚类里簇中心也要是一条线段但“平均线段”没有唯一解。工程上比较稳妥的做法是分别算中点、方向和长度中心点簇内所有线段中点的加权平均值方向先把每条线段的方向角乘 2转成单位向量后求平均再把平均向量转回角度。为什么要乘 2因为 0 度和 180 度是同一个方向直接平均角度会出现“一条 10 度、一条 170 度平均成 90 度”的荒谬结果。乘 2 之后10 度变成 20 度170 度变成 340 度这两个向量的平均值指向 0 度方向正好是两条线段共同的主方向长度簇内所有线段长度的加权平均。最后以中心点为中心沿平均方向伸展一半平均长度就得到了新的代表线段。这个更新规则不是唯一方案但胜在稳定、直观、容易实现。我在项目里用过一段时间没有出现方向震荡或中心点漂移的问题。3. 算法主体流程分配与更新的完整拆解3.1 初始化K 值怎么定初始线段怎么挑线段聚类的整体流程和 K-Means 几乎一样。第一步是确定 K也就是希望把线段分成多少组。K 的选择没有万能公式通常结合场景来定如果是道路提取可以先做一次方向直方图统计估算大概有几个主方向再结合路网连通性确定 K如果是图层分离可以先人工看几张图估计图层数。确定 K 之后初始代表线段的选择会影响最终结果。最简单的做法是从数据里随机抽 K 条线段作为初始代表线段。但我建议用类似 K-Means 的做法先随机抽第一条然后每次选一条“离已有代表线段距离最远”的线段作为下一个初始种子。这样能显著减少收敛到局部最优的概率。3.2 分配步骤每条线段归属到哪一个簇分配阶段遍历所有线段对每条线段分别计算它到 K 个代表线段的组合距离 D选择距离最小的代表线段作为归属簇。这一步最核心的就是 2.3 节里的距离公式。如果位置权重和方向权重设置得不合理分配结果会在前几轮出现剧烈震荡。例如两条相距很近但方向垂直的线段如果方向权重太低它们可能被分到同一个簇等簇中心更新之后其中一条线段又会因为方向差异太大被踢出去来回反复迭代难以收敛。3.3 更新步骤重新计算代表线段所有线段完成分配后每个簇得到一组线段。接下来按 2.4 节的规则重新计算每个簇的代表线段作为下一轮分配的依据。这一步有个容易被忽略的小细节更新代表线段时应当只使用“位置权重”或“长度权重”来决定中点位置不要把方向信息混进位置计算。否则代表线段的位置会被方向奇异的短线段拉偏导致整个簇中心偏移。3.4 收敛判定及其稳定性迭代什么时候停常见判据有三个分配结果不再变化簇的成员集合稳定所有线段到其所属簇中心的距离总和变化小于某个阈值达到最大迭代次数比如 100 轮。我建议同时启用前两个判据。原则上 K-Means 类算法在有限次迭代后一定会收敛但可能收敛到局部最优所以不能只跑一次。实际工程里我会用 5 到 10 组随机初始化分别跑完整迭代最后选择“总距离最小”的那一次结果作为最终聚类。虽然多花点时间但结果稳定性好很多。3.5 一个可核对的迭代实例为了让你对流程有更直观的感觉我构造一个小例子。假设有 7 条线段编号起点终点长度方向角S1(0, 1)(3, 1)3.00°S2(1, 2)(4, 2)3.00°S3(8, 1)(11, 1.2)3.0约2°S4(5, 5)(5, 8)3.090°S5(6, 6)(6, 9)3.090°S6(1, 8)(1, 10)2.090°S7(0, 5)(0, 8)3.090°肉眼能看出这些线段大致分为两组一组是水平方向的 S1、S2、S3一组是垂直方向的 S4、S5、S6、S7。假设 K2初始代表线段选取 S1 和 S4。第一轮分配时S2 离 S1 很近方向也一致归到 A 簇S3 虽然水平位置偏右但它方向是 0 度左右距离 S1 的代表线段的组合距离比距离垂直的 S4 更小所以也归到 A 簇。S5、S6、S7 方向垂直归到 B 簇。第一轮更新之后A 簇代表线段大约在 (4, 1.4) 附近、方向接近 0 度B 簇代表线段大约在 (3.5, 7.5) 附近、方向接近 90 度。第二轮分配时所有线段归属不变迭代收敛。这个简单例子说明只要距离度量里同时包含位置和方向算法就能很自然地根据“方向主成分”把线段分开。4. 工程实现中最容易踩的坑4.1 线段长度差异太大导致聚类漂移我最早跑真实数据时发现一个问题数据里有一条特别长的线段比如几百米其他线段都是几米。聚类时这条长线段直接被选为初始代表线段更新簇中心后它的中点几乎决定了整个簇的位置周围较短但方向一致的线段反而被甩出去。根源在于组合距离公式里位置项用的是“线段中点”到代表线段的距离而长线段方向对中点的约束太强。处理办法有两种一是做长度归一化预处理。把特别长的线段按固定长度切分比如每 50 米一段保证参与聚类的对象尺度相近。二是更新代表线段时按线段长度加权长度越长的线段对簇中心和方向的贡献越大但超过一定阈值后权重不再线性增加避免单条线段一家独大。4.2 相交线段的方向歧义道路交叉口是最典型的例子。一条横路和一条竖路在空间上共用同一个区域甚至端点都相近。如果位置权重 w_p 太大聚类时很容易把这两条正交线段分到同一个簇导致后续拟合出来的“道路中心线”变成了一个 L 形拐角完全不符合实际路网结构。应对方案有两个方向。第一种是提高方向权重让算法宁可牺牲一点空间紧密度也要保证簇内方向一致。第二种是采用两阶段策略先按方向把线段分成几个大桶比如每 30 度一个桶再在每个桶内做空间聚类。这样交叉路口的横线、竖线在一开始就被分开了后续不容易互相污染。4.3 空簇与退化簇迭代过程中某个簇可能一个成员都没有分配到于是代表线段无法更新。空簇出现时常见策略是保留上一次迭代的代表线段或者重新选一条“距离其他代表线段最远”的线段作为新种子。后者更推荐因为它能把聚类从局部最优里拉出来。退化簇指的是簇内线段数量很少比如只有 1 到 2 条而且彼此位置相距很远。这种情况通常是 K 值设得太大或者局部最优导致的。可以先跑一次完整的聚类然后统计每个簇的成员数量把成员数小于阈值的簇合并到最近的邻居簇里再做一轮微调。4.4 性能优化大数据量下不能硬算线段聚类的每轮迭代都要计算 N 乘 K 次点到线段距离。N 是几万条时还能扛N 到几百万时就会很慢。我的优化经验是从两个方向下手一是空间索引。用 R 树或网格索引先把代表线段的位置信息建起来分配阶段只需对每条线段查找邻近的几个簇不需要遍历全部 K 个簇。这个优化在 K 比较大时特别明显。二是方向分桶加速。在分配之前把线段按方向角分桶每条线段只需要和“方向相近”的那几个桶里的代表线段计算距离。实现时要注意边界处理比如一条方向 170 度的线段也要去 0 度附近的桶里找候选。5. 效果评测与参数调试心得5.1 评价指标不能只看簇内距离只用“簇内点到代表线段的平均距离”来评价聚类结果很容易出现假象方向一致的线段被聚成一簇但簇与簇之间在空间上重叠严重。所以我会同时看两个指标位置误差每条线段的中点到簇代表线段的垂直距离平均值反映空间紧密度方向误差簇内线段方向角的标准差反映方向一致性。如果位置误差小、方向误差大说明方向权重不够簇内混入了方向杂乱的线段。反过来方向误差小、位置误差大说明位置权重偏弱或者 K 值太小不同位置的同向线段被强行合并。5.2 K 值选择肘部法则之外的实用技巧肘部法则在所有聚类算法里都适用线段聚类也不例外。连续跑 K2 到 K10把“所有线段到簇中心的总距离”画成曲线找一个拐点。但更实用的办法是结合业务。例如道路提取目标是获得 20 条完整道路那 K 就可以初始设成 40因为每条道路可能会被切分成两段。跑完聚类后再对每个簇内的线段做一次合并把合并后的条数压到目标值。这样既减少了 K 值的敏感性又给后续处理留了余地。5.3 权重调参的经验法则w_p 和 w_a 的调参没有标准答案但我总结了一套可复用的经验先把 w_p 固定为 1.0w_a 设为 0.3跑一遍完整聚类用上一节的指标做一次评估如果同一个簇里出现明显正交或大角度交叉的线段说明 w_a 太小把 w_a 调到 0.5 或 0.8 再跑如果不同簇之间出现空间重叠说明 w_a 太大把 w_a 调回 0.2 附近数据里线段的平均长度变化很大时优先调整 L_scale而不是频繁动 w_p 和 w_a。另外强烈建议在调试阶段把每轮迭代的中间结果可视化出来。只看最终结果很难判断是初始化太差、距离度量不对、还是 K 值选错了。把每个簇的代表线段画在图上跟着迭代过程看几条基本能一眼定位问题。6. 扩展思路从“聚类线段”到“线段合并与结构化”6.1 与 DBSCAN、HDBSCAN 的对比线段聚类也不是只有 K-Means 这一条路。DBSCAN 和 HDBSCAN 同样能对线段做聚类只需要把每条线段编码成特征向量比如 [中点 x, 中点 y, 方向角, 长度]再用带噪音的密度聚类。但 DBSCAN 类方法的问题在于它不区分“簇的方向一致性”。两条线段空间上靠近如果它们只是端点碰在一起、方向完全不同DBSCAN 仍然会把它们算作同一个簇除非你把方向编码成足够强的维度并且把 eps 调得很小。这在实际工程里很别扭因为你既要保证空间连通又要保证方向一致eps 很难同时满足两个维度。相比之下K-Means 类线段聚类把距离度量设计成“位置 方向”的加权组合语义更直接。它在处理“规整方向占主导”的数据时优势明显比如道路、建筑轮廓。缺点是簇形状只能是凸的如果目标簇是弯曲的道路一条弧线会被切成多段直线后聚成多个簇这需要在后续做线段合并。6.2 聚完类之后怎么把线段合并成完整结构聚类只是第一步。以道路提取为例每个簇里往往有几十条破碎短线需要拟合成一条长线。最常用的做法是 PCA 主成分分析把簇内所有线段的端点作为点集求协方差矩阵的主方向然后沿主方向做长度范围的投影得到一条合并后的长线段。如果簇内方向高度一致还可以做带约束的最小二乘拟合强行让拟合结果的方向等于簇的主方向。这个做法在 CAD 图层分离里很好用能把同一面墙的缺口补上输出干净的矢量边线。6.3 具体落地的先后顺序建议最后分享一个我在项目里的落地方案。先不急着写完整算法而是分四步走先写一个“点到线段距离”函数用几十条测试数据验证正确性再写“组合距离”函数把位置、方向、长度三个信息都放进去跑通一次完整的“分配—更新”迭代在图上画出前两轮的结果最后加上初始化策略、收敛判据和空簇处理。每一步都能独立验证最后合在一起时问题会少很多。我见过不少同事一上来就把 K-Means 模板套上最后调试距离函数时已经分不清是分配逻辑问题还是更新逻辑问题。先小步跑通再放大规模线段聚类这个算法并没有想象中那么复杂。