title: Generating points in area with at least X gap length in-between
body: <p>I am trying to come up with a method for generating X amount of random points in a given area (in my case a square). The one thing that makes this such an issue is that each point has to be at least Y units away from all other points.</p>
  
  <p>What springs to mind at first is (in c#) to check the distance between the new point and all existing points:</p>
  
  <pre><code>while(points.Count &lt; pointsToGenerate)
  {
       Point newPoint = NewPoint();
       bool addPoint = true;
       foreach(Point p in points)
       {
            if((p - newPoint).Length() &lt; minDistance)
            {
                addPoint = false;
                break;
            }
       }
  
       if(addPoint)
       {
            points.Add(newPoint);
       }
  }
  </code></pre>
  
  <p>Now this would certainly work however if no valid points were ever found this would become a never ending loop. So throw in a magical number Z there as a limit of tries?</p>
  
  <pre><code>if(loopCount &gt; 100)
  {
       break;
  }
  </code></pre>
  
  <p>Now this has some obvious problems. If the points are randomly generated, then loopCount can go above Z even if there are places left to place the point. It not only can, but it will happen!</p>
  
  <p>What I could do is to create a list of available point per each pass and then select a random one of those. This would work flawlessly except for one thing: Performance. I'm not in need of super performance in my application, but the area is 1000^2. A lot of points to check per pass even if I limit myself to integers!</p>
  
  <p>So, what I can come up with might not suffice, thus I would love some assistance on this. Is there a better way to generate X points in an area A with the minimum distance between points Y?</p>
  
  <p>Thanks!</p>
  
  <p><strong>EDIT:</strong> With better, I mean generally better where a balance of performance vs perfection is achieved. A bit vague, I know. I'm not entierly sure how much overhead I can have for generating those points yet so I'm basically after anything more elegant than my own method.</p>
  
  <p>~Robert</p>