Как случайным образом сгенерировать группу сайтов на 2D плоскости, которые имеют примерно одинаковое количество пространства между ними?

Question

Я использую JavaFX для отображения сайтов, но вам не нужно понимать JavaFX, чтобы ответить на мой вопрос. Я хотел включить полный рабочий пример кода, чтобы вы могли запустить его самостоятельно. Однако, чтобы выручить меня, вам, вероятно, нужно взглянуть только на метод randomlyChooseSites() внизу моего примера.

В этом коде я генерирую группу случайных точек на 2D-плоскости. Я хотел бы, чтобы они были более равными по расстоянию друг от друга, но не были бы идеально равными по расстоянию.

Как я могу случайным образом генерировать точки на 2D-плоскости и сделать так, чтобы они были ближе к равному на расстоянии друг от друга, чем сейчас, без того, чтобы идеально было равно по расстоянию?

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

Хорошим алгоритмом для использования будет Выборка диска Пуассона .

Вариант этого алгоритма Роберта Бридсона широко доступен, посмотрите здесь , выглядит нормальномне

Answer 2

(На самом деле, более точное выражение вопроса поможет вам найти ответ.)

Это возможное решение, если вы ищете одинаковое среднее расстояние между соседними точками (вдоль каждой оси) :

Таким образом, для этого решения разделите плоскость на прямоугольники одинакового размера, каждый из которых будет содержать одну точку. Поместите точку случайным образом в прямоугольник и сделайте это для всех прямоугольников. Тогда среднее расстояние между всеми соседними точками будет одинаковым ... вдоль каждой оси.

Я использовал идеальную квадратную сетку, с обеих сторон одинаковые. Затем найдите наименьшую идеальную квадратную сетку, которая будет соответствовать этому количеству сайтов, и удалите лишние области в углах. (Для 50 сайтов это 8х8 (64)).

Измените функцию randomlyChooseSites следующим образом:

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

Некоторые точки будут очень близки, этого можно избежать, добавив изменение, чтобы генерировать точки ближе к центру каждого прямоугольника.