Есть ли простой алгоритм, который может найти конверт из нескольких кругов?

Question

Учитывая количество точек на 2d поверхности и радиусы для этих точек, я могу легко нарисовать круги для них. Мне нужен алгоритм, который рисует только конверт (правильное слово для того, что я ищу?) Или внешнюю границу этих объединенных кругов. Кроме того, второй набор кругов может «покушаться» на эти круги, в результате чего получается своего рода «граница».

Изображение того, что я ищу

Answer 1

Быстрый способ нарисовать схему объединения дисков -

• заполнить все диски желтым цветом, затем

• заполнитьвсе диски белого цвета с меньшим радиусом.

Это можно адаптировать к «вторженным» кружкам, при условии, что вы заполните только оставшиеся части дисков. К сожалению, в общем случае поиск оставшихся частей может быть непростой геометрической проблемой.

---

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

• заполните изображение нулями, затем для всех дисков заполните каждый пиксель значением расстояния до окружности (максимум в центре), но пока сохраняйте только самое высокое значение.

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

В конце этого процесса первое изображение будет представлять собой «ландшафт», состоящий из пересекающихся конусов;и для каждой точки ландшафта вы будете знать цвет.

• наконец, раскрасьте пиксели, высота которых меньше требуемой ширины обводки, используя карту цветов.

Answer 2

Вы можете сделать рисование в два этапа.

1) Нарисуйте контур, используя следующий метод: Для каждой точки нарисуйте круг, используя ваш любимый метод рисования кругов, но перед рисованием пикселя, убедитесь, чточто оно не содержится ни в каком другом круге. Сделайте это для каждой точки, и вы получите свой контур.

2) Постройте границы между различными наборами, используя следующий метод: Для каждой пары точек из разных наборов вычислите две точки пересечения окружностей. Если есть пересечение, граница может быть нарисована как сегмент, соединяющий эти две точки. Тем не менее, вы должны сделать две линии, одну для круга A, а другую для круга B. Чтобы нарисовать линию для круга A, слегка сместите сегмент в направлении точки A. Затем, используйте ваш любимый метод рисования линий, но перед рисованиемпиксель, убедитесь, что он ближе к точке А, чем любая другая точка противоположного множества. После рисования линии повторите процесс для круга B. Обратите внимание, что оба сегмента не обязательно имеют одинаковую длину из-за асимметрии точек разных наборов. Однако при рисовании всех контуров и границ он всегда будет иметь замкнутую форму.