Размещено на http://www.allbest.ru/

Декартовы координаты

координатные оси (на плоскости это оси абсцисс - ось X и ординат - ось Y);

координаты точки- пара чисел (x - абсцисса, y - ордината), описывающая положение точки;

Расстояние между точками

Если даны две точки на оси абсцисс, то расстояние между ними равно модулю (абсолютной величине) разности абсцисс этих точек d=|x1-x2|. Соответственно, для точек на оси ординат надо брать модуль разности ординат d=|y1-y2|.

Для произвольных точек и расстояние вычисляется по теореме Пифагора и равно .

Заметим, что, если абсциссы (или ординаты точек равны), то расстояние оказывается равным просто модулю разности других координат, как для точек на осях координат.

расстояние точка отрезок вектор

Середина отрезка

Точка с координатами, равными среднему арифметическому абсцисс и среднему арифметическому ординат, является серединой отрезка с концами в данных точках, т.е. точка - середина отрезка, соединяющего точки и .

Сразу отметим более общий факт. Если есть несколько точек, то точка с координатами, равными среднему арифметическому всех абсцисс и среднему арифметическому всех ординат, является центром тяжести данных точек. В частности, центр тяжести вершин треугольника - это точка пересечения медиан. В любом выпуклом многоугольнике - центр тяжести заведомо лежит внутри этого многоугольника.

Упражнение 1

Формула расстояния между точками сразу дает нам уравнение окружности данного радиуса R с центром в заданной точке O(X, Y):

Действительно, любая пара (x, y), удовлетворяющая этому уравнению, задает координаты точки, удаленной на расстояние R от точки O(X, Y). Заметим, что квадратный корень, который присутствует в формуле расстояния, здесь не нужен, потому что вместо R мы берем R2.

Упражнение 5

Вектор v = (x, y) - направленный отрезок, идущий из начала координат в точку (x, y) или любой другой равный и сонаправленный ему;

Скалярное произведение векторов v = (x1, y1) и w = (x2, y2), равное произведению длин векторов на косинус угла между ними , или, через координаты: .

1. Скалярное произведение ненулевых векторов равно нулю тогда и только тогда, когда векторы перпендикулярны.

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

Упражнение 6

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

Длина векторного произведения векторов v=(x1, y1) и w=(x2, y2), равно произведению длин векторов на синус угла между ними , или, через координаты: . Длина векторного произведения численно равна площади параллелограмма, построенного на перемножаемых векторах v и w как на сторонах.

1. Векторное произведение ненулевых векторов равно нулю тогда и только тогда, когда векторы параллельны.

2. При общей начальной точке у двух векторов их векторное произведение больше нуля, если второй вектор направлен влево от первого, и меньше нуля, если вправо.

Упражнение 7

Полярный угол точки (x,y) может быть вычислен через арктангенс:

{возвращается число из диапазона [0,2]}

PolarAngle:=arctan2(y,x);

if y<0 then PolarAngle:=2*pi+PolarAngle;

Прямая

В школе чаще всего уравнение прямой дается в следующем виде:

Это, так называемое, уравнение прямой с угловым коэффициентом. Использование этого уравнения при программировании сопряжено с опасностью в случае, если приходится работать с вертикальными прямыми. При этом угловой коэффициент k должен принимать бесконечное значение, что может привести к ошибке.

Чаще применяется уравнение прямой в общем виде:

A, B, C - некоторые числа, причем A и B одновременно не равны нулю (в этом случае, вообще, никакого уравнения не остается). Итак, мы видим, что уравнение прямой - это просто некоторое линейное уравнение.

Задать прямую - значит задать ее коэффициенты. Коэффициенты же, как правило, выбираются из некоторых дополнительных соображений. Например, если надо, чтобы прямая проходила через заданную точку , можно написать: Действительно, координаты точки M превращают это уравнение в тождество: 0 = 0.

При этом, если надо получить уравнение в общем виде, то следует раскрыть скобки и привести подобные члены, при этом, коэффициент при x будет равен A, при y: B, а свободный член будет равен .

Если надо, чтобы прямая проходила через две заданные точки и , выписывается линейная функция, принимающая значение y1 в точке x1 и значение y2 в точке x2. Уравнение прямой проходящей через две заданные точки:

Для общей формулы уравнения прямой Ax+By+C=0, имеем A=y2-y1, B=x1-x2, C=-x1·A-y1·B.

Полуплоскости

Точки, в которых левая часть уравнения прямой положительна, образуют положительную полуплоскость, а в которых отрицательна - отрицательную полуплоскость.

Если точки (x1,y1) и (x2,y2) лежат по разные стороны от заданной прямой Ax+By+C=0,

(Ax1+By1+C)( Ax2+By2+C)<0.

Пересечение двух прямых

Чтобы найти точку пересечения двух прямых, надо решить систему из двух соответствующих линейных уравнений

A1x+B1y+C1=0,

A2x+B2y+C2=0.

Решаем методом Крамера:

d=A1·B2 - A2·B1, dx=-C1·B2 + C2·B1, dy=-A1·C2 + A2·C1,

