Геометрические задачи
Вычислительная геометрия – это раздел информатики, изучающий алгоритмы решения геометрических задач. Такие задачи возникают в компьютерной графике, проектировании интегральных схем, технических устройств и др. Исходными данными в такого рода задачах могут быть множество точек, набор отрезков, многоугольники и т.п. Результатом может быть либо ответ на какой-то вопрос, либо какой-то геометрический объект.
Для построения фигур зачастую используют вектора в ПДСК. И на их основе выводятся формулы для вычисления, чаще всего используют векторное произведение.
Скалярное произведение векторов — это число, равное произведению длин этих векторов на косинус угла между ними.
(а, b) = |а|·|b|·соs∠(а, b)
В случае, когда векторы задаются координатами a( x1, y1), b( x2, y2), скалярное произведение (a, b) = x1·x2+ y1·y2.
Существует также понятие псевдоскалярного (косого) произведения:
[а, b] = |а|·|b|·sin(α)
где α — угол вращения (против часовой стрелки) от a к b. При условии того что а или b равны нулевому вектору, то принято считать что [а, b] = 0.
В случае, когда векторы задаются координатами a a( x1, y1), b( x2, y2) то косое произведение [а, b] = x1·y2 — y1·x2.
Геометрически косое произведение векторов представляет собой ориентированную площадь параллелограмма, натянутого на эти вектора.
В задачах вычислительной геометрии псевдоскалярное произведение отводится к числу избранных. Оно считается неким Экскалибуром. Это связано с тем, что решение с использованием псевдоскалярного произведения является намного проще любого другого.
Скалярное произведение векторов — это число, равное произведению длин этих векторов на косинус угла между ними.
(а, b) = |а|·|b|·соs∠(а, b)
В случае, когда векторы задаются координатами a( x1, y1), b( x2, y2), скалярное произведение (a, b) = x1·x2+ y1·y2.
Существует также понятие псевдоскалярного (косого) произведения:
[а, b] = |а|·|b|·sin(α)
где α — угол вращения (против часовой стрелки) от a к b. При условии того что а или b равны нулевому вектору, то принято считать что [а, b] = 0.
В случае, когда векторы задаются координатами a a( x1, y1), b( x2, y2) то косое произведение [а, b] = x1·y2 — y1·x2.
Геометрически косое произведение векторов представляет собой ориентированную площадь параллелограмма, натянутого на эти вектора.
В задачах вычислительной геометрии псевдоскалярное произведение отводится к числу избранных. Оно считается неким Экскалибуром. Это связано с тем, что решение с использованием псевдоскалярного произведения является намного проще любого другого.
Вычислительная геометрия на плоскости требует от учащихся знаний формул математики. Таких как:
cos( β-α ) выражается через координаты (ax;ay) и (bx;by) и длины la;lb:
Выражение (ax·by - bx·ay) играет весьма важную роль. Если оно отрицательно, угол поворота вектора a к вектору b направлен по часовой стрелке (вправо), а если положительно – против (влево). Если оно равно 0, векторы коллинеарны.
Из равенства ax·by - bx·ay=la·lb·sin(β-α) следует, что ax·by - bx·ay выражает ориентированную площадь параллелограмма, образованного векторами a и b. Она отрицательна, если кратчайшее движение от вектора a к вектору b направлено вправо, иначе положительна. Ориентированная площадь треугольника, образованного векторами, равна половине площади параллелограмма, то есть 1/2(xa·yb - ya·xb); её знак определяется так же, как для параллелограмма.
Из равенства ax·by - bx·ay=la·lb·sin(β-α) следует, что ax·by - bx·ay выражает ориентированную площадь параллелограмма, образованного векторами a и b. Она отрицательна, если кратчайшее движение от вектора a к вектору b направлено вправо, иначе положительна. Ориентированная площадь треугольника, образованного векторами, равна половине площади параллелограмма, то есть 1/2(xa·yb - ya·xb); её знак определяется так же, как для параллелограмма.
В случае, если вектор задан длиной и углом выразить поворот очень просто. А если вектор задан координатами необходимо для начала выразить координаты повернутого вектора через координаты заданного:
Аналогично
Таким образом, из «тригонометрических операций» нужны только cos(φ) и sin(φ).
Представление прямой в задачах обычно приходится строить по двум точкам, через которые она проходит. По заданным точкам (x0;y0) и (x1;y1) и произвольной точке прямой (x;y) с помощью пропорции получается уравнение:
Представление прямой в задачах обычно приходится строить по двум точкам, через которые она проходит. По заданным точкам (x0;y0) и (x1;y1) и произвольной точке прямой (x;y) с помощью пропорции получается уравнение:
Таким образом, из «тригонометрических операций» нужны только cos(φ) и sin(φ).
Представление прямой в задачах обычно приходится строить по двум точкам, через которые она проходит. По заданным точкам (x0;yo) и (x1;y1) и произвольной точке прямой (x;y) с помощью пропорции получается уравнение:
Представление прямой в задачах обычно приходится строить по двум точкам, через которые она проходит. По заданным точкам (x0;yo) и (x1;y1) и произвольной точке прямой (x;y) с помощью пропорции получается уравнение:
Если прямая не вертикальна, то есть Xo≠X1, можно разделить общее уравнение почленно на X1-Xo и прийти к уравнению с угловым коэффициентом:
В уравнении вида угловой коэффициент y=k·x+d выражает тангенс угла наклона прямой к горизонтали, смещение d – значение у при х=0. Угол наклона α отсчитывается от оси Ох; диапазоном значений α можно считать либо 0 ≤ α ≤ ℼ (исключая ℼ/2), либо -(ℼ/2) ≤ α ≤ ℼ/2 .
- Вектор с координатами (А;В) перпендикулярен прямой, заданной общим уравнением Ах+Ву+С=0.
- Если прямая задана общим уравнением Ах+Ву+С=0 и для нее нужно получить систему с направляющим вектором, то в качестве вектора можно взять (-В;А); остается только подобрать начальную точку.
- Если прямая задана системой с направляющим вектором (ax;ay), то в общем уравнении этой прямой в качестве коэффициентов можно взять A= -ay и В= ax ; остается подобрать С так, чтобы прямая проходила через начальную точку.
Пример геометрической задачи:
Два соседа-фермера получили во владение по участку в виде круга. Возникло подозрение, что часть территории принадлежит обоим фермерам. Они не стали судиться, а объединились в кооператив, чтобы совместно использовать всю полученную землю. Какая площадь оказалась в распоряжении кооператива?
Входные данные:
В строке текста шесть вещественных чисел через пробел: координаты центра и радиус одного круга, затем то же – другого. Все числа по модулю не больше 10^16 и содержат не больше трех знаков после запятой.
Выходные данные:
Одно число в экспоненциальной форме без округления и с возможной погрешностью не больше 10^(-3).
Пример
Входные данные: 0 0 17 0 21 10.
Выходные данные: 1.15575235315894Е+0003.
- Вектор с координатами (А;В) перпендикулярен прямой, заданной общим уравнением Ах+Ву+С=0.
- Если прямая задана общим уравнением Ах+Ву+С=0 и для нее нужно получить систему с направляющим вектором, то в качестве вектора можно взять (-В;А); остается только подобрать начальную точку.
- Если прямая задана системой с направляющим вектором (ax;ay), то в общем уравнении этой прямой в качестве коэффициентов можно взять A= -ay и В= ax ; остается подобрать С так, чтобы прямая проходила через начальную точку.
Пример геометрической задачи:
Два соседа-фермера получили во владение по участку в виде круга. Возникло подозрение, что часть территории принадлежит обоим фермерам. Они не стали судиться, а объединились в кооператив, чтобы совместно использовать всю полученную землю. Какая площадь оказалась в распоряжении кооператива?
Входные данные:
В строке текста шесть вещественных чисел через пробел: координаты центра и радиус одного круга, затем то же – другого. Все числа по модулю не больше 10^16 и содержат не больше трех знаков после запятой.
Выходные данные:
Одно число в экспоненциальной форме без округления и с возможной погрешностью не больше 10^(-3).
Пример
Входные данные: 0 0 17 0 21 10.
Выходные данные: 1.15575235315894Е+0003.
