Точки фильтра XY по расстоянию с LINQ

Question

У меня есть список точек XY, и я хочу сгруппировать их на заданное расстояние, скажем, все точки, находящиеся на расстоянии x между ними, должны быть сгруппированы в другой список.

В принципе, если у меня есть A = (0,0), B = (0,1), C = (0,2), я хочу сгруппировать все точки с максимальным сопротивлением 1, чтобы получить: [[A, B], [C]];

Answer 1

Я действительно не понял ваш вопрос, поэтому я не совсем уверен, как вы хотите сделать группировку, но это может привести к тому, что вы в правильном направлении.

(Написано в VB, но почти идентичны в C# - Вы также не указать предпочитаемый язык):

Dim MyPoints As New List(Of Point) 

    MyPoints.Add(New Point(0, 0)) 
    MyPoints.Add(New Point(0, 1)) 
    MyPoints.Add(New Point(0, 2)) 

    Dim query = From pt1 In MyPoints 
       From pt2 In MyPoints 
       Where Not (pt1.Equals(pt2)) 
       Select New With {.pt1 = pt1, .pt2 = pt2, .dist = Math.Sqrt((pt1.X - pt2.X)^2 + (pt1.Y - pt2.Y)^2)} 

Answer 2

Что вы пытаетесь сделать, это назвали clustering, что означает, группируя набор данных (двухмерные точки в вашем случае) в набор групп с некоторыми характеристиками (заданное расстояние между точками). Я настоятельно рекомендую прочитать приведенную выше ссылку, чтобы лучше понять ее. Вы можете быть заинтересованы в двух типах кластеров:

• иерархическая кластеризация, который создает группы на основе расстояния связи,
• Центроиды, что создает группы «окружающие» центры групп

Все зависит от того, сколько данных у вас есть. Для небольших наборов вы можете попытаться реализовать некоторые простые алгоритмы самостоятельно. Для больших данных я бы предпочел использовать стороннюю библиотеку, такую ​​как Numl, которая содержит методы для обоих вышеперечисленных типов.

Вот пример кода кластеризации с использованием Numl. Данный класс:

class Point 
{ 
    [Feature] 
    public double X { get; set; } 
    [Feature] 
    public double Y { get; set; } 
    public Point(double X, double Y) 
    { 
     this.X = X; 
     this.Y = Y; 
    } 
    public override string ToString() 
    { 
     return string.Format("({0}; {1})", X, Y); 
    } 
} 

вы можете написать:

var model = new HClusterModel(); 
var desc = Descriptor.Create<Point>(); 
var linker = new CentroidLinker(new EuclidianDistance()); 
var data = new List<Point>() { new Point(0.0, 1.0), 
           new Point(0.0, 2.0), 
           new Point (10.0, 0.0) }; 
var result = model.Generate(desc, data, linker); 
foreach (var cluster in result.Children) 
{ 
    Console.WriteLine("Cluster:"); 
    Console.WriteLine(string.Join(", ", cluster.Members.OfType<Point>())); 
} 

, что приводит к:

Answer 3

У меня был удар в этом, хотя это, вероятно, не является фантастически эффективным способ сделать что-то; ссылка в ответе Конрада кажется хорошим местом для изучения.

Я не совсем уверен, как вы определяете «внутри диапазона», поэтому я принял простой расчет расстояния.

// Set up some points 
List<Point> Points = new List<Point>(); 

Points.Add(new Point(0, 0)); 
Points.Add(new Point(0, 1)); 
Points.Add(new Point(0, 2)); 

// Distance 
int maxDistance = 1; 

// Replace as appropriate 
Func<Point, Point, int, bool> myDistanceFunction = delegate(Point p1, Point p2, int range) 
{ 
    // Same coordinate. 
    if (p1 == p2) 
     return true; 

    int xDelta = p1.X - p2.X; 
    int yDelta = p1.Y - p2.Y; 

    double distance = Math.Sqrt(xDelta * xDelta + yDelta * yDelta); 

    return (distance <= range); 
}; 

// Loop through all points and calculate distance to all other points. 
var Results = Points.Select(firstPoint => new 
{ 
    TargetPoint = firstPoint, 
    PointsInRange = Points 
     .Where(secondPoint => 
      (secondPoint != firstPoint) && // Will you allow same coordinates? 
       myDistanceFunction(secondPoint, firstPoint, maxDistance)) 
}); 

// Spit the results out. 
foreach (var result in Results) 
{ 
    Console.WriteLine("Point {0} - Points within {1} unit(s):", result.TargetPoint, maxDistance); 

    foreach (var point in result.PointsInRange) 
    { 
     Console.WriteLine("\t{0}", point); 
    } 
} 

Выход:

Point {X=0,Y=0} - Points within 1 unit(s): 
     {X=0,Y=1} 
Point {X=0,Y=1} - Points within 1 unit(s): 
     {X=0,Y=0} 
     {X=0,Y=2} 
Point {X=0,Y=2} - Points within 1 unit(s): 
     {X=0,Y=1} 

Там место для улучшения, например, он не чувствует себя умным, чтобы вычислять расстояния для пар точек дважды, и я не, если вы позволите дублировать координаты, но там может быть что-то полезное.

Вы также можете написать функцию расстояния как выражение lamba, хотя я не уверен, что это яснее.

Func<Point, Point, int, bool> myDistanceFunction = 
(
    (p1, p2, range) => Math.Sqrt(
     ((p1.X - p2.X) * (p1.X - p2.X)) + 
     ((p1.Y - p2.Y) * (p1.Y - p2.Y)) 
    ) <= range 
); 

Answer 4

К сожалению для всех, я сделал пост не очень понятно, в основном им с помощью C# и я исключал кластеризацию для конкретной цели, скажем, у меня есть некоторые моменты, и их идентификаторы и мне нужно «рассортируйте их», сохраняя информацию о ids, затем просто сделал среднюю точку на оси X, cos im заинтересован только в группировке по этому атрибуту позиции.

В конце точки не более 10, а информация об идентификаторах очень важна для того, чтобы знать, кто есть, поэтому я решил собрать идентификаторы точек достаточно близко, а затем использовать список перечней координат для определения результатов , сделал это очень сырой, потому им в спешке, но полностью открыт для дальнейшей реализации, просто им не в состоянии использовать LINQ :)

