На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Площадь общей части круга и квадрата , Алгоритм нахождения площади пересечения
    Дан квадрат с вершинами (0; 0),(1, 0),(1; 1),(0, 1) и окружность с центром в (x, y) радиусом r. Как найти площадь общей части этих фигур?
      Найти точки и форму пересечения, разбить его на простые части - сектора, сегменты круга, треугольники, вычислить площадь каждой части.
        Представить окружность к примеру 32 угольником.
        Найти пересечение двух многоугольников одним из алгоритмов.
        https://yadi.sk/i/63hpws523Q4Gwz
        И вычислить площадь многоугольника
        http://pers.narod.ru/algorithms/pas_polygon_square.html
          Нужно разделить задачу на частные случаи:
          1. круг вне квадрата.
          2. круг внутри квадрата.
          3. центр круга вне квадрата, внутрь круга попадает часть квадрата без вершин.
          4. центр круга вне квадрата, внутрь круга попадает часть квадрата с одной вершиной.
          ....
          И так далее, вариантов довольно много, и у каждого решение будет своё. Эти решения по отдельности не представляют большой сложности, если какой-то конкретный случай вызывает затруднения - могу расписать подробнее.
            Печаль ещё и в том, что если расширить/поменять задачу на куб и шар, то всё несколько усложнится. А изначально хочется/ожидается нечто простенькое... :yes-sad:
              Я бы просто разбил границу пересечения на части, каждая из которых либо отрезок, либо дуга, после чего просто посчитал площадь по формуле Грина.
                Нужно квантовать исходный квадрат!

                Пусть длина стороны квадрата равна а, где а = 10 000, 100 000, 1 000 000 или 1 000 000 000 атомов/точек))
                Для КАЖДОЙ точки/атома квадрата найти расстояние от центра окружности до нее, и, если расстояние будет МЕНЬШЕ радиуса окружности, следовательно, эта часть квадрата, состоящая из 1-го атома, попадает в область окружности...
                Зная кол-во таких атомов, легко получить общую площадь

                Преимущества: не нужно знать сложные алгоритмы, геометрию и хорошо уметь программировать, т к все сводится к циклам for и элементарным формулам
                Недостатки: если взять триллион атомов, то быстродействие "умрет"

                Смотря, какая нужна точность расчета, до какого знака...
                Примечание: точка/атом обладает определенной площадью, хотя в классической геом. точка НЕ имеет площади..

                Скрытый текст
                Возможно, приведенный алгоритм полный бред :no:
                  А если переписать решение задачи на шейдеры, то вообще можно много выиграть!.. :rolleyes:
                    Цитата Mikle @
                    Нужно разделить задачу на частные случаи:
                    1. круг вне квадрата.
                    2. круг внутри квадрата.
                    3. центр круга вне квадрата, внутрь круга попадает часть квадрата без вершин.
                    4. центр круга вне квадрата, внутрь круга попадает часть квадрата с одной вершиной.

                    +1 а потом взять и найти ;)
                    0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                    0 пользователей:


                    Рейтинг@Mail.ru
                    [ Script execution time: 0,0272 ]   [ 15 queries used ]   [ Generated: 29.03.24, 02:08 GMT ]