Создание точек в области с длиной промежутка не менее X

Question

Я пытаюсь придумать метод для генерации X количества случайных точек в данной области (в моем случае это квадрат). Единственное, что делает эту проблему такой, заключается в том, что каждая точка должна находиться на расстоянии не менее Y единиц от всех остальных точек.

Сначала на ум приходит (в c #) проверить расстояние между новой точкой и всеми существующими точками:

while(points.Count < pointsToGenerate)
{
     Point newPoint = NewPoint();
     bool addPoint = true;
     foreach(Point p in points)
     {
          if((p - newPoint).Length() < minDistance)
          {
              addPoint = false;
              break;
          }
     }

     if(addPoint)
     {
          points.Add(newPoint);
     }
}

Теперь это, безусловно, сработает, однако, если не будет найдено действительных точек, это станет бесконечным циклом. Так брось там магическое число Z как предел попыток?

if(loopCount > 100)
{
     break;
}

Теперь у этого есть некоторые очевидные проблемы. Если точки генерируются случайным образом, то loopCount может идти выше Z, даже если есть места, где можно разместить точку. Это не только может, но и случится!

Что я мог сделать, это создать список доступных точек для каждого прохода, а затем выбрать случайный из них. Это будет работать безупречно, за исключением одного: производительность. Мне не нужна супер производительность в моем приложении, но область составляет 1000 ^ 2. Много точек для проверки за проход, даже если я ограничусь целыми числами!

Итак, то, что я могу придумать, может оказаться недостаточным, поэтому я хотел бы получить некоторую помощь в этом. Есть ли лучший способ создать точки X в области A с минимальным расстоянием между точками Y?

Спасибо!

РЕДАКТИРОВАТЬ: Под лучшим, я имею в виду лучше, когда достигается баланс производительности и совершенства. Немного расплывчато, я знаю. Я не совсем уверен, сколько я могу потратить на создание этих очков, поэтому я в основном стремлюсь к чему-то более элегантному, чем мой собственный метод.

~ Роберт

Answer 1

Чтобы понять вашу проблему: вы ищете оптимальный ответ (т.е. домашнее задание) или очень хороший алгоритм, который лучше, чем создание случайных точек?

В первом случае, боюсь, это очень сложная проблема, если у вас нет предварительной информации по области А. И я считаю, что будет трудно найти алгоритм, который быстрее, чем изучение каждого отдельного случая. .

Однако, если у вас есть некоторая предварительная информация об А, тогда все может быть проще. Например, , если оно выпуклое , вы можете использовать тот факт, что оптимальный тротуар, если ваше пространство бесконечно, является шестиугольным . Это означает, что вы должны поставить свои точки (в X) на концах треугольников

Итак:

• вычислить выпуклую оболочку (O (n * log (n)))
• вычислить диаметр (две самые дальние точки вашего набора)
• начать с добавления к X одной из точек (диаметра)
• затем добавьте точки, которые соответствуют шестиугольному тротуару, отдав предпочтение точкам на выпуклой оболочке

Этот алгоритм не является оптимальным (если только вы не определили очень хорошее "одобрение для выпуклых оболочек" ...)

---

Редактировать: комментарий г-на Е. напомнил мне, что оптимальная вещь для дорожного покрытия основана на круговой упаковке . Слава ему за точность!

---

Тем не менее, У меня есть другой алгоритм, который выглядит очень красиво и, возможно, даже оптимально! Он не требует каких-либо условий на A и стоит немного дороже, но не слишком много. Да, я знаю, это противоречит тому, что я сказал, но кого это волнует! Хороший алгоритм достаточно хорош.

Давайте назовем B набор доступных точек на данный момент. И C - точки, образующие конечности B. В начале B = A, и если A - квадрат, то C состоит из 4 точек (углов). Вы просто должны рекурсивно:

• вычислите две самые дальние точки B. Для этого вам нужны только точки в C
• добавить к X одну из точек (диаметра) случайным образом
• уберите из B точки, которые сейчас недоступны. Вам нужно только обновить C для этого.

Я знаю, что если вы работаете в сетке 1000x1000, C начинается с 4 точек, но после добавления одной точки к X это означает, что C возрастает до 1570 пунктов (примерно (pi / 2) 1000). Вы должны заметить, что вы никогда не помещаете в память B, которая является большой (O (n ^ 2), если A может быть помещена в сетку n) Только C, и я считаю, что в любой момент размер C является O (n), который остается намного лучше, чем O (n ^ 2). И вычисление диаметра остается O (размер (C)) = O (n)

Answer 2

Вот мои мысли, я думаю, что вы должны разделить область на квадраты с длиной стороны, равной Y. После этого у вас могут остаться прямоугольники с одной из сторон меньше, чем у, если только область = целое число * y2. Теперь максимальное количество очков, которое вы можете сгенерировать, равно числу квадратов + прямоугольников.Поэтому, если X больше этого, вы можете завершить метод с ошибкой.

Чтобы начать генерировать точки, начните с последнего (нижнего правого) наименьшего прямоугольника.Выберите там случайную точку и найдите точку в ее верхнем и левом прямоугольниках так, чтобы они находились на расстоянии Y от первой точки, и начните заполнять точку в прямоугольнике / квадрате, только если ее непосредственный правый и ближайший нижний квадрат / прямоугольникзаполнены.Следовательно, вы заполняете первый квадрат в конце.

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

Чтобы сделать вещи более случайными, вы можете начать погружение в квадраты стороны Y с любого из четырехсторон, (здесь это было вверху слева), так что начальная точка каждый раз отличается.

Answer 3

Если вы хотите случайное распределение, вы можете ответить на вопрос «Есть ли точка, расположенная на расстоянии менее y от этой точки» за O (1) время, разделив вашу сетку на ячейки размера y. Тогда любая точка P, находящаяся на расстоянии менее y от другой точки Q, должна находиться в одной из 9 ячеек, соседних с ячейкой Q, и поэтому вы можете просто использовать хеш-таблицу и выполнить 9 проверок. Кроме того, каждая ячейка может содержать не более 2 точек.

С такой структурой данных вы можете затем сделать случайную выборку с отклонением, чтобы заполнить ваше пространство. Пока у относительно мало по сравнению с общей площадью, вы быстро добьетесь успеха.

Answer 4

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

PointsRemaining = X
Points = new CoordinateCollection
Width = 1000
Height = 1000
if (Width > Hight)
    Swap(Width, Hight)
    Swapped = true
NumberOfLocationsAvailable = new int[Width]
InitializeArrayValues(NumberOfLocationsAvailable, Height)
TotalLocationsAvailable = Width * Height
While (TotalLocationsAvailable > 0 and PointsRemaining > 0)
    NextPoint = Random(0, TotalLocationsAvailable)
    NextCoordinates = FindCoordinates(NextPoint, NumberOfLocationsAvailable)
    NumberLocationsRemoved = RemoveLocationsWithinDistance(NextCoordinates, Points, NumberOfLocationsAvailable, Y)
    TotalLocationsAvailable = TotalLocationsAvailable - NumberLocationsRemoved
    Points.Add(NextCoordinates)
    PointsRemaining = PointsRemaining - 1
if (Swapped)
    Points = RotatePoints(Points)

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

Answer 5

Вы можете использовать метод молекулярной динамики .

Начните с большой коробки и разбросайте свои точки по ней на некоторой регулярной сетке с интервалом> Y.

Теперь обработайте каждую точку как сферическую частицу, которая взаимодействует с другими точками через некоторый отталкивающий потенциал, такой как отталкивающий Леннард-Джонс, с параметрами, выбранными так, чтобы эффективный диаметр каждой частицы был Y.

Дайте частицам случайный характерскорости, и решить уравнения движения с помощью дискретного решателя (скажем, скорость-Верле, это не должно быть точным).Отталкивание между частицами будет держать частицы Y отдельно.По мере того, как вы обновляете позиции частиц, каждый раз немного уменьшайте размер окна, пока не получите нужный размер.(О, коробка может быть обработана с периодическими граничными условиями или коротким отталкивающим полем.)

Конечно, вы должны быть уверены, что вы можете поместить все свои частицы вкоробка.В 2D известна оптимальная упаковка окружностей, см. Задачу Кеплера.Разве я не слышал, что проблема 3D Kepler теперь тоже решена?