| Радиус первой окружности |
| Радиус второй окружности |
| Расстояние между двумя окружностями |
| Площадь пересечения двух окружностей по заданным параметрам равна: |
|
| Первые координаты пересечения | |
| Вторые координаты пересечения |
Позволяет рассчитать площадь пересечения двух окружностей произвольных радиусов.
Используются достаточно простые формулы, которые элементарно доказываются.
Дополнительно есть калькулятор, который высчитывает координаты пересечения двух окружностей
Площадь пересечения двух окружностей состоит из двух сегментов FDG и FBG
Вывести формулу расчета площади пересечения двух окружностей можно из двух общеизвестных формул и знаний решения треугольника:
Формулы сектора окружности
(S=cfrac{alpha(R^2)}{2})
и длина хорды окружности
(L=2Rsin(cfrac{alpha}{2}))
По известным сторонам треугольника AFС определяем высоту на сторону AC.
Удвоением этой высоты мы получаем длину хорды, после этого узнаем угол альфа по второй формуле.
По известным сторонам треугольника AFG узнаем его площадь. Вычитаем её из площади сектора окружности, ведь угол альфа нам уже известен.
И получаем площадь сегмента FBG
Подобным образом вычисляем FDG
Это лишь один из способов решения задачи вычисления площади пересечения двух окружностей.
(S=S_1+S_2)
(S_1=cfrac{R_1^2*(F_1-sin(F_1))}{2})
(S_2=cfrac{R_2^2*(F_2-sin(F_2))}{2})
где
(F_1=2*acos{cfrac{R_1^2-R_2^2+D^2}{2*R_1*D}})
(F_2=2*acos{cfrac{R_2^2-R_1^2+D^2}{2*R_2*D}})
где
– радиус первой окружности
– радиус второй окружности
– расстояние между центрами окружностей
Пример
Хотим узнать площадь пересечения двух окружностей радиусом в 1 и расстоянием между центрами 0.8079455
Пишем okr 1 1 0.8079455
Ответ
Площадь двух пересекающихся окружностей равна = 1.5707963388681~ (pi/2)
Первая окружность радиус 4, вторая окружность радиус 2, расстоянием между центрами 3
Пишем okr 4 2 3
Ответ
Площадь двух пересекающихся окружностей равна = 9.5701994729833
Первая окружность радиус 4, вторая окружность радиус 2, расстоянием между центрами 0
Пишем okr 4 2 0
Ответ
Окружности не пересекаются
Нужно найти площадь пересечения двух окружностей (формулы взял тут):
S = S1 + S2
где,
- R1 — радиус первой окружности;
- R2 — радиус второй окружности;
- D — расстояние между центрами окружностей.
Код:
float find_area(float x1, float y1, float r1, float x2, float y2, float r2) {
// Расстояние между центрами окружностей
float distance = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
float f1, f2;
float s1, s2;
if(distance >= r1 + r2) {
// Если не пересекаются (можно дополнить вычислением площади внутренней окружности)
return 0;
}else if(distance <= fabs(r1 - r2)) {
// Если окружность внутри другой
return 0;
}
else {
// Если пересекаются
f1 = 2 * acos((r1*r1 - r2*r2 - distance*distance) / (2 * r1 * distance));
f2 = 2 * acos((r2*r2 - r1*r1 - distance*distance) / (2 * r2 * distance));
s1 = (r1*r1 * (f1 - sin(f1))) / 2;
s2 = (r2*r2 * (f2 - sin(f2))) / 2;
return s1 + s2;
}
return 0;
}
Площадь пересечения окружностей
(x1 = 0; y1 = 0; r1 = 2) ∩ (x2 = 3; y2 = 0; r2 = 4)
должна быть равна примерно 9.57019, но у меня выводит что-то непонятное:
-1.#IND00
eri
31.6k3 золотых знака26 серебряных знаков56 бронзовых знаков
задан 27 ноя 2016 в 20:06
Hardc0reHardc0re
1,1492 золотых знака11 серебряных знаков26 бронзовых знаков
9
В комментариях уже всё обсудили, добавлю только что неплохо было бы проверить аргументы acos на [-1...1], а то знаете ли, бывают такие окружности, что круг в них не помещается 🙂 В смысле, что формула строго не доказана на всём диапазоне значений. Кстати, спасибо автору за код! 🙂
Саша Черных
4,24614 золотых знаков41 серебряный знак92 бронзовых знака
ответ дан 5 фев 2017 в 5:18
1
В коде ошибка!
acos((r1*r1 - r2*r2 - distance*distance)
Исходя из формулы, квадрат дистанции надо прибавлять
Gleb Kemarsky
7,2742 золотых знака22 серебряных знака45 бронзовых знаков
ответ дан 3 июн 2017 в 17:19
JavaScript реализация на основе формулы из нажми.
function Circle(x, y , r) {
this.x = x;
this.y = y;
this.r = r;
this.getAreaOfCircle = function() {
let areaOfCircle = Math.PI * Math.pow(this.r, 2);
return areaOfCircle;
}
}
const firstСircle = new Circle(0, 0, 3);
const secondCircle = new Circle(5, 0, 4);
function getAreaOfIntersectionOfCircles(firstСircle, secondCircle) {
let distance = Math.sqrt(Math.pow((firstСircle.x - secondCircle.x), 2) + Math.pow((firstСircle.y - secondCircle.y), 2));
if (distance >= firstСircle.r + secondCircle.r) {
return 0;
} else if ((distance + secondCircle.r) <= firstСircle.r) {
return secondCircle.getAreaOfCircle()
} else if ((distance + firstСircle.r) <= secondCircle.r) {
return firstСircle.getAreaOfCircle()
} else {
const F1 = 2 * Math.acos(((firstСircle.r * firstСircle.r) - (secondCircle.r * secondCircle.r) + (distance * distance)) / (2 * firstСircle.r * distance));
const F2 = 2 * Math.acos(((secondCircle.r * secondCircle.r) - (firstСircle.r * firstСircle.r) + (distance * distance)) / (2 * secondCircle.r * distance));
const S1 = ((firstСircle.r * firstСircle.r) * (F1 - Math.sin(F1))) / 2;
const S2 = ((secondCircle.r * secondCircle.r) * (F2 - Math.sin(F2))) / 2;
return S1 + S2;
}
}
console.log(`Area of intersection of circles: ${getAreaOfIntersectionOfCircles(firstСircle, secondCircle).toFixed(2)}`);
ответ дан 7 ноя 2022 в 19:22
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Given the coordinates of the centers of two circles (X1, Y1) and (X2, Y2) as well as the radii of the respective circles R1 and R2. Find the floor of the area of their intersection.
Note: Use the value of Pi as 3.14
Examples:
Input: X1 = 0, Y1 = 0, R1 = 4, X2 = 6, Y2 = 0, R2 = 4
Output: 7
Explanation: The intersecting area equals 7.25298806. So, Answer is 7.Input: X1 = 0, Y1 = 0, R1 = 5, X2 = 11, Y2 = 0, R2 = 5
Output: 0
Explanation: The circles don’t intersect.
Approach: Follow the steps to solve this problem:
- Firstly calculate the euclidean distance between the two points and store it (say d).
- If, d > R1 + R2, then the circle never insects, so, return 0.
- Else if, d ≤ (R1 – R2) and R1 ≥ R2, then circle with radius R2 is inside the circle with radius R1, so, return floor(Pi * R2 * R2).
- Else if, d ≤ (R2 – R1) and R2 ≥ R1, then circle with radius R1 is inside the circle with radius R2, so, return floor(Pi * R1 * R1).
- Else, find:
- alpha = acos((R1 * R1 + d * d – R2 * R2) / (2 * R1 * d)) * 2 [acos is inverse cosine]
- beta = acos((R2 * R2 + d * d – R1 * R1) / (2 * R2 * d)) * 2
- a1 = 0.5 * beta * R2 * R2 – 0.5 * R2 * R2 * sin(beta)
- a2 = 0.5 * alpha * R1 * R1 – 0.5 * R1 * R1 * sin(alpha)
- Return, the value of floor(a1+a2).
Below is the implementation of the above approach.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return area of intersection
long long int
intersectionArea(long double X1, long double Y1,
long double R1, long double X2,
long double Y2, long double R2)
{
long double Pi = 3.14;
long double d, alpha, beta, a1, a2;
long long int ans;
// Calculate the euclidean distance
// between the two points
d = sqrt((X2 - X1) * (X2 - X1) + (Y2 - Y1) * (Y2 - Y1));
if (d > R1 + R2)
ans = 0;
else if (d <= (R1 - R2) && R1 >= R2)
ans = floor(Pi * R2 * R2);
else if (d <= (R2 - R1) && R2 >= R1)
ans = floor(Pi * R1 * R1);
else {
alpha = acos((R1 * R1 + d * d - R2 * R2)
/ (2 * R1 * d))
* 2;
beta = acos((R2 * R2 + d * d - R1 * R1)
/ (2 * R2 * d))
* 2;
a1 = 0.5 * beta * R2 * R2
- 0.5 * R2 * R2 * sin(beta);
a2 = 0.5 * alpha * R1 * R1
- 0.5 * R1 * R1 * sin(alpha);
ans = floor(a1 + a2);
}
return ans;
}
// Driver Code
int main()
{
int X1 = 0, Y1 = 0, R1 = 4;
int X2 = 6, Y2 = 0, R2 = 4;
// Function Call
cout << intersectionArea(X1, Y1, R1, X2, Y2, R2);
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
class GFG {
// Function to return area of intersection
static int intersectionArea(int X1, int Y1, int R1,
int X2, int Y2, int R2)
{
double Pi = 3.14;
double d, alpha, beta, a1, a2;
int ans;
// Calculate the euclidean distance
// between the two points
d = Math.sqrt((X2 - X1) * (X2 - X1)
+ (Y2 - Y1) * (Y2 - Y1));
if (d > R1 + R2)
ans = 0;
else if (d <= (R1 - R2) && R1 >= R2)
ans = (int)Math.floor(Pi * (double)R2
* (double)R2);
else if (d <= (R2 - R1) && R2 >= R1)
ans = (int)Math.floor(Pi * (double)R1
* (double)R1);
else {
alpha = Math.acos((R1 * R1 + d * d - R2 * R2)
/ (2 * R1 * d))
* 2;
beta = Math.acos((R2 * R2 + d * d - R1 * R1)
/ (2 * R2 * d))
* 2;
a1 = 0.5 * beta * R2 * R2
- 0.5 * R2 * R2 * Math.sin(beta);
a2 = 0.5 * alpha * R1 * R1
- 0.5 * R1 * R1 * Math.sin(alpha);
ans = (int)Math.floor(a1 + a2);
}
return ans;
}
public static void main(String[] args)
{
int X1 = 0, Y1 = 0, R1 = 4;
int X2 = 6, Y2 = 0, R2 = 4;
// Function Call
System.out.print(
intersectionArea(X1, Y1, R1, X2, Y2, R2));
}
}
// This code is contributed by lokeshmvs21.
Python3
# Python3 code to implement the approach
from math import sqrt, acos, floor, sin
# Function to return area of intersection
def intersectionArea(X1, Y1, R1, X2, Y2, R2) :
Pi = 3.14;
# Calculate the euclidean distance
# between the two points
d = sqrt(((X2 - X1) * (X2 - X1)) + ((Y2 - Y1) * (Y2 - Y1)));
if (d > R1 + R2) :
ans = 0;
elif (d <= (R1 - R2) and R1 >= R2) :
ans = floor(Pi * R2 * R2);
elif (d <= (R2 - R1) and R2 >= R1) :
ans = floor(Pi * R1 * R1);
else :
alpha = acos(((R1 * R1) + (d * d) - (R2 * R2)) / (2 * R1 * d)) * 2;
beta = acos(((R2 * R2) + (d * d) - (R1 * R1)) / (2 * R2 * d)) * 2;
a1 = (0.5 * beta * R2 * R2 ) - (0.5 * R2 * R2 * sin(beta));
a2 = (0.5 * alpha * R1 * R1) - (0.5 * R1 * R1 * sin(alpha));
ans = floor(a1 + a2);
return ans;
# Driver Code
if __name__ == "__main__" :
X1 = 0; Y1 = 0; R1 = 4;
X2 = 6; Y2 = 0; R2 = 4;
# Function Call
print(intersectionArea(X1, Y1, R1, X2, Y2, R2));
# This code is contributed by AnkThon
C#
// C# code to implement the approach
using System;
public class GFG{
// Function to return area of intersection
static int intersectionArea(int X1, int Y1, int R1,
int X2, int Y2, int R2)
{
double Pi = 3.14;
double d, alpha, beta, a1, a2;
int ans;
// Calculate the euclidean distance
// between the two points
d = Math.Sqrt((X2 - X1) * (X2 - X1)
+ (Y2 - Y1) * (Y2 - Y1));
if (d > R1 + R2)
ans = 0;
else if (d <= (R1 - R2) && R1 >= R2)
ans = (int)Math.Floor(Pi * (double)R2
* (double)R2);
else if (d <= (R2 - R1) && R2 >= R1)
ans = (int)Math.Floor(Pi * (double)R1
* (double)R1);
else {
alpha = Math.Acos((R1 * R1 + d * d - R2 * R2)
/ (2 * R1 * d))
* 2;
beta = Math.Acos((R2 * R2 + d * d - R1 * R1)
/ (2 * R2 * d))
* 2;
a1 = 0.5 * beta * R2 * R2
- 0.5 * R2 * R2 * Math.Sin(beta);
a2 = 0.5 * alpha * R1 * R1
- 0.5 * R1 * R1 * Math.Sin(alpha);
ans = (int)Math.Floor(a1 + a2);
}
return ans;
}
static public void Main (){
int X1 = 0, Y1 = 0, R1 = 4;
int X2 = 6, Y2 = 0, R2 = 4;
// Function Call
Console.WriteLine(
intersectionArea(X1, Y1, R1, X2, Y2, R2));
}
}
// This code is contributed by Pushpesh Raj.
Javascript
// JS code to implement the approach
// Function to return area of intersection
function
intersectionArea(X1,Y1,
R1, X2,
Y2, R2)
{
let Pi = 3.14;
let d, alpha, beta, a1, a2;
let ans;
// Calculate the euclidean distance
// between the two points
d = Math.sqrt((X2 - X1) * (X2 - X1) + (Y2 - Y1) * (Y2 - Y1));
if (d > R1 + R2)
ans = 0;
else if (d <= (R1 - R2) && R1 >= R2)
ans = Math.floor(Pi * R2 * R2);
else if (d <= (R2 - R1) && R2 >= R1)
ans = Math.floor(Pi * R1 * R1);
else {
alpha = Math.acos((R1 * R1 + d * d - R2 * R2)
/ (2 * R1 * d))
* 2;
beta = Math.acos((R2 * R2 + d * d - R1 * R1)
/ (2 * R2 * d))
* 2;
a1 = 0.5 * beta * R2 * R2
- 0.5 * R2 * R2 * Math.sin(beta);
a2 = 0.5 * alpha * R1 * R1
- 0.5 * R1 * R1 * Math.sin(alpha);
ans = Math.floor(a1 + a2);
}
return ans;
}
// Driver Code
let X1 = 0, Y1 = 0, R1 = 4;
let X2 = 6, Y2 = 0, R2 = 4;
// Function Call
console.log(intersectionArea(X1, Y1, R1, X2, Y2, R2));
//this code is contributed by ksam24000
Time Complexity: O(log N)
Auxiliary Space: O(1)
Last Updated :
23 Nov, 2022
Like Article
Save Article
Расчет площади пересечения окружностей методом Монте-Карло
Время на прочтение
4 мин
Количество просмотров 45K
Эта статья родилась как логическое продолжение пятничного поста о методе Бутстрапа, а особенно, комментариев к нему. Не защищая метод Бутстрапа, стоит уделить внимание методам Монте-Карло. Здесь я хочу поделиться своим опытом применения Монте-Карло в одной из своих практических задач, а также обоснованием законности этого применения.
Итак, моя задача заключалась в необходимости вычисления площади фигуры, являющейся пересечением окружностей, с последующей реализацией на языке JavaScript. Площадь под графиком – это интеграл. Интегрирование методом Монте-Карло достаточно широко известно, но, как многие верно заметят, его применение требует некоторого обоснования. За подробностями прошу под кат.
Обоснование
Задача расчета площади пересечения двух окружностей является тривиальной геометрической задачей (координаты центров окружностей и их радиусы нам известны). Площадь пересечения двух окружностей – это сумма площадей соответствующих сегментов этих окружностей. Есть решения для расчета площади пересечения двух, трех, четырех окружностей в различных частных случаях.
А вот решения общего случая для пересечения даже трех окружностей уже далеко не так тривиальны. В процессе поиска я нашел даже исследования по расчету площади пересечения N окружностей, однако они настолько же интересны, насколько и сложны.
Здесь на сцену выходит метод Монте-Карло. Благодаря современным компьютерным мощностям этот метод позволяет провести большое количество статистических испытаний, на основе результатов которых делается обобщение.
Итак, алгоритм расчета площади любой фигуры методом Монте-Карло сводится к следующему:
- Фигура вписывается в прямоугольник. Координаты сторон прямоугольника известны, значит, известна его площадь.
- Псевдослучайным образом внутри прямоугольника генерируется большое количество точек. Для каждой точки определяется, попала ли точка внутрь исходной фигуры или нет.
- В результате площадь исходной фигуры вычисляется исходя из обычной пропорции: отношение количества точек, попавших в фигуру, к общему количеству сгенерированных точек равно отношению площади фигуры к площади ограничивающего ее прямоугольника.
Последняя проблема, которую надо решить, заключается в том, что каким-то образом необходимо определять, попала ли точка внутрь исходной фигуры. В моем случае данная задача решается достаточно просто, поскольку моя фигура состоит из окружностей, координаты центров и радиусы которых известны.
Реализация задачи на JavaScript
Рисование окружностей делалось средствами замечательной библиотеки D3.js. Алгоритм начального взаимного расположения окружностей выходит за рамки данной статьи, поэтому примем начальное расположение как данность.
Собираем массив пересечений пар окружностей
var nodes = d3.selectAll("circle.node");
var squares = [];
var intersections = [];
nodes.each(function(node){
// считаем радиус и площадь окружности
var r = this.r.baseVal.value;
var s = 3.14159*r*r;
squares.push({node: node, square: s, r: r});
// ищем пересечения пар окружностей
nodes.each(function(node2){
// расстояние между центрами и сумма радиусов
var center_dist = Math.sqrt(Math.pow(node.x-node2.x, 2)+(Math.pow(node.y-node2.y, 2)));
var radius_sum = r + this.r.baseVal.value;
if(center_dist <= radius_sum && node.index != node2.index){
// окружности пересекаются. проверить, что это пересечение найдено впервые
node.r = r;
node2.r = this.r.baseVal.value;
if(isNewIntersection(intersections, node, node2))
intersections.push({node1: node, node2: node2, center_dist: center_dist});
}
});
});
Считаем площадь фигуры
var areaCalculator = {
intersections: [], // массив пересечений, устанавливается снаружи
frame: {}, // рамка вокруг фигуры
circles: [], // массив окружностей
figureArea: 0, // искомая площадь фигуры
monteCarlo:
function(p){
// получаем массив окружностей из пересечения
var circles = [];
var x1_, y1_, x2_, y2_; // координаты сторон прямоугольника
var inCirclesArr = function(node){
for(var j=0; j<circles.length; j++){
if(circles[j].index==node.index){
return true;
}
}
return false;
};
for(var i=0; i<this.intersections.length; i++){
if(!inCirclesArr(this.intersections[i].node1)){
circles.push(this.intersections[i].node1);
}
if(!inCirclesArr(this.intersections[i].node2)){
circles.push(this.intersections[i].node2);
}
}
this.circles = circles;
circles.sort(function(a,b){
return a.x-a.r > b.x-b.r ? 1 : -1;
});
x1_ = circles[0].x-circles[0].r;
circles.sort(function(a,b){
return a.x+a.r < b.x+b.r ? 1 : -1;
});
x2_ = circles[0].x+circles[0].r;
circles.sort(function(a,b){
return a.y-a.r > b.y-b.r ? 1 : -1;
});
y1_ = circles[0].y-circles[0].r;
circles.sort(function(a,b){
return a.y+a.r < b.y+b.r ? 1 : -1;
});
y2_ = circles[0].y+circles[0].r;
this.frame.x1 = x1_;
this.frame.x2 = x2_;
this.frame.y1 = y1_;
this.frame.y2 = y2_;
this.frame.area = (x2_-x1_)*(y2_-y1_);
// рисуем прямоугольник
paintRect(this.frame);
// p - количество генерируемых точек. В примере использовалось 100.000, чего хватило для приемлемой точности
var p_positive = 0; // количество точек попавших в фигуру
// генерируем p точек для определения площади фигуры
for(var i=0; i<p; i++){
var x_rand = Math.random()*(x2_-x1_)+x1_;
var y_rand = Math.random()*(y2_-y1_)+y1_;
var yes = false;
for(var j=0; j<circles.length; j++) {
if(!yes && (
(circles[j].x-circles[j].r) <= x_rand &&
(circles[j].x+circles[j].r) >= x_rand &&
(circles[j].y-circles[j].r) <= y_rand &&
(circles[j].y+circles[j].r) >= y_rand )
){
yes = true;
p_positive++;
}
}
}
// площадь фигуры = площадь прямоугольника*кол-во точек внутри фигуры / общее кол-во точек
this.figureArea = this.frame.area*p_positive/p;
}
};
Пара гвоздей в метод Бутстрапа
Если говорить именно о методе Бутстрапа, то мое личное мнение заключается в том, что случайная генерация набора данных по имеющемуся набору в общем случае не может служить для оценки закономерностей, поскольку сгенерированная информация не является достоверной. В общем, это же, только более умными (и нередко более резкими) словами, говорят и многие авторы, например, Орлов в своем учебнике по Эконометрике.
Заключение
Методы Монте-Карло являются вполне жизнеспособными и весьма полезными в некоторых случаях, как, например, в моем. Возможности современных компьютеров, даже обычных настольных машин, вполне позволяют оперировать подобными статистическими методами с достаточно большим количеством испытаний и, соответственно, получать достаточную точность результата. Но при всем этом, конечно, они являются лишь упрощением модели и не могут претендовать на что-то большее.
Виктор – неправильно 🙂 Вы посчитали разность площадей двух окружностей, что никакого отношению не имеет к их данной диспозиции.
Я сейчас немного почеркала на листочке, формула получается немного громоздкая, писать ее не буду, но дам совет, как посчитать.
Искомая площадь есть сумма площадей двух сегментов, образованных от каждой окружности путем отсечения части окружности хордой, проведенной через точки пересечения окружностей.
Площадь сегмента есть разница между площадью сектора, заключенного между радиусами и дугой, заключенной между точками пересечения окружностей, и треугольника, построенного на радиусах и хорде, стягивающей упоминаемую дугу.
Нам потребуется длина той части А, которая находится в искомой площади, назовем ее Х. Она равно R1+R2-A.
Площадь треугольника – половина произведения основания на высоту. Высота находится легко: это разность между радиусом, и той частью Х, что заключена между точкой пересечения мередианного (для сектора) радиуса с окружностью и с хордой, стягивающей дугу между точками пересечения окружностей. Эта самая часть для большей окружности равна Х/2 умноженная на отношение радиуса меньшей окружности к радиусу большей окружности; для меньшей окружности эта часть рана Х/2 умноженная на отношение радиуса большей окружности к радиусу меньшей.
Зная высоту и стороны треугольника, находим основание по правилу прямоугольного треугольника и попутно значение угла, стягиваемого упоминаемой дугой (это уже элементарная геометрия).
Далее находим площадь треугольника и площадь сектора ((пи х радиус в квадрате х величину угла в градусах)/360), и из их разности площадь сегмента.
Проделываем эту процедуру для каждой окружности и складываем полученные площади. Искомая площадь найдена 🙂
