如何找到距离给定点最近的点（点为（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());
    }

编辑：要明确的是，它们可以有多接近的数字只是我在那里抛出的一个数字（目前）它可以是任何>~30

Edit2：将所有元组更改为Vector2并使用建议的代码，仍然没有改变问题

编辑 3：使用 for 循环遍历所有点（在 while 循环内部）并使用 break 似乎已经解决了问题。

Answer 1

这应该做： （要求您删除所有元组并将它们替换为 Vector2 类型，这通常更有意义。您还想调整您的命名。

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

Answer 2

您似乎希望它相当快，因为这是一个相当慢的算法（我认为是 O(N^2)）。一个明显的优化是只计算距离平方并用它来比较距离 - 这消除了平方根运算。

但是你有一个更严重的问题。如果你的操作是正确的，那么你正在尝试在屏幕上放置 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 3

您可以迭代平面中的点，并使用this公式来计算与您获得的新随机点的距离。

Answer 4

这样的事情怎么样？

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);
}

只需将 Point 类更改为您的元组或您正在使用的任何内容

Answer 5

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

这是基于此时的最佳答案，但将返回最近的点而不是最远的点（如方法名称所示）。 :-)