Geometry_Engine: Sort list of points to minimise distance between all points

[jamesramsden-bh]

Take a list of points. You want to reorder this list so that, if you measure the distance between each consecutive pair of points, then sum these distances for the list, the overall distance is minimised. This is the gist of the Travelling Salesman Problem.

While the full solution to the TSP is NP-hard, I created a simplified version in GH/C#, which could be useful to be formalised into the BHoM. While the full TSP aims for a global optimum, my version is much simpler (and non-globally-optimal in the general case):

• Pick a start point and add it to the new sorted list. Remove this point from the pool of remaining points.
• Find the nearest point to the first point, and add that to the sorted list, and remove it from the pool of remaining points.
• Repeat the above point for all other points.

The GH code is below, and would need to be adapted to BHoM standards.

  private void RunScript(List<Point3d> x, ref object A)
  {

    //get ring of points
    List<Point3d> ringPoints = x;

    //join this ring up with nearest neighbours
    List<Point3d> sortedPoints = new List<Point3d>();


    //set up first item
    sortedPoints.Add(ringPoints[0]);
    ringPoints.RemoveAt(0);

    //now go through the ring points, finding nearest neighbours, and adding them
    int safety = 100; //safety not necessary if the loop below is well written!
    while(ringPoints.Count > 0)
    {
      Point3d np = NearestPoint(sortedPoints.Last(), ringPoints);
      sortedPoints.Add(np);
      ringPoints.Remove(np);
      //remember to remove a ringPoint for every loop!!
      safety--;
      if(safety < 0) break;
    }

    A = sortedPoints;



  }

  // <Custom additional code> 

  //finds the nearest point in a collection. Ignores itself if it finds itself.
  Point3d NearestPoint(Point3d pt, List<Point3d> comparisonpts)
  {
    double minDistance = Double.MaxValue;
    Point3d rtnpt = new Point3d();
    foreach (var cp in comparisonpts)
    {
      double dist = cp.DistanceTo(pt);
      if(dist == 0) continue;
      if(dist < minDistance)
      {
        minDistance = dist;
        rtnpt = cp;
      }
    }
    return rtnpt;
  }