Так что я использовал что-то вроде этого:

// class to hold information 

public class userObject{ 

     public string id; 
     public Vector3D position=Vector3D.Zero; 

     public userObject(string Id, Vector3D Position){ 

      id=Id; 
      position=Position; 


     } 
    } 

    // list of grouped ids (nanocluster :) 

    public Dictionary<int, List<userObject>> slots ; 



    private void forceCheck(){ 



     // create list of object from incoming coordinates (ids and point vector3d) 

     List<userObject> users=new List<userObject>(); 

     for(int a=0;a<FId_In.SliceCount;a++){ 

      userObject uo=new userObject(FId_In[a],FPositions_In[a]); 

      users.Add(uo); 
     } 



     // Clean result, this is different in another version im working on 



     slots =new Dictionary<int,List<userObject>>(); 


     // check for close points (a couple of lines should be changed to achieve a real clustring, but this way i can control all points will not create an horizontal cluster, told u raw mode on 

     for(int k=0;k<users.Count;k++){ 

      List<userObject> matches=new List<userObject>(); 


      // Check if ids is already registered in one slot 
      int isInSlot=checkIdInSlots(users[k].id); 



      if(isInSlot==-1){ 

       matches.Add(users[k]); 

       for(int j=k+1;j<users.Count;j++){ 




      // call a function to check x distance, but can use full vector3d when needed 

      if(checkClose(users[k].position,users[j].position,FXThreshold_In[0])){  


         matches.Add(users[j]); 

        } 


       } 



      // finally add entry with grouped ids....sure all this is a line of linq :D 

       addNewSlot(matches); 

      } 




     } 


    } 

было бы неплохо лучше понять, как linq может быть использован для достижения такого же результата, уверен, что он может быть более надежным, спасибо вам всем :)