Алгоритм вычисления площади

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

Это ясно.
Но как оценить сколько нужно точек бросить чтобы получить нужную точность вычисления?

чем болше тем лучше ;D ;D
вобще из математической статистики известно что дисперсия среднего арифметического обратно пропорциональна корню из колва точек, а коефициент не могу сказать. подумай, поинтегрируй ;D ;D ;D

Монте Карло, ну-ну, успехов Вам. Только не забудте проверять принадлежность каждой точки всем многоугольникам ;D, генерировать точки надо по всему региону. Далее предполагаем точность 0.01\% ==> нужно проверить 10000*10000*25000=2.5 10^12 принадлежностей. Пусть в секунду проверяется 10^6 => вся работа чуть менее зем за 1000 часов. Есть повод потребовать от начальства Pentium IX с 4096 процессорами.

to wormball
Замечание справедливо для нормального распределения, а праведливо ли оно для равномерного (random).

Сообщение отредактировано: PAV - 17.06.03, 10:38

А ты можешь что-нибудь быстрое предложить для 25000 примоугольников ?

дык:)

разделяй и властвуй + включения/исключчения....

не была б счас сессия, я б написал.

Метод монте карло можно оптимизировать (ИМХО).
Ну во-первых, точки нужно брать не случайным образом, а перебором всех.

А потом, может 0.01\% и не нужно...

Цитата Budda, 25.06.03, 19:34:37

Метод монте карло можно оптимизировать (ИМХО).
Ну во-первых, точки нужно брать не случайным образом, а перебором всех.

;D ;D ;D ;D ;D
Это уже не метод Монте Карло, а хрен...а к нему не хватает.
Перебор всех точек очень веселое занятие, если учесть что в постановке вопроса было указано -- прямоугольники заданы в Double post #8. Мантисса double ~10^15 соответсвенн надо пербрать 10^30 точек!!!

придумал кульный алгоритм:)
O(N²)

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

потом один проход - вычислить площадь всех прямоугольников и все:)

если задача еще актуальна, то на договорных условиях возьмусь реализовать программу:)