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

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

Сообщение отредактировано: vot - 28.06.03, 13:31

формула включений-исключений... дается в дискретке.

плащадь =
площади всех прямоугольников
- площадь пересечений каждый двух прямоугольникво
+ площадь пересечения каждых трех
- каждых четырех
+ каждых пяти
....
пока не будет использована площадь пересечения всех.

площадь пересечения n прямоугольников - это площадь общей части этих прямоугольников..
ЗЫ вопрос более уместен в разделе "алгоритмы"

A можно поподробнее пожалуйста

пусть у нас есть три прямоугольника А, В и С.

площадь , которую они вместе покрывают будет равна
S_A+S_B+S_C-
-S_AB-S_AC-S_BC+S_ABC

S_AB - это площадь общей части прямоугольников А и В.
-------------------------------
-    *******                        -
-    *         *                        -
-    *S(AB) *                        -
-    *         *                        -
----*------*------------------
    *         *
    *         *
    *******

А S_ABC - общей части всех прямоугоьлникв.

для больше чем 3 обобщить сможешь?

ЗЫ попробуй все это нарисовать, будет проще:)

Сообщение отредактировано: Demo_S - 13.06.03, 06:59

Ясно, спасибо.
А другие варианты имеются?

Метод монтекарло.

Твоя фигура лежит внутри некоторой области известной площади So. Случайным образом кидаем n точек в эту область. Подсчитываем количество m точек  попавших внутрь фигуры (внутрь хотя бы одного прямоугольника). Площадь твоей фигуры Sf = So * m / n. Чем больше точек, тем точнее результат.

Сообщение отредактировано: m - 13.06.03, 08:20

Метод Монтекарло не устраивает
Нужен точный результат

Можно воспользоваться Апи.
Делаем CRgn, пихаем туда все прямоугольники, потом говорим GetRegionData и получаем уже непересекающиеся прямоугольники (имхо). Тупо суммируем их площади, уря.

Дело в том что все прямоугольники состоят из типа
double.
Так что CRgn не подходит

Цитата Aleksan, 13.06.03, 13:15:42

Метод Монтекарло не устраивает
Нужен точный результат

Так кинь десять тысяч точек и у тебя будет точность сотые доли процента. Мало? еще добавь.
А double все равно будет давать погрешность

Дело в том что нужно вычислять это быстро и точно

Колличество прямоугольников может доходить до
25000 штук

Цитата Aleksan, 13.06.03, 16:01:37

Колличество прямоугольников может доходить до
25000 штук

Посмотри здесь: http://algolist.manual.ru/maths/geom/index.php. Может быть, что полезное отыщешь.

А как выглядит формула оценки точности вычисления площади по методу Монтекарло?

Цитата Demo_S, 13.06.03, 10:57:21

пусть у нас есть три прямоугольника А, В и С.

площадь , которую они вместе покрывают будет равна
S_A+S_B+S_C-
-S_AB-S_AC-S_BC+S_ABC

S_AB - это площадь общей части прямоугольников А и В.
-------------------------------
-    *******                        -
-    *         *                        -
-    *S(AB) *                        -
-    *         *                        -
----*------*------------------
    *         *
    *         *
    *******

А S_ABC - общей части всех прямоугоьлникв.

для больше чем 3 обобщить сможешь?

ЗЫ попробуй все это нарисовать, будет проще:)

Пожалуйста если можно напиши обобщенный алгоритм

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

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

чем болше тем лучше ;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 прямоугольника, или обрезаем его, так, чтобы получившиеся в результате прямоугольники не пересекались.

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

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