如何找到到给定点的最近点（点是（x，y），在不同点的列表中）？

Question

目前我有一个从随机生成的随机点。我正在尝试检查给定的随机点是否离平面中任何其他现有点太近，如果它离所有其他点足够远，它将被添加到其他点列表中。我从一个给定的点开始，列表中的第一个 hundered 点就是这样生成的。我的问题是，当我将列表中的所有点绘制到屏幕上时，这些点通常比允许的距离更近。

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

这样的事情怎么样？

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

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

Answer 3

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

但是你有一个更严重的问题。如果您的 OP 是正确的，那么您将尝试在屏幕上放置 100 个点，使得其中 none 个点之间的距离小于 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公式计算与您获得的新随机点的距离。

如何找到到给定点的最近点（点是（x，y），在不同点的列表中）？

How to find closest point (point being (x,y), in a list of different points) to a given point?

c#

random

distance

points