How to find furthest point in list , C#

Grasshopper
, ,
1

Trying to make a slight modification to Peter’s C# code as posted here: Closest point | two lists of points - #11 by chris.pm that finds the closest points in a list.

Peter’s code snippet uses RhinoCommon functionality from the Point3dList class as [ClosestIndexInList ] and [ClosestPointInList]

for(int j = 0; j < N;j++){
      for(int i = 0; i < loops;i++){
        p2 = Point3dList.ClosestPointInList(List2C, p1);
        p1 = Point3dList.ClosestPointInList(List1C, p2);
      }
      pairTree.AddRange(new Point3d[2]{p1,p2}, new GH_Path(j));

      int pIndex1 = Point3dList.ClosestIndexInList(List1C, p1);
      int pIndex2 = Point3dList.ClosestIndexInList(List2C, p2);

      if(j == 0){
        indicesTree.AddRange(new int[2]{pIndex1,pIndex2}, new GH_Path(j));
      }
      else{
        if(Indices == 2){
          int pI1 = Point3dList.ClosestIndexInList(List1, p1);
          int pI2 = Point3dList.ClosestIndexInList(List2, p2);
          indicesTree.AddRange(new int[2]{pI1,pI2}, new GH_Path(j));
        }
      }

I want to modify it to find the furthest point (and it’s index). I can imaging iterating through all points and calculate the distances, something along the lines of this snippet below, but with many (100.000+) points in 2 lists this will probably be CPU intensive, and more importantly will probably result in same points lists as ‘farthest’ . Any suggestions for a method that extents peters’s solution (as i know that works)

for i in range(n):

        for j in range(i+1, n):
            distance = math.sqrt((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2)
            if distance > farthest_distance:
                farthest_distance = distance
                farthest_pair = (i, j)

    return farthest_distance, farthest_pair
2 
  private void RunScript(Point3d P, List<Point3d> Ps, ref object A, ref object B)
  {
    double cfd = 0.0; //furthest distance
    int idx = 0; //furthest index
    for(int i = 0;i < Ps.Count;i++)
    {
      double tmp = P.DistanceTo(Ps[i]);
      if(tmp > cfd)
      {
        idx = i;
        cfd = tmp;
      }
    }
    A = cfd;
    B = idx;
  }

EDIT: corrected, thanks to Farouk Serragedine

Indeed with 100k+ pts it will kill your pc for 3 days, if you do it with every point, so you absolutely need to cluster the points with some sort of k-means before doing the listing. This will significally decrease the calculation time, as you’ll limit the number to search. if you need to do it with one point only, k-means probably won’t help significally.

1 Like
3

Correcting the typo :
It should be i < Ps.Count instead of 0 < Ps.Count . As written, the loop will never execute because 0 < Ps.Count is always false, which means that cfd and idx will never be initialized or updated.

1 Like
4

thanks, didn’t catch that one

5

If this cloud of points exists within a convex hull, then you could probably eliminate many from the search by excluding those in the “core”.

6

@akilli Ah, nice trick. Though not applicable for now.

Like ben suggested, I indeed implement the K-means, to reduce the load.

@farouk.serragedine , @benedict Thanks guys, but am I missing something as I just get ‘null’s’ when I ran this? Types are set correctly. Mind sharing a .gh file

7

fp.gh (4.2 KB)

8

Thx. Made a stupid typo while copy/pasting