Вектор (он же точка) - основная сущность, необходимая для решения задач по вычислительной геометрии. Всегда удобно реализовать вектор и операции с ним в виде класса. Ниже приведена реализация класса точки и некоторого набора операций на языке Java:
class Point {
 double x, y;
 
 //конструкторы
 public Point() {
  this.x = 0;
  this.y = 0;
 }
 
 public Point(double x, double y) {
  this.x = x;
  this.y = y;
 }
 
 //сложение векторов
 public Point add(Point other) {
  return new Point(x + other.x, y + other.y);
 }
 
 //вычитание
 public Point substract(Point other) {
  return new Point(x - other.x, y - other.y);
 }
 
 //длина вектора
 public double length() {
  return Math.sqrt(x * x + y * y);
 }
 
 //умножение на константу
 public Point multiply(double d) {
  return new Point(d * x, d * y);
 }
 
 //скалярное произведение
 public double dotProd(Point other) {
  return x * other.x + y * other.y;
 }
 
 //векторное произведение
 public double crossProd(Point other) {
  return x * other.y - y * other.x;
 }
 
 //поворот на угол ang радиан против часовой стрелки
 public Point rotate(double ang) {
  return new Point(x * Math.cos(ang) - y * Math.sin(ang),x * Math.sin(ang) + y * Math.cos(ang));
 }
 
 //поворот на прямой угол против часовой стрелки
 public Point rotate90(double ang) {
  return new Point(-y, x);
 }
 
 //расстояние между точками
 public double distTo(Point other) {
  return this.subsract(other).len();
 }
 
 //угол между векторами (в радианах)
 public double angleTo(Point other) {
  return Math.atan2(this.crossProd(other), this.dotProd(other));
 }
 
