Геометрические задачи, решаемые аналитически при помощи приемов алгебры, являются неотъемлемой частью программы школьного обучения. Кроме логического и пространственного мышления они развивают понимание ключевых взаимосвязей между сущностями окружающего мира и абстракциями, применяемыми людьми для формализации отношений между ними. Нахождение точек пересечения простейших геометрических фигур - один из типов подобных задач.
Предположим, что даны две окружности, заданные своими радиусами R и r, а также координатами их центров - соответственно (x1, y1) и (x2, y2). Требуется вычислить, пересекаются ли эти окружности, и если да, то найти координаты точек пересечения .Для простоты можно предположить, что центр одной из заданных окружностей совпадает с началом координат. Тогда (x1, y1) = (0, 0), а (x2, y2) = (a, b). Также имеет смысл предполагать, что a ? 0 и b ? 0.
Таким образом, координаты точки (или точек) пересечения
окружностей
, если они есть, должны удовлетворять системе из двух уравнений:x^2 + y^2 = R^2,
(x - a)^2 + (y - b)^2 = r^2.
После раскрытия скобок уравнения приобретают вид:x^2 + y^2 = R^2,
x^2 + y^2 - 2ax - 2by + a^2 + b^2 = r^2.
Теперь первое уравнение можно вычесть из второго. Таким образом, квадраты переменных исчезают, и возникает линейное уравнение: -2ax - 2by = r^2 - R^2 - a^2 - b^2. С его помощью можно выразить y через x:y = (r^2 - R^2 - a^2 - b^2 - 2ax)/2b.
Если подставить найденное выражение для y в уравнение окружности, задача сводится к решению квадратного уравнения: x^2 + px + q = 0, гдеp = -2a/2b,
q = (r^2 - R^2 - a^2 - b^2)/2b - R^2.
Корни этого уравнения позволят найти координаты точек пересечения окружностей . Если уравнение неразрешимо в действительных числах, то окружности не пересекаются. Если корни совпадают между собой, то окружности касаются друг друга. Если корни различны, то окружности пересекаются.
Если a = 0 или b = 0, то исходные уравнения упрощаются. Например, при b = 0 система уравнений примет вид:x^2 + y2 = R^2,
(x - a)^2 + y^2 = r^2.
После вычитания первого уравнения из второго получается:- 2ax + a^2 = r^2 - R^2.Его решение: x = - (r^2 - R^2 - a2)/2a. Очевидно, что в случае b = 0 центры обеих окружностей лежат на оси абсцисс, и у точек их пересечения будет одинаковая абсцисса.
Если a = 0 и b = 0, но при этом R ? r, то одна из окружностей заведомо находится внутри другой, и точки пересечения отсутствуют. Если же R = r, то окружности совпадают, и точек их пересечения бесконечно много.
Если ни у одной из двух окружностей
центр не совпадает с началом координат, то их уравнения будут иметь вид:(x - x1)^2 + (y - y1)^2 = R^2,
(x - x2)^2 + (y - y2)^2 = r^2.Если перейти к новым координатам, получающимся из старых методом параллельного переноса: x? = x + x1, y? = y + y1, то эти уравнения приобретают вид:x?^2 + y?^2 = R^2,
(x? - (x1 + x2))^2 + (y? - (y1 + y2))^2 = r^2.Задача, таким образом, сводится к предыдущей. Найдя решения для x? и y?, можно легко вернуться к изначальным координатам, обратив уравнения для параллельного переноса.
Итак, моя задача заключалась в необходимости вычисления площади фигуры, являющейся пересечением окружностей, с последующей реализацией на языке JavaScript. Площадь под графиком – это интеграл. Интегрирование методом Монте-Карло достаточно широко известно, но, как многие верно заметят, его применение требует некоторого обоснования. За подробностями прошу под кат.
А вот решения общего случая для пересечения даже трех окружностей уже далеко не так тривиальны. В процессе поиска я нашел даже исследования по расчету площади пересечения N окружностей , однако они настолько же интересны, насколько и сложны.
Здесь на сцену выходит метод Монте-Карло . Благодаря современным компьютерным мощностям этот метод позволяет провести большое количество статистических испытаний, на основе результатов которых делается обобщение.
Итак, алгоритм расчета площади любой фигуры методом Монте-Карло сводится к следующему:
Собираем массив пересечений пар окружностей
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 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;
}
};
Пусть заданы две окружности своими уравнениями: (X-X A) 2 +(Y-Y A) 2 =S 2 A ; (X-X B) 2 +(Y-Y B) 2 =S 2 B
. При этом точка А
с координатами (X A; Y A)
есть центр первой окружности, а S A
-радиус этой окружности. Соответственно точка В
с координатами (X B; Y B)
- центр второй окружности, аS B
-радиус второй окружности. Определение координат точек пересечения этих окружностей (а их в общем случае две) можно получить решением представленных уравнений. Однако, с точки зрения вычислительной, такой метод решения является достаточно трудоемким. В связи с этим воспользуемся несколько иным приемом и будем вычислять не координаты искомых точек, а приращения координат относительно центров заданных окружностей. Рассмотрим внимательно рис. 2.3. Для определения координат т. Q
необходимо знать дирекционный угол направления AQ
ирасстояние между этими точками А
и Q
. Решая прямую геодезическую задачу, мы можем найти координаты точки Q.
Расстояние от точки А
до точки Q
известно - это радиус первой окружности S A
. Дирекционный угол направления AQ
может быть вычислен по формуле α AQ =α AB -β A (2.13) Если искомая точка Q находится СЛЕВА от исходного направления АВ, то дирекционный угол получают как РАЗНОСТЬ;
Если искомая точка F находится СПРАВА от исходного направления АВ, то дирекционный угол получают как СУММУ.
Второе правило мы будем использовать при нахождении дирекционного угла направленияAF
:. α AF =α AB +β A (2.14) Дирекционный угол α AB направления АВ
получим из решения обратной геодезической задачи по известным координатам точек А
и В.
Остается решить вопрос относительно вычисления угла β A . Аналогичные рассуждения мы можем провести по поводу вычисления приращений координат по линиям BQ
и BF
. Длины линий BQ
и BF
равны радиусу второй окружности S B , а дирекционные углы этих направлений могут быть вычислены по формулам: α BA =α BA +β B ; (2.15) α BF =α BA -β B . (2.16) Рис.2.3. Определение координат точек пересечения двух окружностей.
Обратите внимание на знаки, с которыми угол β B входит в эти формулы! Вспомните, как вычислить дирекционный угол α BA
, если известен дирекционный угол α AB
. Здесь также остается открытым вопрос о величине угла β B
. Вычисление этих углов может быть осуществлено по формулам: Вспомните, почему треугольники AKQ
и BKQ
- прямоугольные! Учитывая, что для указанных треугольников QK -
общий катет, можем записать следующее равенство: S 2 A -AK 2 =S 2 B -BK 2
. Приписав к последнему равенству очевидное равенство AK+BK=AB,
получим систему из двух уравнений с двумя неизвестными. Решив эту систему (решение выполнить самостоятельно), получим Контроль вычислений можно осуществить по формуле AK+BK=AB.
Применяя формулы (2.17) и (2.18), вычисляем вспомогательные углы βи β B . Затем по формулам (2.14) - (2.16) вычисляем дирекционные углы направлений AQ
, AF
, BQ
и BF
. Далее по формулам вычисляем приращения координат и с контролем координаты точек Q
и F
.Пара гвоздей в метод Бутстрапа
Если говорить именно о методе Бутстрапа, то мое личное мнение заключается в том, что случайная генерация набора данных по имеющемуся набору в общем случае не может служить для оценки закономерностей, поскольку сгенерированная информация не является достоверной. В общем, это же, только более умными (и нередко более резкими) словами, говорят и многие авторы, например,