Расстановка точек в 3D пространстве

Тема в разделе "WASM.A&O", создана пользователем murder, 8 май 2018.

  1. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Имеется параллелепипед со сторонами A, B, C и заданное количество точек k. Требуется расположить точки внутри параллелепипеда так, чтобы максимизировать минимальное расстояние между парами соседних точкек.

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

    На геймдеве нашёл такой совет:
    Отсюда и вытекает сабж.

    Решается ли такое за конечное приемлемое время? Если да, то какими методами (киньте ссылкой).
     
  2. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    murder, если мы ищем самое оптимальное решение при изначально фиксированном k, то сложность этой задачи скорее всего будет NP. Наиболее эффективный для практического применения может быть такой вариант: взять гексагональную упаковку шаров, выбрать такой шаг между ними, чтобы требуемое количество влезало в параллелепипед, двигать и вращать параллелепипед относительно шаров чтобы можно было чуть увеличить размер шариков или запихать еще несколько штук. Хотя скорее всего оптимальным будет разместить слои шаров параллельно одной из граней, нужно будет только выбрать относительно какой.

    https://ru.wikipedia.org/wiki/Плотная_упаковка_равных_сфер
    Судя по картинке параллельно одной из граней получается при гексагональной упаковке, при кубической будет параллельно граням тетраэдра вписанного в куб, но в любом случае вычислить количество шаров можно будет только после того, как определимся с их раскладкой.
     
    Последнее редактирование: 8 май 2018
    murder нравится это.
  3. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    murder, не совсем понятно.. допустим, имеем 3 тчк (x,y,z) и d(x,y)+d(y,z)+d(x,z) == MIN
    так ???:scratch_one-s_head:
     
  4. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Black_mirror,
    Круто - похоже на то, что нужно.
    Очевидно параллельно самой большой по площади. Пошёл медитировать.

    UbIvItS,
    нет MIN=min(d(x,y),d(x,z),d(zy)). В моём представлении максимум этой функции даст палитру наиболее различимых оттенков цвета. Может я и не прав.
     
  5. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Согласно Гипотезе Кеплера нужно использовать так называемую гранецентрированную кубическую упаковку.
     
  6. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Это не насколько очевидно, к примеру если мы расставляем 8 точек в прямоугольнике размером 2 на sqrt(3), то 6 из них нужно разместить вдоль длинных сторон, а две внутри среднего ряда. Если удвоить короткую сторону прямоугольника и расставлять в нём 13 точек, то ряды так и останутся параллельно стороне длиной 2, хотя теперь она является короткой стороной.
     
  7. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Пока алгоритм вырисовывается довольно страшноватый:
    1) "Закинуть" в параллелепипед k сфер с начальным диаметром скажем 150/k (размеры параллелепипеда 77, 150, 28) в случайные координаты
    2) Порасталкивать шары каким то количеством итераций интегрирования Верле, пропорциональным k.Причём шары должны отталкиваться друг от друга, но для стенок параллелепипеда шары - это просто точки.
    3) Если после шага 2 шары не соприкасаются друг с другом - увеличить их диаметр и повторить шаг 2.

    Думаю должно быть проще, ведь все шары одинакового размера.
     
  8. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    получается ноль мин. расстояние.
     
  9. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    UbIvItS,
    Да. А нужно найти такое положение точек, при котором это минимальное расстояние максимально.

    Попробовал порасталкивать шары в 2D, ну то есть круги. Если для 2 кругов всё нормально, то для 3 и более происходит преждевременное "устаканивание" системы, при котором дальнейшее увеличение диаметра не возможно.

    1.png

    Вот более удачный пример
    1.png
     
    Последнее редактирование: 10 май 2018
  10. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Наверное нужно задавать начальные координаты не рандомом а сеткой.
     
  11. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    тогда d(x,y)+d(y,z)+d(x,z) == MАХ и тады-сь получаем примерно так
    допустим, ящик с размерами 30х9х4

    2 тчк == макс. длина 30м.
    3 == равнобедренный треугольник (основание 30м, высота [9^2+4^2]^0,5).
    +++
    короче, алгоритм на каждой итерации добавляет новую тчк относительно ранее расположенных.