 //возвращает нормированный вектор (то же направление, длина равна 1)
 public Point norm() {
  return this.multiply(1.0 / this.length());
 }
}
public double toRadians(double degreeAng) {
 return degreeAng / 180.0 * Math.PI;
}
public double toDegrees(double radAng) {
 return radAng / Math.PI * 180.0;
}
Рекомендуется реализовывать этот класс так же и на других языках (реализуя операции методами). В некоторых языках, например C++, можно для удобства вместо методов использовать операторы, например:
struct point {
 double x, y;
 point() : x(0), y(0) {};
 point(double _x, double _y) : x(_x), y(_y) {};
 point operator + (point other) {
  point *p = new point(x + other.x, y + other.y);
  return *p;
 }
 point operator - (point other) {
  ...
 }
 ...
}
Можно писать без указателей и new:
point operator + (point other) {
 point w(x + other.x, y + other.y);
 return w;
}
или так:
point operator + (point other) {
 point w;
 w.x = x + other.x;
 w.y = y + other.y;
 return w;
}
Тогда для сложения можно писать p1 + p2 вместо p1.add(p2), аналогично остальное.
Почти всегда для решения задачи по геометрии не требуется ничего кроме векторов и перечисленных операций. Кроме тривиальных операций вроде сложения, умножения на константу и т.п., полезны операции скалярного и векторного (псевдоскалярного произведения). Пусть есть два вектора: u с координатами x1 и y1, v с координатами x2, y2. Тогда скалярное произведение u · v = |u| * |v| * cos(a), где |u| - длина, a - направленный угол от вектора u к вектору v. Скалярное произведение хорошо выражается через координаты: u · v = x1 * x2 + y1 * y2. Векторное произведение u * v = |u| * |v| * sin(a), в тех же обозначениях. В координатах, u * v = x1 * y2 - y1 * x2.
Эти операции хороши потому, что с одной стороны хорошо выражаются через координаты векторов, поэтому их вычисление не приводит к большому увелечению погрешности, такому, как при использовании тригонометрических и других подобных функций; а при целочисленных координатах векторов эти произведения вообще целые. С другой стороны, скалярное и векторное произведения включают в себя синус и косинус угла между векторами, то есть всю информацию об их взаимоположении. Например, чтобы проверить, с какой стороны от вектора u находится вектор v, достаточно посмотреть на знак векторного произведения: он совпадает со знаком синуса угла между векторами, который совпадает просто со знаком угла, соответственно векторное произведение u * v положительно тогда и только тогда, когда угол между u и v положительный, то есть вектор v находится справа от вектора u.
boolean isToTheRight(Point u, Point v) {
 return u.crossProd(v) > 0;
}
Аналогично, по знаку скалярного произведения можно определить острый, прямой или тупой угол между векторами: соответственно при положительном, нулевом и отрицательном скалярном произведении.
С помощью векторного и скалярного произведения можно проверить, принадлежит ли точка отрезку:
//p - проверяемая точка, a, b - концы отрезка
boolean isOnSegment(Point p, Point a, Point b) {
 Point l = b.substract(a);
 return l.crossProd(p.substract(a)) == 0 && l.dotProd(p.substract(a)) >= 0 && l.multiply(-1).dotProd(p.substract(b)) >= 0;
}
l.crossProd(p.substract(a)) == 0 - проверяем коллинеарность векторов b - a и p - a, то есть то, что точки a, b и p лежат на одной прямой
l.dotProd(p.substract(a)) >= 0 - проверяем, что угол между p - a и b - a острый, то есть что p лежит по ту же сторону от точки a, что и b
l.multiply(-1).dotProd(p.substract(b)) >= 0 - то же, только для точки b
Таким образом, мы представляем отрезок как пересечение прямой ab, полуплоскости, порожденной прямой, проходящей через a перпендикулярно прямой ab, такой что b лежит в ней, и такой же полуплоскости для b - равенства/неравенства в коде как раз задают прямую и две полуплоскости.
Кроме всего прочего, векторное произведение u * v еще равняется площади параллелограмма, натянутого на вектора u и v (можно заметить, вспомнив, что формула для площади параллелограмма совпадает с формулой для векторного произведения: |u| * |v| * sin(a), где a - угол между u и v). Можно посчитать и площадь треугольника, натянутого на эти вектора - это половина площади соответствующего параллелограмма.
//функция, вычисляющая площадь треугольника с вершинами в точках a, b и c
double triangleArea(Point a, Point b, Point c) {
 return Math.abs(l.crossProd(b.substract(a), c.substract(a)) / 2);
}
Здесь считаем площадь как векторное произведение векторов b - a и c - a. Модуль нужен потому, что векторное произведение на самом деле - ориентированная площадь (знак синуса может быть положительный и отрицательный), то есть равна площади, если v расположен справа от u, и минус площади в другом случае.
Зная площадь треугольника, можно считать площади более сложных фигур, например многоугольников:
//p - массив вершин в порядке обхода, n - количество вершин
double polygonArea(Point[] p, int n) {
 double s = 0;
 for (int i = 0; i < n; ++i) {
  s += p[i].crossProd(p[i + 1]);
 }
 return abs(s) / 2;
}
Считаем площадь многоугольника как сумму площадей треугольников, у которых одна вершина совпадает с началом координат, а две другие - соседние вершины многоугольника. За счет того, что площадь ориентирована, вся "лишняя" площадь сократится (поэтому модуль нужно брать только в конце), и в результате получится ровно площадь многоугольника. Доказательство этого факта - упражнение для читателя.
Заметим, что здесь мы считали, что p[n] = p[0] (так часто удобно делать при работе с многоугольниками) - если бы это было не так, последний шаг цикла при i = n - 1 был бы некорректен. Другой способ, не предполагающий p[n] = p[0]:
...
for (int i = 0; i < n; ++i) {
 s += p[i].crossProd(p[(i + 1) % n]);
}
...
С помощью векторов легко решаются и разные конструктивные задачи. Например, найдем точку пересечения медиан треугольника:
//a, b, c - вершины треугольника
Point getCentroid(Point a, Point b, Point c) {
 Point m = (b + c) * 0.5 //середина стороны bc
 return a + (m - a) * (2.0 / 3);
}
Найдем m - середину стороны bc (нетрудно заметить, что вектор из начала координат в середину стороны равен полусумме векторов в концы сторон). m - a - вектор из a в m, а поскольку точка пересечения медиан находится на медиане на расстоянии в 2/3 ее длины от соответствующей вершины треугольника(то есть делит ее в отношении 2 к 1, считая от вершины), достаточно взять вектор медианы, укоротить его так, чтобы его длина была 2/3 от начальной (это и значит умножить его на 2/3 как вектор) , и приложить к a - получится как раз точка пересечения медиан.
Адрес: 614039, г. Пермь, ул. Комсомольский проспект, 45
Телефон: +7 (342) 212-80-71
E-Mail: school9-perm@ya.ru
Вопрос администратору сайта