x=dx/d, y=dy/d.

Если d=0, прямые не пересекаются (параллельны или совпадают).

Параллельные прямые

Ясно, что прямые и не имеют общих точек, если , поэтому для построения прямой, параллельной данной, достаточно задать у нее такие же коэффициенты при x и y, как и у исходной прямой.

Вектор, параллельный данной прямой

Если провести прямую через начало координат, то ее уравнение будет . При этом точка , как и точка , будут лежать на этой прямой, а значит, вектора с такими координатами параллельны прямой .

Вектор, перпендикулярный данной прямой

Нетрудно убедиться, что скалярное произведение векторов (A, B) и равно , что означает их перпендикулярность, а значит, вектор (A, B) перпендикулярен прямой .

Отсюда, в частности, следует, что прямая перпендикулярна прямой .

Упражнение 8

Найдите уравнение прямой, равноудаленной от двух заданных точек и .

Решение 1. Искомая прямая является перпендикулярной к отрезку MN и проходит через его середину. Поэтому выпишем сначала уравнение прямой, проходящей через точки M и N:

Видим, что коэффициент при x равен , а при y равен . Уравнение прямой, перпендикулярной данной, будет иметь при x и при y коэффициенты, равные, соответственно, и . А, чтобы эта прямая проходила через середину отрезка MN, надо, чтобы она имела уравнение:

.

Решение 2. Запишем формулы расстояний от точки (x, y) до заданных точек и приравняем их. Получим: (x - x1)2 + (y - y1)2 = (x - x2)2 + (y - y2)2. После раскрытия скобок квадраты сокращаются и остается искомое уравнение.

Упражнение 9

Найдите центр описанной около данного треугольника окружности.

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

Угол между двумя прямыми

Угол между двумя прямыми A1·x + B1·y + C1 = 0 и A2·x + B2·y + C2 = 0 равен углу между перпендикулярными им векторами, т.е. (A1, B1) и (A2, B2). Используя формулу скалярного произведения, получаем:

Уравнение прямой в нормальной форме

Если у уравнения прямой оказывается, что , то это уравнение называется нормальным, и оно обладает важным свойством: при подстановке в это уравнение координат любой точки плоскости левая часть оказывается равной расстоянию от этой точки до данной прямой. Причем, для точек одной полуплоскости это расстояние получается положительным, а для точек другой полуплоскости - отрицательным. Здесь мы этот важный факт оставляем без доказательства.

Итак, чтобы узнать расстояние от точки до прямой, надо координаты точки подставить в нормальное уравнение прямой. Чтобы получить нормальное уравнение прямой из произвольного имеющегося, надо разделить его на . Убедитесь, что после такого деления сумма квадратов коэффициентов при x и y станет равна 1.

Упражнение 10

Определите расстояние от точки (2, 6) до прямой .

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

Упражнение 11

Заданы уравнения двух прямых: A1·x + B1·y + C1 = 0 и A2·x + B2·y + C2 = 0

Определите уравнение биссектрисы угла, образованного ими. Сколько решений имеет задача?

Подсказка. Биссектриса - это прямая, каждая точка которой одинаково удалена от каждой из данных прямых. Поэтому достаточно приравнять эти расстояния (см. упражнение 10).

Упражнение 12

Найдите центр описанной около данного треугольника окружности.

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

Площади

1. Существует много формул для площади треугольников, каждая из которых может применяться. Все зависит от того, какими данными мы располагаем. Однако, чтобы найти площади других многоугольников, редко удается применить формулы для площадей треугольников. Чаще всего используется формула, использующая формулу площади трапеции на координатной плоскости. Приведем эту формулу с краткими пояснениями.

Пусть на плоскости задан отрезок с координатами концов: (x1, y1) и (x2, y2). Площадь трапеции, основаниями которой являются перпендикуляры, опущенные из концов отрезка на ось X, равна произведению полусуммы оснований на высоту, т.е. .

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

.

Каждое слагаемое в этой формуле равно площади трапеции, лежащей под соответствующей стороной многоугольника. Поэтому площадь, лежащая под самим многоугольником прибавляется к общей сумме, когда мы проходим «верхние» вершины и вычитается, когда мы проходим «нижние» вершины. Остается только площадь самого многоугольника.

Нарисуйте какой-нибудь многоугольник на координатной плоскости и убедитесь, что вы все поняли правильно.

2. Формула Пика. Если вершины многоугольника расположены в точках с целочисленными координатами, то выполнено следующее равенство:

S=I+B/2-1,

где S - площадь многоугольника, I - число целых точек, лежащих внутри многоугольника, B - число целых точек, лежащих на границе многоугольника.

Построение выпуклой оболочки

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

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

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

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

Метод трассировки луча

Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно -- то снаружи. Это основано на том простом наблюдении, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника. Алгоритм известен под такими названиями, как crossing number (count) algorithmили even-odd rule.

В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет. Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец -- выше или лежит на луче.

Алгоритм работает за время O(N) для N-угольника.

Размещено на Allbest.ru