3D点云顺时针排序生成连续路径问题求助
弯曲结构3D点云顺时针排序需求
我有一组带弯曲结构的3D点云,需要将点按顺时针排序以生成连续路径,但之前尝试的两种方法都失效了:
方法1:最近邻遍历排序
代码实现:
public static List<Point3D> OrderPointsLinearPath(List<Point3D> points) { if (points == null || points.Count <= 1) return points; // 存储排序后的点 var orderedPoints = new List<Point3D>(); var remainingPoints = new HashSet<Point3D>(points); // 从最左侧点开始 var currentPoint = remainingPoints.OrderBy(p => p.X).First(); orderedPoints.Add(currentPoint); remainingPoints.Remove(currentPoint); while (remainingPoints.Count > 0) { // 找到当前点的最近邻 var nearestPoint = remainingPoints .OrderBy(p => currentPoint.DistanceTo(p)) .First(); orderedPoints.Add(nearestPoint); currentPoint = nearestPoint; remainingPoints.Remove(nearestPoint); } return orderedPoints; }
问题:排序后左上角出现孤立点,原因是遍历到某一节点时,最近邻并非路径上的下一个连续点,导致路径跳点遗漏。
方法2:质心角度排序
先定义辅助类:
public class Ordered3DPoint { public Point3D centroid; public Point3D ro; public double AngleToCentroid; public Point3D RefPoint; public Ordered3DPoint(Point3D centroid, Point3D ro) { this.centroid = centroid; this.ro = ro; var delta = (ro - centroid); AngleToCentroid = Math.Atan2(-delta.Y, delta.X); RefPoint = ro; } }
排序逻辑:
var cX = points.Sum(ro => ro.X) / points.Count; var cY = points.Min(ro => ro.Y); var cZ = points.Sum(ro => ro.Z) / points.Count; var centroid = new Point3D(cX, cY, cZ); var orderedPoints = points.Select(ro => new Ordered3DPoint(points.First(), ro)).ToList(); points = orderedPoints.OrderByDescending(ro => ro.AngleToCentroid).Select(ro => ro.RefPoint).ToList(); return points;
问题:由于点云存在弯曲结构,基于全局质心的角度排序无法适配局部路径走向,排序结果不符合连续路径要求。
图示说明
- 排序结果示意图:显示路径在左上角出现孤立点的错误排序效果
- 原始点云图:呈现带有弯曲形态的3D点云原始分布
现寻求可适配弯曲结构、能正确实现3D点云顺时针排序且无孤立点的有效方案。
内容的提问来源于stack exchange,提问作者Coskun Ozogul
相关产品推荐
相关产品推荐

