Область пересечения между кругом и прямоугольником

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

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

псевдокод (мой настоящий код - всего ~ 12 строк ..)

find the signed (negative out) normalized distance from the circle center
to each of the infinitely extended rectangle edge lines,
ie.
d_1=(xcenter-xleft)/r
d_2=(ycenter-ybottom)/r
etc

for convenience order 1,2,3,4 around the edge. If the rectangle is not
aligned with the cartesian coordinates this step is more complicated but
the remainder of the algorithm is the same

If ANY d_i <=- 1 return 0

if ALL d_i >=  1 return Pi r^2

this leave only one remaining fully outside case: circle center in
an external quadrant, and distance to corner greater than circle radius:

for each adjacent i,j (ie. i,j=1,2;2,3;3,4;4,1)
     if d_i<=0 and d_j <= 0 and d_i^2+d_j^2 > 1 return 0

now begin with full circle area  and subtract any areas in the
four external half planes

Area= Pi r^2
for each  d_i>-1
     a_i=arcsin( d_i )  #save a_i for next step
     Area -= r^2/2 (Pi - 2 a_i - sin(2 a_i)) 

At this point note we have double counted areas in the four external
quadrants, so add back in:

for each adjacent i,j
   if  d_i < 1 and   d_j < 1  and d_i^2+d_j^2 < 1
       Area += r^2/4 (Pi- 2 a_i - 2 a_j -sin(2 a_i) -sin(2 a_j) + 4 sin(a_i) sin(a_j))

return Area

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

Наслаждайтесь.

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

Площадь можно рассчитать путем интегрирования уравнения окружности y = sqrt [a ^ 2 - (xh) ^ 2] + k где a - радиус, (h, k) - центр круга, чтобы найти площадь под кривой. Вы можете использовать компьютерную интеграцию, где область делится на множество маленьких прямоугольников и вычислять их сумму, или просто использовать здесь закрытую форму.

А вот источник C #, реализующий концепцию выше. Обратите внимание, что существует особый случай, когда указанный х лежит вне границ круга. Я просто использую простой обходной путь (который не дает правильных ответов во всех случаях)

public static void RunSnippet()
{
    // test code
    double a,h,k,x1,x2;
    a = 10;
    h = 4;
    k = 0;
    x1 = -100;
    x2 = 100;

    double r1 = Integrate(x1, a, h, k);
    double r2 = Integrate(x2, a, h, k);

    Console.WriteLine(r2 - r1);

}

private static double Integrate(double x, double a,double h, double k)
{
    double a0 = a*a - (h-x)*(h-x);

    if(a0 <= 0.0){
        if(k == 0.0)
            return Math.PI * a * a / 4.0 * Math.Sign(x);
        else
            throw new Exception("outside boundaries");
    }

    double a1 = Math.Sqrt(a*a - (h-x)*(h-x)) * (h-x);
    double area = 0.5 * Math.Atan(a1 / ((h-x)*(h-x) - a*a))*a*a - 0.5 * a1 + k * x;
    return area;
}

Примечание: Эта проблема очень похожа на проблему в Google Code Jam Задача квалификационного раунда 2008 года : Мухобойка . Вы также можете щелкнуть ссылки для оценки, чтобы загрузить исходный код решения.

Спасибо за ответы,

Я забыл упомянуть, что оценки площади было достаточно. Тот; Поэтому, в конце концов, после просмотра всех вариантов, я пошел с оценкой Монте-Карло, где я генерирую случайные точки в круге и проверяю, находятся ли они в рамке.

В моем случае это, вероятно, более производительный. (У меня есть сетка, расположенная над кругом, и я должен измерить отношение круга, принадлежащего каждой из ячеек сетки.)

Спасибо

Возможно, вы можете использовать ответ на на этот вопрос , где задается область пересечения между кругом и треугольником. Разделите ваш прямоугольник на два треугольника и используйте алгоритмы, описанные там.

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

Вот еще одно решение проблемы:

public static bool IsIntersected(PointF circle, float radius, RectangleF rectangle)
{

        var rectangleCenter = new PointF((rectangle.X +  rectangle.Width / 2),
                                         (rectangle.Y + rectangle.Height / 2));

        var w = rectangle.Width  / 2;
        var h = rectangle.Height / 2;

        var dx = Math.Abs(circle.X - rectangleCenter.X);
        var dy = Math.Abs(circle.Y - rectangleCenter.Y);

        if (dx > (radius + w) || dy > (radius + h)) return false;


        var circleDistance = new PointF
                                 {
                                     X = Math.Abs(circle.X - rectangle.X - w),
                                     Y = Math.Abs(circle.Y - rectangle.Y - h)
                                 };


        if (circleDistance.X <= (w))
        {
            return true;
        }

        if (circleDistance.Y <= (h))
        {
            return true;
        }

        var cornerDistanceSq = Math.Pow(circleDistance.X - w, 2) + 
                    Math.Pow(circleDistance.Y - h, 2);

        return (cornerDistanceSq <= (Math.Pow(radius, 2)));
}