Имеется параллелепипед со сторонами A, B, C и заданное количество точек k. Требуется расположить точки внутри параллелепипеда так, чтобы максимизировать минимальное расстояние между парами соседних точкек. Поясню для чего это нужно. Допустим я хочу нарисовать круговую диаграмму или например расставить разноцветные маркеры на карте. Для лёгкости восприятия нужно будет подбирать заданное количество максимально различимых цветов. На геймдеве нашёл такой совет: Отсюда и вытекает сабж. Решается ли такое за конечное приемлемое время? Если да, то какими методами (киньте ссылкой).
murder, если мы ищем самое оптимальное решение при изначально фиксированном k, то сложность этой задачи скорее всего будет NP. Наиболее эффективный для практического применения может быть такой вариант: взять гексагональную упаковку шаров, выбрать такой шаг между ними, чтобы требуемое количество влезало в параллелепипед, двигать и вращать параллелепипед относительно шаров чтобы можно было чуть увеличить размер шариков или запихать еще несколько штук. Хотя скорее всего оптимальным будет разместить слои шаров параллельно одной из граней, нужно будет только выбрать относительно какой. https://ru.wikipedia.org/wiki/Плотная_упаковка_равных_сфер Судя по картинке параллельно одной из граней получается при гексагональной упаковке, при кубической будет параллельно граням тетраэдра вписанного в куб, но в любом случае вычислить количество шаров можно будет только после того, как определимся с их раскладкой.
Black_mirror, Круто - похоже на то, что нужно. Очевидно параллельно самой большой по площади. Пошёл медитировать. UbIvItS, нет MIN=min(d(x,y),d(x,z),d(zy)). В моём представлении максимум этой функции даст палитру наиболее различимых оттенков цвета. Может я и не прав.
Это не насколько очевидно, к примеру если мы расставляем 8 точек в прямоугольнике размером 2 на sqrt(3), то 6 из них нужно разместить вдоль длинных сторон, а две внутри среднего ряда. Если удвоить короткую сторону прямоугольника и расставлять в нём 13 точек, то ряды так и останутся параллельно стороне длиной 2, хотя теперь она является короткой стороной.
Пока алгоритм вырисовывается довольно страшноватый: 1) "Закинуть" в параллелепипед k сфер с начальным диаметром скажем 150/k (размеры параллелепипеда 77, 150, 28) в случайные координаты 2) Порасталкивать шары каким то количеством итераций интегрирования Верле, пропорциональным k.Причём шары должны отталкиваться друг от друга, но для стенок параллелепипеда шары - это просто точки. 3) Если после шага 2 шары не соприкасаются друг с другом - увеличить их диаметр и повторить шаг 2. Думаю должно быть проще, ведь все шары одинакового размера.
UbIvItS, Да. А нужно найти такое положение точек, при котором это минимальное расстояние максимально. Попробовал порасталкивать шары в 2D, ну то есть круги. Если для 2 кругов всё нормально, то для 3 и более происходит преждевременное "устаканивание" системы, при котором дальнейшее увеличение диаметра не возможно. Вот более удачный пример
тогда d(x,y)+d(y,z)+d(x,z) == MАХ и тады-сь получаем примерно так допустим, ящик с размерами 30х9х4 2 тчк == макс. длина 30м. 3 == равнобедренный треугольник (основание 30м, высота [9^2+4^2]^0,5). +++ короче, алгоритм на каждой итерации добавляет новую тчк относительно ранее расположенных.
