Sorting points by coordinates

benoitlahoz's picture

Hi !

I guess I have posted yet a question quite similar in another topic. But I still have the same trouble...

I would like to sort a stfucture of points so I can have a coherent shape at the end. I can't manage to do this. I tried to implement a connected component algorithm but it is terribly slow...

Does anybody have an idea ?

Thanks !

usefuldesign.au's picture
Re: Sorting points by coordinates

Sort patch? I guess you're looking for something more sophisticated… what do you want to sort by if not X, Y, or Z?

I've filtered a point structures to highlight only those points within a certain distance of currently selected point so I can jump to them with keystrokes. For small number of points <200 it's instantaneous from what I remember (I think I did it in JS patch).

benoitlahoz's picture
Re: Sorting points by coordinates

Thanks Alastair for your answer.

I would like to have a kind of blob of an openCL structure of points. My OpenCL kernel treats the points before by width then by height, so my structure is sorted the same way.

In my plugin I sorted my points before by Y then by X ("connected components brute force method") but it is very slow and I guess there is a better way to do this... but I'm not skilled at this work...

I have around a hundred of points and I woud be very very very happy to see your JS patch ! :-D

usefuldesign.au's picture
Re: Sorting points by coordinates

Will dig it out tonight if I can. OpenCL — not my department… haha

benoitlahoz's picture
Re: Sorting points by coordinates

:-D Thanks !

usefuldesign.au's picture
Re: Sorting points by coordinates

Okay I don't want to post the whole comp, partly because I used it make my avatar id image and partly because I can't find a fully functional file… dozens of iterations and all are only partially function in one area.

I have 286 points in my Geodesic dome (thanks Tangible Interactive for the data set). The javascript that selects the nearest points to any given point (inside a numeric limit) works as fast as my comp does anyway, about 14fps. This is the script:

function (__structure points_in_range,  __number _length,
 __number point_index, __structure sampler) 
main (__structure point_struct, __number total_points,
 __index point_A, __index point_B, __number cut_off)
{
   var result = new Object();
   var dist = new Number();
   var points = new Array();
   points = point_struct;
   var set = new Array();
 
   if (!_testMode)
   {
//      Co-ordinates for the point we are measuring distance from.
      sample = points[point_A];
      result.sampler = sample;
      close_point_no = 0;
      var point_no = sample.point_no *1.;  
      Px = sample.X * 1.;
      Py = sample.Y * 1.;
      Pz = sample.Z * 1.;
//   Find the close by points inside cut-off distance and 
//   assign to a struct called set
      for (d=0; d<total_points; d++)
      {
         if (d == point_A) continue
         sample = points[d];
         Bx = sample.X ;
         By = sample.Y ;
         Bz = sample.Z ;
//   Send differnce in 3 axses for calculation of distance
         dist = distance ((Bx - Px) , (By - Py) , (Bz - Pz));
         if (dist <= cut_off) {
            set[close_point_no] = sample;
            close_point_no++
            }
      }
      result.points_in_range = set;
      result._length = dist;
   }
 
 
//   result.points_in_range = 0 ;
   return result;
}
 
function distance (dX, dY, dZ)
{
   return Math.sqrt( dX*dX + dY*dY + dZ*dZ)
}

The other script I'll post compares all the points with each other and plots chords between points that have a distance that falls inside a user definable range.

function (__structure Chords, __number _length, __structure sampler) 
main (__structure point_struct, __number total_points, __number cut_off_low, __number cut_off_high)
{
   var result = new Object();
   var dist = new Number();
   var set = new Array();
 
   if (!_testMode)
   {
//      Co-ordinates for the point we are measuring distance from.
      counter = 0;
//   Find the close by points inside cut-off distance and 
//   assign to a struct called set
      var P = new Object();
      var B = new Object();
      var counter = new Number();
      P = point_struct [54];
      B = point_struct [56];
      for (i=0; i<total_points; i++)
      {
         P = point_struct [i];
         for (j=i; j<total_points; j++)
         {
            B = point_struct [j];
//   Compare distance to cut-off to get neighbooring nodes.
            dist = distance ((B.X - P.X) , (B.Y - P.Y) , (B.Z - P.Z));
            if (dist > cut_off_low & dist < cut_off_high)
            {
               set[counter++] = P;
               set[counter++] = B;
            }
         }
      }
      result.sampler = P;
      result.Chords = set;
      result._length = counter;
   }
 
 
   return result;
}
 
function distance (dX, dY, dZ)
{
   return Math.sqrt( dX*dX + dY*dY + dZ*dZ)
} 

I probably should have passed 2 point vectors to the distance function not 3 scalars as result of subtractions but you can fix-up the niceties. I wrote this when I was struggling with JS patch parsing error concepts in QC. The second script takes a second to re-evaluate when you change one of the inputs on my old clunker (dual G5 PPC). OpenCL would tear this up in less than the blink of an eye for thousands of points I imagine.

benoitlahoz's picture
Re: Sorting points by coordinates

Thank you so much Alastair !

What a deep work.

I'll try to tinker with the second one especially. It will be very useful for me !!!

I'll post the results (if there are).