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

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

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

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

So :

• вычислить выпуклую оболочку (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 (size (C)) = O (n)

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

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

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

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

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

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.

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

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

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

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

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

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

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