Search code examples
c#randomdistancepoints

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


Currently I have a random point being generated from Random. I am trying to check if the given random point is too close to any other existing points in the plane, if it is far enough away from ALL other points, it will be added to the list of other points. I start with one given point and the first hundered points in the list are being generated this way. My problem is, when I go to draw all the points on the list onto the screen, often the points are much closer than they should be allowed to be.

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: to be clear, the number for how close they can be is just a number I threw out there (for now) it can be anything >~30

Edit2: Changed all tuples to Vector2 and used suggested code, still hasn't changed the problem

Edit 3: Using a for loop to loop through all the points (inside of the while loops) and using break seems to have fixed the problem.


Solution

  • What about something like this?

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

    Just change the Point class to your tuple or whatever you are using