Геометрические задачи, решаемые аналитически при помощи приемов алгебры, являются неотъемлемой частью программы школьного обучения. Кроме логического и пространственного мышления они развивают понимание ключевых взаимосвязей между сущностями окружающего мира и абстракциями, применяемыми людьми для формализации отношений между ними. Нахождение точек пересечения простейших геометрических фигур - один из типов подобных задач.
Инструкция
Предположим, что даны две окружности, заданные своими радиусами 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 окружностей , однако они настолько же интересны, насколько и сложны.
Здесь на сцену выходит метод Монте-Карло . Благодаря современным компьютерным мощностям этот метод позволяет провести большое количество статистических испытаний, на основе результатов которых делается обобщение.
Итак, алгоритм расчета площади любой фигуры методом Монте-Карло сводится к следующему:
- Фигура вписывается в прямоугольник. Координаты сторон прямоугольника известны, значит, известна его площадь.
- Псевдослучайным образом внутри прямоугольника генерируется большое количество точек. Для каждой точки определяется, попала ли точка внутрь исходной фигуры или нет.
- В результате площадь исходной фигуры вычисляется исходя из обычной пропорции: отношение количества точек, попавших в фигуру, к общему количеству сгенерированных точек равно отношению площади фигуры к площади ограничивающего ее прямоугольника.
Реализация задачи на 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
Пара гвоздей в метод Бутстрапа
Если говорить именно о методе Бутстрапа, то мое личное мнение заключается в том, что случайная генерация набора данных по имеющемуся набору в общем случае не может служить для оценки закономерностей, поскольку сгенерированная информация не является достоверной. В общем, это же, только более умными (и нередко более резкими) словами, говорят и многие авторы, например,Пусть заданы две окружности своими уравнениями: (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 .