Есть прямоугоьлная область и она покрывается неким неограниченным количеством кругом. Надо узнать когда процент покрытия превысит некий порог. Фишка в том, что круги могут залазить друг на друга и даже вообще совпадать. Абсолютная точность процентажа не нужна, можно некие оценки.

Как сделать наиболее быстро работающий алгоритм?

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

H>Есть прямоугоьлная область и она покрывается неким неограниченным количеством кругом. Надо узнать когда процент покрытия превысит некий порог. Фишка в том, что круги могут залазить друг на друга и даже вообще совпадать. Абсолютная точность процентажа не нужна, можно некие оценки.

H>Как сделать наиболее быстро работающий алгоритм?

Навскидку — можно нагенерировать точек с координатами для прямоугольника и кругов, засунуть в std::set, потом через разность множеств посчитать, сколько отъели у прямоугольника круги.
Второй способ — графический. Где-то в буфере рисовать круги одного цвета на прямоугольнике другого цвета. Потом считать, сколько точек осталось цвета прямоугольника.
Что в первом способе скорость и точность будет зависеть от количества точек (во втором от шага подсчёта или масштаба).

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

H>Как сделать наиболее быстро работающий алгоритм?

Аппроксимировать круги полигонами. На каждом шаге вычислять разность между исходной областью (она может разбиваться) и очередным кругом.

Библиотеки для клиппинга есть готовые и оптимизированные. Сами алгоритмы можно посмотреть там же.

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

H>Абсолютная точность процентажа не нужна, можно некие оценки.
H>Как сделать наиболее быстро работающий алгоритм?

доработать идею: Урок 14. Измерение площади фигуры с помощью палетки

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

H>Есть прямоугоьлная область и она покрывается неким неограниченным количеством кругом. Надо узнать когда процент покрытия превысит некий порог. Фишка в том, что круги могут залазить друг на друга и даже вообще совпадать. Абсолютная точность процентажа не нужна, можно некие оценки.

H>Как сделать наиболее быстро работающий алгоритм?

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

Если хочется скорость лучше чем n квадрат, для предварительной фильтрации кругов, проверяемых для каждой точки использовать
https://ru.wikipedia.org/wiki/Дерево_квадрантов
Предварительно можно исключить круги, находящиеся полностью внутри других кругов.

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

S>Метод Монте Карло Думаю тут будет быстрее, чем считать площади дополнений.
S>Или подсчет по регулярной сетке, как в ответе по палетке.
S>Но Монте Карло будет быстрей, потому что можно заканчивать расчет , если порог будет превышен (с запасом).

Вот мне тоже Монте-Карло сразу вспомнился