Re: Упаковка окружностей

From

Mikhail Kalenkov ()

To

Rustam Ramazanov

Date

2002-11-28T18:31:21Z

Area

RU.ALGORITHMS

From: "Mikhail Kalenkov" <kalenkov@rinet.ru>

Hello Rustam

> Попробую переформулировать, видимо сделал это не точно.
> Есть на плоскости набор из n кружочков заданного радиуса. Нужно найти
> кольцо минимального радиуса такое, чтобы в него можно было поместить
> все кружочки. Естественно, что кружочки перекрываться не должны.
> Интересует также как правильно разместить эти кружочки в кольце.
> В этом плане посоветуйте.
А сколько реально у тебя кружочков? Больше 1000? Тебе действительно нужна
оптимальность или годится решение очень близкое к оптимальному? В любом
случае у меня есть пару идей. Мне почему-то кажется, что в случае равных
окружностей их центры должны образовывать, так называемую, треугольную
решётку (система равносторонних треугольников плотно заполняющих
плоскость). Заполним теперь всю плоскость кружочками с центрами в узлах
треугольной решётки. Выберем теперь произвольную точку на этой плоскости и
окружность с центром в этой точке. Внутрь этой окружности попадёт некоторое
количество кружочков, причём их количество несложно вычислить. Если
попалось мало кружочков, то чуть увеличиваем радиус окружности и так до
достижении того момента, как в нашу большую окружность попадёт ровно нужное
количество кружков. Теперь дело за тонкой подгонкой радиуса окружности. Тут
можно действовать так. Найдём минимальное расстояние от целых кружков
попавших в нашу окружность до границы окружности. На это расстояние можно
спокойно уменьшить радиус окружности. Таким образом мы нашли радиус
описывающей окружности как функцию положения центра. Осталось
минимизировать эту функцию, для чего существует достаточно много
алгоритмов. Нужно только опасаться попасть в локальный минимум.
> Также, если есть n кружочков одного радуиса и m другого. Но эта задача
> намного сложней и я не знаю, разрешима ли она вообще?
Мне кажется, что гарантированного алгоритма тут нет.

    Михаил Каленков.


--- ifmail v.2.15dev5
 * Origin: Cronyx Plus ISP (2:5020/400)