Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90769 Fri, 27 Jun 2003 09:57:58 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90769 O(N2)

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

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

если задача еще актуальна, то на договорных условиях возьмусь реализовать программу:):):)]]> Demo_S Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90768 Thu, 26 Jun 2003 08:18:37 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90768 Цитата Budda, 25.06.03, 19:34:37
Метод монте карло можно оптимизировать (ИМХО).
Ну во-первых, точки нужно брать не случайным образом, а перебором всех.

;D ;D ;D ;D ;D
Это уже не метод Монте Карло, а хрен...а к нему не хватает.
Перебор всех точек очень веселое занятие, если учесть что в постановке вопроса было указано -- прямоугольники заданы в Double post #8. Мантисса double ~10^15 соответсвенн надо пербрать 10^30 точек!!!]]> PAV Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90767 Wed, 25 Jun 2003 15:34:37 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90767 Ну во-первых, точки нужно брать не случайным образом, а перебором всех.

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

]]> Budda Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90766 Tue, 17 Jun 2003 17:53:21 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90766
разделяй и властвуй + включения/исключчения....

не была б счас сессия, я б написал.:):)]]> Demo_S Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90765 Tue, 17 Jun 2003 12:23:03 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90765 Aleksan Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90764 Tue, 17 Jun 2003 10:31:31 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90764
to wormball
Замечание справедливо для нормального распределения, а праведливо ли оно для равномерного (random).]]> PAV Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90763 Mon, 16 Jun 2003 13:33:39 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90763 вобще из математической статистики известно что дисперсия среднего арифметического обратно пропорциональна корню из колва точек, а коефициент не могу сказать. подумай, поинтегрируй ;D ;D ;D]]> wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90762 Mon, 16 Jun 2003 13:03:38 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90762 Но как оценить сколько нужно точек бросить чтобы получить нужную точность вычисления?]]> Aleksan Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90761 Mon, 16 Jun 2003 12:45:20 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90761 wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90760 Mon, 16 Jun 2003 08:02:45 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90760 Цитата Demo_S, 13.06.03, 10:57:21
пусть у нас есть три прямоугольника А, В и С.

площадь , которую они вместе покрывают будет равна
SA+SB+SC-
-SAB-SAC-SBC+SABC

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

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

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

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



Пожалуйста если можно напиши обобщенный алгоритм]]> Aleksan Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90759 Mon, 16 Jun 2003 05:52:36 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90759 Aleksan Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90758 Fri, 13 Jun 2003 17:15:48 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90758 Цитата Aleksan, 13.06.03, 16:01:37
Колличество прямоугольников может доходить до
25000 штук


Посмотри здесь: http://algolist.manual.ru/maths/geom/index.php. Может быть, что полезное отыщешь.]]> Alexsid Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90757 Fri, 13 Jun 2003 12:01:37 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90757 25000 штук]]> Aleksan Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90756 Fri, 13 Jun 2003 10:39:26 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90756 Aleksan Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90754 Fri, 13 Jun 2003 09:49:54 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90754 Цитата Aleksan, 13.06.03, 13:15:42
Метод Монтекарло не устраивает
Нужен точный результат

Так кинь десять тысяч точек и у тебя будет точность сотые доли процента. Мало? еще добавь.
А double все равно будет давать погрешность]]> MeG Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90753 Fri, 13 Jun 2003 09:39:49 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90753 double.
Так что CRgn не подходит]]> Aleksan Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90752 Fri, 13 Jun 2003 09:27:01 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90752 Делаем CRgn, пихаем туда все прямоугольники, потом говорим GetRegionData и получаем уже непересекающиеся прямоугольники (имхо). Тупо суммируем их площади, уря.]]> HOMO_PROGRAMMATIS Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90751 Fri, 13 Jun 2003 09:15:42 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90751 Нужен точный результат]]> Aleksan Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90750 Fri, 13 Jun 2003 08:18:51 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90750
Твоя фигура лежит внутри некоторой области известной площади So. Случайным образом кидаем n точек в эту область. Подсчитываем количество m точек  попавших внутрь фигуры (внутрь хотя бы одного прямоугольника). Площадь твоей фигуры Sf = So * m / n. Чем больше точек, тем точнее результат.]]> MeG Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90749 Fri, 13 Jun 2003 07:19:44 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90749 А другие варианты имеются?]]> Aleksan Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90748 Fri, 13 Jun 2003 06:57:21 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90748
площадь , которую они вместе покрывают будет равна
SA+SB+SC-
-SAB-SAC-SBC+SABC

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

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

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

ЗЫ попробуй все это нарисовать, будет проще:)]]> Demo_S Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90747 Fri, 13 Jun 2003 06:37:01 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90747 Aleksan Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90746 Fri, 13 Jun 2003 06:07:32 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90746
плащадь =
площади всех прямоугольников
- площадь пересечений каждый двух прямоугольникво
+ площадь пересечения каждых трех
- каждых четырех
+ каждых пяти
....
пока не будет использована площадь пересечения всех.

площадь пересечения n прямоугольников - это площадь общей части этих прямоугольников..
ЗЫ вопрос более уместен в разделе "алгоритмы"]]> Demo_S Алгоритмы https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90745 Fri, 13 Jun 2003 05:33:43 +0000 Алгоритм вычисления площади https://forum.sources.ru/index.php?showtopic=9259&view=findpost&p=90745 Если есть идеи подскажите пожалуйста.]]> Aleksan Алгоритмы