Sorting 3D points to generate a continuous line

Question

I have a point cloud and I want to sort points clockwise.

I am trying to use this code:

public static List<Point3D> OrderPointsLinearPath(List<Point3D> points)
{
    if (points == null || points.Count <= 1)
        return points;

    // Create a list to store the ordered points
    var orderedPoints = new List<Point3D>();
    var remainingPoints = new HashSet<Point3D>(points);

    // Start with the leftmost point
    var currentPoint = remainingPoints.OrderBy(p => p.X).First();
    orderedPoints.Add(currentPoint);
    remainingPoints.Remove(currentPoint);

    while (remainingPoints.Count > 0)
    {
        // Find the closest point to the current point
        var nearestPoint = remainingPoints
            .OrderBy(p => currentPoint.DistanceTo(p))
            .First();

        orderedPoints.Add(nearestPoint);
        currentPoint = nearestPoint;
        remainingPoints.Remove(nearestPoint);
    }

    return orderedPoints;
}

The problem is on the top left side of the image, there is an orphelin point left as shown on the second image.

I understand why. If we imagine that I am starting from the first point on the image and take the nearest to continue, when I am on the 10th point, the 12th point is closer than the 11th one.

I tried many thing like taking the centroid and ordering by

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;

It doesn't work because of the forms bent structure.

I

try something involving "momentum", or direction at least. Olivier's answer below embodies that. -- your points are spaced somewhat lumpily. that can cause trouble. you might have to involve additional logic, modify the "cost function" that decides which point to pick. sharp corners will always be tricky. — Christoph Rackwitz
– Christoph Rackwitz, Commented Mar 5 at 21:59
Yes (angle of advance) ... it's a path (of points) one should be able to crawl. Geometry allows for smoothing. — Gerry Schmitz
– Gerry Schmitz, Commented Mar 6 at 0:14

Olivier Jacot-Descombes · Accepted Answer · 2025-03-06 15:10:27Z

1

Except for the first point, I would not take the distance to the current point, but the distance to the next expected point position.

Get the next expected point like this:

expected = current + (current - previous) = 2 * current - previous

If this skips points because the distance between two consecutive points is very uneven, you can tweak the formula by going only partially towards the next expected point. Example of going only half-way:

expected = current + 0.5 * (current - previous)

Also, repeatedly ordering points by distance is very inefficient. Use a space-partitioning data structure suited to store spatial data like k-d tree (Wikipedia). I have created one here: CySoft.Collections.Geometry (Github)

edited Mar 6 at 15:10

answered Mar 5 at 17:55

Olivier Jacot-Descombes

114k14 gold badges149 silver badges202 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Coskun Ozogul Mar 6 at 7:59

Olivier, thanks for this answer. I am going to try this out. The github link is broken.

Olivier Jacot-Descombes Mar 6 at 14:45

Sorry, it was private. I made it public and the link should work now.

Collectives™ on Stack Overflow

Sorting 3D points to generate a continuous line

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related