Как найти ближайшую точку (точку (x, y), в списке разных точек) до заданной точки?

Question

В настоящее время у меня есть случайная точка, создаваемая из Random. Я пытаюсь проверить, является ли данная случайная точка слишком близкой к любым другим существующим точкам на плоскости, если она находится достаточно далеко от ВСЕХ других точек, она будет добавлена ​​в список других точек. Я начинаю с одной заданной точки, и первые измеченные точки в списке генерируются таким образом. Моя проблема заключается в том, что когда я иду, чтобы нарисовать все точки в списке на экране, часто точки намного ближе, чем им должно быть позволено.

public void generateFirstMap() 
    { 
     int count = 0; 
     do 
     { 
      int randXpixels = Main.rand.Next(24, Main.screenWidth - 16); //leave outer 16 pixels of screen empty (planet sprite has diameter of 8 pixels) 
      int randYpixels = Main.rand.Next(27, Main.screenHeight - 27); 
      Tuple<int, int> coord = Tuple.Create(randXpixels, randYpixels); 
      if (distance(closestPoint(coord), coord) < 200) 
      { 
       continue; 
      } 
      points.Add(coord); //List<Tuple<int,int>> points; 

      count++; 
     } while(count < 100); 


public Tuple<int, int> closestPoint (Tuple<int, int> p1) 
    { 
     Tuple<int, int> p2 = Tuple.Create(0, 0); 
     bool firstRun = true; 
      foreach (Tuple<int, int> point in points) 
      { 
       if (firstRun) 
       { 
        p2 = point; 
        firstRun = false; 
       } 
       else if (distance(p1, p2) < distance(p1, point)) 
       { 
        p2 = point; 
       } 
      } 
      return p2; 
    } 

public double distance(Tuple<int, int> p1, Tuple<int, int> p2) 
    { 
     Vector2 line = new Vector2((p2.Item1 - p1.Item1), (p2.Item2 - p1.Item2)); 
     return Math.Abs(line.Length()); 
    } 

Edit: быть ясно, число для того, как близко они могут быть просто номер, я бросил там (сейчас) это может быть что угодно> ~ 30

Edit2: Изменены все кортежи Vector2 и используемый предложенный код, все еще не изменили проблему

Редактирование 3: Использование цикла for для циклического перемещения по всем точкам (внутри циклов while) и с использованием прерывания, похоже, устранило проблему.

Answer 1

Что о чем-то.. как это?

public void generateFirstMap() 
{ 
    int count = 0; 
    do 
    { 
     bool addPoint = true; 
     int randXpixels = Main.rand.Next(24, Main.screenWidth - 16); 
     int randYpixels = Main.rand.Next(27, Main.screenHeight - 27); 
     for (int a = 0; a < points.Count; a++) 
     { 
      int dX = randXpixels - points[a].X; 
      int dY = randYpixels - points[a].Y; 
      if (dX * dX + dY * dY < 200) 
      { 
       addPoint = false; 
       break; 
      } 
     } 
     if(addPoint) 
      points.Add(new Point(randXpixels,randYpixels)); 

     count++; 
    } while (count < 100); 
} 

Просто измените класс точки на ваш кортеж или что вы используете

Answer 2

Это должно сделать: (Требуется вам удалить Alls кортежей и заменить их типа Vector2, что делает гораздо больше смысла в целом Кроме того, вы хотите настроить именование

public Vector2 GetClosestPoint (Vector2 v1) 
{ 
    return points.OrderByDescending(v2 => GetDistance(v1,v2)).First(); 
} 

Answer 3

Похоже, вы хотели бы, чтобы это было фай rly быстро, потому что это довольно медленный алгоритм (я думаю, O (N^2)). Очевидная оптимизация заключается в том, чтобы просто вычислить квадрат расстояния и использовать его для сравнения расстояний - это устраняет операцию с квадратным корнем.

Однако у вас есть гораздо более серьезная проблема. Если ваш OP правильный, то вы пытаетесь разместить 100 точек на экране, чтобы ни один из них не был ближе, чем на 200 пикселей друг от друга. Это вряд ли произойдет с случайно выбранными точками, потому что есть вероятность, что они произойдут в таких позициях, что после того, как номер был помещен, просто нет места для больше.

В любом случае, вот какой-то код, который попытается вычислить баллы - но он никогда не закончится, потому что точки не подойдут, если вы не сделаете экран ОЧЕНЬ большим. Попробуйте запустить его с разными семенами для конструктора Random() и посмотреть, что произойдет.

using System; 
using System.Collections.Generic; 
using System.Drawing; 

namespace ConsoleApplication2 
{ 
    class Program 
    { 
     private static void Main() 
     { 
      var points = new List<Point>(); 

      int screenWidth  = 1920; 
      int screenHeight = 1280; 
      int numPointsWanted = 100; 

      long nearestAllowedSquared = 200*200; 

      Random rng = new Random(12345); 

      while (points.Count < numPointsWanted) 
      { 
       int randXpixels = rng.Next(24, screenWidth - 16); 
       int randYpixels = rng.Next(27, screenHeight - 27); 
       var point = new Point(randXpixels, randYpixels); 

       if (distanceToNearestPointSquared(point, points) >= nearestAllowedSquared) 
       { 
        points.Add(point); 
        Console.WriteLine(points.Count); 
       } 
      } 
     } 

     private static long distanceToNearestPointSquared(Point point, IEnumerable<Point> points) 
     { 
      long nearestDistanceSquared = long.MaxValue; 

      foreach (var p in points) 
      { 
       int dx = p.X - point.X; 
       int dy = p.Y - point.Y; 

       long distanceSquared = dx*dx + dy*dy; 

       nearestDistanceSquared = Math.Min(nearestDistanceSquared, distanceSquared); 
      } 

      return nearestDistanceSquared; 
     } 
    } 
} 

Answer 4

Вы можете перебирать точки на плоскости и использовать this формулы для вычисления расстояния с новой случайной точкой вы получите.