C# - создание групп точек

Question

Как создать то, что принимает одну точку и список всех точек и возвращает список точек, которые достаточно близки к исходной точке или к достаточно близкой точке.

Если вы до сих пор не может понять меня вот картина:

Я пробовал:

int range = 6; 
    public List<IntPoint> getClosePoints(ref Dictionary<IntPoint,bool> allPoints,IntPoint startingPoint) { 
     List<IntPoint> closePoints = new List<IntPoint>(); 
     closePoints.Add(startingPoint); 
     bool gotBigger = true; 

     while (gotBigger) { 
      gotBigger = false; 
      foreach (IntPoint proven in closePoints.ToList()) { 
       foreach (IntPoint possible in allPoints.Keys.ToList()) { 
        if (isInRange(proven,possible,range) && !allPoints[possible]) { 
         gotBigger = true; 
         closePoints.Add(possible); 
         allPoints[possible] = true; 
        } 
       } 
      } 
     } 
     return closePoints; 
    } 

    public bool isInRange(IntPoint A, IntPoint B, int range){ 
     if(A.DistanceTo(B) < range) 
      return true; 
     return false; 
    } 

(IntPoint является похож на Point, это от AForge, все очки имеют bool значение false) Но это делает мою программу супер-лаги, учитывая, что она называется тысячей раз в цикле. :/(А также, кажется, не работать)

Answer 1

попробовать это:

public IEnumerable<Point> GetPoints(Point origin, IEnumerable<Point> points, int distance) 
{ 
    var result = new HashSet<Point>(); 
    var found = new Queue<Point>(); 
    found.Enqueue(origin) 

    while(found.Count > 0) 
    { 
     var current = found.Dequeue(); 
     var candidates = points 
      .Where(p => !result.Contains(p) && 
        p.Distance(current) <= distance); 

     foreach(var p in candidates) 
     { 
      result.Add(p); 
      found.Enqueue(p) 
     } 
    } 

    return result; 
} 

я думаю, что это прямо вперед достаточно, в любом случае функция HashSet является то, что он может сказать, если он содержит элемент в ближайшем O (1).

Answer 2

Это проблема кластеризации. В простых шагах,

1. Получите все точки, близкие к вашим входным точкам;
2. Добавьте все пункты, возможно, Hashset;
3. Теперь поместите все точки в вашем Hashset в очередь и перейдите к шагу 1.
4. Перерыв, когда ваш Hashset аналогичен предыдущей итерации. Вы нашли все правильные моменты.