Есть окружности. Вокруг них нужно построить плавный контур. Можно это сделать путем 'честного' пересчета, но это не катит в силу трудозатрат. Сейчас реализован алгоритм на основе расчета нормали (расчитываем нижнюю точку контура, и "двигаемся" по часовой стрелки по контуру, определяя все его точки). Но этот метод тоже не очень хорош по производительности в силу того, что нужно очень много рачитывать силу и нормаль. Также при этом методе накапливается ошибка, что ведет в неправильному построению контура
Кто-нибудь сталкивался с такой проблемой? Есть ли надежный и быстроработающий алгоритм для решения этой задачи?

Здравствуйте, Аноним, Вы писали:

А> Кто-нибудь сталкивался с такой проблемой? Есть ли надежный и быстроработающий алгоритм для решения этой задачи?

Первое, что приходит в голову — вариации на тему выпуклой оболочки (convex hull). Для этого надо окружности превратить в правильные многоугольники и посчитать выпуклую оболочку. После чего востановить список окружностей в порядке обхода и посчитать точные отрезки и дуги.

Здравствуйте, Аноним, Вы писали:

А> Есть окружности. Вокруг них нужно построить плавный контур. Можно это сделать путем 'честного' пересчета, но это не катит в силу трудозатрат. Сейчас реализован алгоритм на основе расчета нормали (расчитываем нижнюю точку контура, и "двигаемся" по часовой стрелки по контуру, определяя все его точки). Но этот метод тоже не очень хорош по производительности в силу того, что нужно очень много рачитывать силу и нормаль. Также при этом методе накапливается ошибка, что ведет в неправильному построению контура
А> Кто-нибудь сталкивался с такой проблемой? Есть ли надежный и быстроработающий алгоритм для решения этой задачи?

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

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, Аноним, Вы писали:

А>> Кто-нибудь сталкивался с такой проблемой? Есть ли надежный и быстроработающий алгоритм для решения этой задачи?

MS>Первое, что приходит в голову — вариации на тему выпуклой оболочки (convex hull). Для этого надо окружности превратить в правильные многоугольники и посчитать выпуклую оболочку. После чего востановить список окружностей в порядке обхода и посчитать точные отрезки и дуги.

А можно подробнее? Как, например расчитать плавный переход между окружностями?

Здравствуйте, xp, Вы писали:

xp>Здравствуйте, Аноним, Вы писали:

А>> Есть окружности. Вокруг них нужно построить плавный контур. Можно это сделать путем 'честного' пересчета, но это не катит в силу трудозатрат. Сейчас реализован алгоритм на основе расчета нормали (расчитываем нижнюю точку контура, и "двигаемся" по часовой стрелки по контуру, определяя все его точки). Но этот метод тоже не очень хорош по производительности в силу того, что нужно очень много рачитывать силу и нормаль. Также при этом методе накапливается ошибка, что ведет в неправильному построению контура
А>> Кто-нибудь сталкивался с такой проблемой? Есть ли надежный и быстроработающий алгоритм для решения этой задачи?

xp>Для начала скажите, что означает "плавный контур" и желательно рисунок с примером.
xp>И думаю помогут кривые Безье, нужно только в зависимости от задачи правильно определить точки кривой Безье.

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

Здравствуйте, Аноним, Вы писали:

А> По сути нужен metaball. Сейчас я реализовал вот этот алгоритм здесь. Но как уже сказал он мне не очень нарвится вот и хочется узнать как можно сделать такое или приближенное к этому, но с меньшими напрягами со стороны проца.

Можно попробовать следующим образом:

Задачу сводим до обвода двух контуров, остальные контура по тому же принципу.
Берем кривую Безье второго порядка (квадратная кривая) здесь
Нам нужно найти три точки — Р0, Р1, Р2.

Крайние точки должны лежать на своих окружностях, средняя видимо на линии АВ, перпендикулярной к линии, соединяющей центры окружностей.
То есть нужно найти:
1. Угловую координату точки Р0
2. Угловую координату точки Р2
3. Расстояние от центров окружностей до АВ
4. Расстояние от пересечения линии, соединяющей окружности с АВ до точки P1.
Входные параметры — диаметры и расстояние между центрами.
Нужно подобрать формулы для расчета четырех необходимых величин по трем известным таким образом.
Это на уровне идеи, сам не пробовал, но рисунок нарисован в CorelDraw, там красным цветом настоящая кривая безье, поэтому вроде должно получиться.

Здравствуйте, Аноним, Вы писали:

А> А можно подробнее? Как, например расчитать плавный переход между окружностями?

Нужно было так сразу и говорить про metaball. Я же исходил из предположения, что окружности должны быть соединены прямыми отрезками по касательным.