Проблема решена.

Это сообщение отредактировал(а) Vasiliyvaya - 7.12.2011, 14:00

С такой точностью подойдёт простое приближённое решение: заменим окружность правильным многоугольником, скажем, со 100 000 точек, и пересечём этот многоугольник с треугольником.

Хинт: чтобы точность была получше, правильный многоугольник надо брать такой, чтобы его площадь равнялась PI*r^2, т.е. расстояние от вершин до центра этого многоугольника должны быть чуть больше r (на сколько больше - можно посчитать с помощью формулы площади правильного многоугольника).

Как пересекать многоугольник с треугольником? Есть очень простой алгоритм пересечения многоугольника с полуплоскостью: мы идём по вершинам многоугольника, и смотрим: если текущая вершина лежит в требуемой полуплоскости, то добавляем её в ответ; затем смотрим: если текущая вершина и следующая вершина лежат строго по разные стороны от прямой, то добавляем в ответ точку пересечения прямой с этим отрезком.

Итого - простое приближённое решение с ~30 строками кода.



Просто для сравнения - точное решение этой задачи будет примерно таким. Находим все точки пересечения окружности со сторонами треугольника, добавляем к ним три вершины треугольника. Затем строим из этих точек планарный граф (в котором рёбра могут быть как прямыми отрезками, так и дугами окружности), и удаляем из графа те рёбра, середины которых не лежат в окружности либо в треугольнике. Дальше у нас остались только рёбра, ограничивающие искомую фигуру, поэтому одним обходом мы можем выписать эти рёбра в том порядке, в котором они идут вдоль границы. Тогда задача нахождения площади сводится к двум позадачкам: по данному ребру найти площадь трапеции под ним (это халява) и по данной дуге найти площадь криволинейной трапеции под ней (а это жесть, придётся поковыряться с интегралами). Итого получилось решение, пожалуй, раз в 100 сложнее по написанию 

to maxdiver.
Можете показать примерный код приближенного решения?

Ну у меня нет готовой реализации под рукой. Кажется, что "примерно" я и так словами уже всё описал.
Вся реализация сводится к тому, чтобы три раза пересечь многоугольник с полуплоскостью (полуплоскость - это прямая плюс знак (+ или -) ). Как пересекать - я написал.

Непонятно как мы саму площадь пересечения найдем-то? Мы же ведь добавляем точки, а не какую-то площадь чего-либо.

Ну после того, как мы пересечём всё и получим многоугольник - найти его площадь уже совсем просто.
Формула площади:

Тогда нам надо найти только точки пересечения, зачем добавлять еще точки, которые лежат в нужной стороне полуплоскости?

Как это - был многоугольник из тысяч точек, мы хотим пересечь его с треугольником - нельзя же для этого только точки пересечения оставить.

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

Ну почти второй вариант, только мы сначала оставим все точки, подходящие под первую полуплоскость, потом среди них оставим все точки, подходящие под вторую полуплоскость, и потом среди оставшихся - только те, что подходят под третью. Итого лишних точек не будет, и точки получатся в порядке обхода многоугольника (это важно для формулы площади: случайно перемешанные точки ей не подойдут).

Да, понятно.
Тогда еще такой вопрос, а как нормально получить эти 10^6 точек многоугольника? Чтобы они были в порядке обхода.

Изначально - понятно как, это просто правильный многоугольник. Если не понятно, то идея такая: пусть r' - это расстояние от центра многоугольника до вершины (r' примерно равно r, оно должно быть чуть больше), и пусть N - число вершин. Тогда i-ая точка будет иметь координаты (r' * cos(2*PI/N*i), r' * sin(2*PI/N*i)).

Потом - когда мы пересекаем с каждой полуплоскостью, этот порядок не нарушится. Действительно, от того, что часть точек удалилась, а перед/после них добавилось по одной точке (точке пересечения) - от этого относительный порядок оставшихся точек не нарушится.

Такое решение работает не всегда верно, например, 
x0 = 4, y0 = 4, r = 5
x1 = 0, y1 = 0, x2 = 4, y2 = 0, x3 = 0, y3 = 4.
Тогда, построив многоугольник, мы включим только точки пересесения и несколько точек многоугольника, но вершины треугольника не добавим, то есть площадь неправильно будет посчитана.

Нет, почему же, вершины треугольника тоже добавятся.
Ещё раз: мы последовательно пересекаем многоугольник с тремя полуплоскостями: с одной стороной треугольника, со второй стороной, и затем с третьей.
Скажем, вершина (4,0) появится после пересечения с полуплоскостями (0,0)-(4,0) и (0,4)-(4,0).

Я не понимаю, как она добавится. Ведь мы же проверяем точки многоугольника с полуплоскостями, мы найдем точку пересечения его со стороной (0 0) - (4 0), добавим её, но ведь точку 4 0 не добавим, ведь она и не принадлежит многоугольнику и не является точкой пересечения.