разделяй и властвуй + включения/исключчения....
не была б счас сессия, я б написал.
| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Алгоритм вычисления площади |
| Автор: Aleksan 13.06.03, 05:33 |
| Нужен алгоритм вычисления прлщади фигуры состоящей и з множества пересекающихся прямоугольников. Если есть идеи подскажите пожалуйста. |
| Автор: Demo_S 13.06.03, 06:07 |
| формула включений-исключений... дается в дискретке. плащадь = площади всех прямоугольников - площадь пересечений каждый двух прямоугольникво + площадь пересечения каждых трех - каждых четырех + каждых пяти .... пока не будет использована площадь пересечения всех. площадь пересечения n прямоугольников - это площадь общей части этих прямоугольников.. ЗЫ вопрос более уместен в разделе "алгоритмы" |
| Автор: Aleksan 13.06.03, 06:37 |
| A можно поподробнее пожалуйста |
| Автор: Demo_S 13.06.03, 06:57 |
| пусть у нас есть три прямоугольника А, В и С. площадь , которую они вместе покрывают будет равна SA+SB+SC- -SAB-SAC-SBC+SABC SAB - это площадь общей части прямоугольников А и В. ------------------------------- - ******* - - * * - - *S(AB) * - - * * - ----*------*------------------ * * * * ******* А SABC - общей части всех прямоугоьлникв. для больше чем 3 обобщить сможешь? ЗЫ попробуй все это нарисовать, будет проще:) |
| Автор: Aleksan 13.06.03, 07:19 |
| Ясно, спасибо. А другие варианты имеются? |
| Автор: MeG 13.06.03, 08:18 |
| Метод монтекарло. Твоя фигура лежит внутри некоторой области известной площади So. Случайным образом кидаем n точек в эту область. Подсчитываем количество m точек попавших внутрь фигуры (внутрь хотя бы одного прямоугольника). Площадь твоей фигуры Sf = So * m / n. Чем больше точек, тем точнее результат. |
| Автор: Aleksan 13.06.03, 09:15 |
| Метод Монтекарло не устраивает Нужен точный результат |
| Автор: HOMO_PROGRAMMATIS 13.06.03, 09:27 |
| Можно воспользоваться Апи. Делаем CRgn, пихаем туда все прямоугольники, потом говорим GetRegionData и получаем уже непересекающиеся прямоугольники (имхо). Тупо суммируем их площади, уря. |
| Автор: Aleksan 13.06.03, 09:39 |
| Дело в том что все прямоугольники состоят из типа double. Так что CRgn не подходит |
| Автор: MeG 13.06.03, 09:49 |
| Цитата Aleksan, 13.06.03, 13:15:42 Метод Монтекарло не устраивает Нужен точный результат Так кинь десять тысяч точек и у тебя будет точность сотые доли процента. Мало? еще добавь. А double все равно будет давать погрешность |
| Автор: Aleksan 13.06.03, 10:39 |
| Дело в том что нужно вычислять это быстро и точно |
| Автор: Aleksan 13.06.03, 12:01 |
| Колличество прямоугольников может доходить до 25000 штук |
| Автор: Alexsid 13.06.03, 17:15 |
| Цитата Aleksan, 13.06.03, 16:01:37 Колличество прямоугольников может доходить до 25000 штук Посмотри здесь: http://algolist.manual.ru/maths/geom/index.php. Может быть, что полезное отыщешь. |
| Автор: Aleksan 16.06.03, 05:52 |
| А как выглядит формула оценки точности вычисления площади по методу Монтекарло? |
| Автор: Aleksan 16.06.03, 08:02 |
| Цитата Demo_S, 13.06.03, 10:57:21 пусть у нас есть три прямоугольника А, В и С. площадь , которую они вместе покрывают будет равна SA+SB+SC- -SAB-SAC-SBC+SABC SAB - это площадь общей части прямоугольников А и В. ------------------------------- - ******* - - * * - - *S(AB) * - - * * - ----*------*------------------ * * * * ******* А SABC - общей части всех прямоугоьлникв. для больше чем 3 обобщить сможешь? ЗЫ попробуй все это нарисовать, будет проще:) Пожалуйста если можно напиши обобщенный алгоритм |
| Автор: wormball 16.06.03, 12:45 |
| монтекарло ето вовсе даже не формула, а метод. берёшь область известной площади, например прямоугольную, содержащую в себе все твои прямоугольники, и начинаешь случайным образом тыкать в неё точки, чтобы они были равномерно распределены по ней. тогда площадь твоей фигуры будет приблизительно равна количеству точек, попавших в фигуру, делённому на общее их количество и умноженному на площадь твоей области. |
| Автор: Aleksan 16.06.03, 13:03 |
| Это ясно. Но как оценить сколько нужно точек бросить чтобы получить нужную точность вычисления? |
| Автор: wormball 16.06.03, 13:33 |
| чем болше тем лучше ;D ;D вобще из математической статистики известно что дисперсия среднего арифметического обратно пропорциональна корню из колва точек, а коефициент не могу сказать. подумай, поинтегрируй ;D ;D ;D |
| Автор: PAV 17.06.03, 10:31 |
| Монте Карло, ну-ну, успехов Вам. Только не забудте проверять принадлежность каждой точки всем многоугольникам ;D, генерировать точки надо по всему региону. Далее предполагаем точность 0.01\% ==> нужно проверить 10000*10000*25000=2.5 10^12 принадлежностей. Пусть в секунду проверяется 10^6 => вся работа чуть менее зем за 1000 часов. Есть повод потребовать от начальства Pentium IX с 4096 процессорами. to wormball Замечание справедливо для нормального распределения, а праведливо ли оно для равномерного (random). |
| Автор: Aleksan 17.06.03, 12:23 |
| А ты можешь что-нибудь быстрое предложить для 25000 примоугольников ? |
| Автор: Demo_S 17.06.03, 17:53 |
| дык:) разделяй и властвуй + включения/исключчения.... не была б счас сессия, я б написал. |
| Автор: Budda 25.06.03, 15:34 |
| Метод монте карло можно оптимизировать (ИМХО). Ну во-первых, точки нужно брать не случайным образом, а перебором всех. А потом, может 0.01\% и не нужно... |
| Автор: PAV 26.06.03, 08:18 |
| Цитата Budda, 25.06.03, 19:34:37 Метод монте карло можно оптимизировать (ИМХО). Ну во-первых, точки нужно брать не случайным образом, а перебором всех. ;D ;D ;D ;D ;D Это уже не метод Монте Карло, а хрен...а к нему не хватает. Перебор всех точек очень веселое занятие, если учесть что в постановке вопроса было указано -- прямоугольники заданы в Double post #8. Мантисса double ~10^15 соответсвенн надо пербрать 10^30 точек!!! |
| Автор: Demo_S 27.06.03, 09:57 |
| придумал кульный алгоритм:) O(N2) просмотриваем все пары прямоугольников. если прямоугольники пересекаются, то один из них оставляем, второй разбиваем на 2 прямоугольника, или обрезаем его, так, чтобы получившиеся в результате прямоугольники не пересекались. потом один проход - вычислить площадь всех прямоугольников и все:) если задача еще актуальна, то на договорных условиях возьмусь реализовать программу:) |