java如何在2D平面上随机生成一组站点，这些站点之间的空间大致相同？

Question

我使用JavaFX来显示站点，但您不需要理解JavaFX来回答我的问题。我想包括一个完整的工作代码示例，这样您就可以自己运行它了。但是，为了帮助我，您可能只需要查看示例底部的randomlyChooseSites()方法

在这段代码中，我在二维平面上生成了一组随机点。我希望他们在距离上更加平等，而不是在距离上完全平等

如何在二维平面上随机生成点，并使它们之间的距离比现在更接近相等，而不是距离完全相等

public class MCVE extends Application {

private final static int WIDTH = 400;
private final static int HEIGHT = 500;

private final static int AMOUNT_OF_SITES = 50;

private final static SplittableRandom RANDOM = new SplittableRandom();

@Override
public void start(Stage primaryStage) {

   // Create the canvas
   Canvas canvas = new Canvas(WIDTH, HEIGHT);
   GraphicsContext gc = canvas.getGraphicsContext2D();
   drawShapes(gc);

   // Add the canvas to the window
   Group root = new Group();
   root.getChildren().add(canvas);
   primaryStage.setScene(new Scene(root));

   // Show the window
   primaryStage.setTitle("Sweep-Line Test");
   primaryStage.show();
}

/**
 * Draws shapes on the Canvas object.
 *
 * @param gc
 */
private void drawShapes(GraphicsContext gc) {

   gc.setFill(Color.BLACK); // sites should be black

   // create random sites
   ArrayList<int[]> siteSet = randomlyChooseSites();

   // add the random sites to the displayed window
   for(int[] i : siteSet) {
      gc.fillRect(i[0], i[1], 5, 5);
   }

}

/**
 * Randomly chooses sites and returns them in a ArrayList
 * @return
 */
private ArrayList<int[]> randomlyChooseSites() {
   // create an ArrayList to hold the sites as two-value int[] arrays.
   ArrayList<int[]> siteList = new ArrayList<>();

   int[] point; // holds x and y coordinates
   for(int i = 0; i < AMOUNT_OF_SITES; i++) {
      // randomly choose the coordinates and add them to the HashSet
      point = new int[] {RANDOM.split().nextInt(WIDTH), RANDOM.split().nextInt(HEIGHT)};
      siteList.add(point);
   }

   return siteList;
}

}

Answer 1

（事实上，更准确地表达问题有助于找到答案。）

如果要查找相邻点（沿每个轴）之间相同的平均距离，则这是一种可能的解决方案。：

对于这个解决方案，把平面分成大小相等的矩形，每个矩形包含一个点。 在矩形中随机放置点，并对所有矩形执行此操作。 那么所有相邻点之间的平均距离将是相同的。。。沿着每个轴

我使用了一个完美的正方形网格，两边都一样。然后找到适合该数量站点的最小完美方形网格，并删除角落中的额外区域。（对于50个站点，它是8x8（64））

修改RandomlyChoosSites函数，如下所示：

private ArrayList<int[]> randomlyChooseSites() {
    // create a HashSet to hold the sites as two-value int[] arrays.
    ArrayList<int[]> siteList = new ArrayList<>();

    class SiteArea
    {
        boolean is_used; // if false, ignore this area (and the point in it)

        int point_x; // absolute coordinates of point generated in this area
        int point_y;
    }

    int gridsize = (int)Math.ceil (Math.sqrt (AMOUNT_OF_SITES));
    int empty_areas = gridsize * gridsize - AMOUNT_OF_SITES; // we want the empty areas in the corners

    int area_size_x = WIDTH / gridsize;
    int area_size_y = HEIGHT / gridsize;

    SiteArea areas[][] = new SiteArea [gridsize][gridsize];

    // initialize all areas on the grid
    for (int i = 0, imax = gridsize * gridsize; i < imax; i++)
    {
        int x_ = (i % gridsize), x = x_ * area_size_x;
        int y_ = (i / gridsize), y = y_ * area_size_y;

        SiteArea a = areas[x_][y_] = new SiteArea ();
        a.is_used = true; // set all areas as used initially

        // generate the point somewhere within this area
        a.point_x = x + RANDOM.split().nextInt(area_size_x);
        a.point_y = y + RANDOM.split().nextInt(area_size_y);

        // to see the grid, create a drawRect() function that draws an un-filled rectangle on gc, with the other params being: top left corner x, y and rectangle width, height
        //drawRect (gc, x, y, area_size_x, area_size_y);
    }

    // disable some of the areas in case if the grid has more rectangles than AMOUNT_OF_SITES
    // cut away at the four corners, by setting those areas to is_used = false
    class Corner { int x; int y; int xdir; int ydir; Corner (int a,int b,int c,int d) { x=a;y=b;xdir=c;ydir=d; } }
    int z = gridsize-1; Corner corners[] = { new Corner (0,0,1,1), new Corner (z,0,-1,1), new Corner (0,z,1,-1), new Corner (z,z,-1,-1) };
    for (int i = 0, imax = empty_areas; i < imax; i++)
    {
        Corner c = corners[i % 4]; // cycle over the corners
        int x = c.x, y = c.y, offset = (i + 4) / 8, xo = offset, yo = offset;
        if (i % 8 > 3)
        {   // cut x
            xo = 0;
        }
        else
        {   // cut y
            yo = 0;
        }
        areas[x + xo * c.xdir][y + yo * c.ydir].is_used = false;
    }

    // export the generated points to siteList
    for (int i = 0, imax = gridsize * gridsize; i < imax; i++)
    {
        int x_ = (i % gridsize);
        int y_ = (i / gridsize);
        SiteArea a = areas[x_][y_];
        if (a.is_used)
        {
            siteList.add (new int[] { a.point_x, a.point_y });
        }
    }



    return siteList;
}

有些点将非常接近，这可以通过添加更改以生成更靠近每个矩形中心的点来避免

Answer 2

好的算法应该是Poisson disk sampling

Robert Bridson这一算法的变体广泛可用，看看here，我觉得还可以