Процент покрытия прямоугольника кругами
От: Homunculus Удмуртия  
Дата: 09.06.21 11:07
Оценка:
Есть прямоугоьлная область и она покрывается неким неограниченным количеством кругом. Надо узнать когда процент покрытия превысит некий порог. Фишка в том, что круги могут залазить друг на друга и даже вообще совпадать. Абсолютная точность процентажа не нужна, можно некие оценки.

Как сделать наиболее быстро работающий алгоритм?
Re: Процент покрытия прямоугольника кругами
От: Maniacal Россия  
Дата: 09.06.21 11:31
Оценка:
Здравствуйте, Homunculus, Вы писали:

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


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


Навскидку — можно нагенерировать точек с координатами для прямоугольника и кругов, засунуть в std::set, потом через разность множеств посчитать, сколько отъели у прямоугольника круги.
Второй способ — графический. Где-то в буфере рисовать круги одного цвета на прямоугольнике другого цвета. Потом считать, сколько точек осталось цвета прямоугольника.
Что в первом способе скорость и точность будет зависеть от количества точек (во втором от шага подсчёта или масштаба).
Re: Процент покрытия прямоугольника кругами
От: wildwind Россия  
Дата: 09.06.21 11:53
Оценка:
Здравствуйте, Homunculus, Вы писали:

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


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

Библиотеки для клиппинга есть готовые и оптимизированные. Сами алгоритмы можно посмотреть там же.
Отредактировано 09.06.2021 11:53 wildwind . Предыдущая версия .
Re: Процент покрытия прямоугольника кругами
От: VsevolodC Россия  
Дата: 09.06.21 12:57
Оценка: +1
Здравствуйте, Homunculus, Вы писали:

H>Абсолютная точность процентажа не нужна, можно некие оценки.

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

доработать идею: Урок 14. Измерение площади фигуры с помощью палетки
Re: Процент покрытия прямоугольника кругами
От: swame  
Дата: 10.06.21 08:22
Оценка: +1
Здравствуйте, Homunculus, Вы писали:

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


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


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

Если хочется скорость лучше чем n квадрат, для предварительной фильтрации кругов, проверяемых для каждой точки использовать
https://ru.wikipedia.org/wiki/Дерево_квадрантов
Предварительно можно исключить круги, находящиеся полностью внутри других кругов.
Отредактировано 10.06.2021 8:30 swame . Предыдущая версия . Еще …
Отредактировано 10.06.2021 8:26 swame . Предыдущая версия .
Re[2]: Процент покрытия прямоугольника кругами
От: Mr.Delphist  
Дата: 18.06.21 12:05
Оценка:
Здравствуйте, swame, Вы писали:

S>Метод Монте Карло Думаю тут будет быстрее, чем считать площади дополнений.

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

Вот мне тоже Монте-Карло сразу вспомнился
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.