Знаковая площадь треугольника и предикат "По часовой стрелке"

Определение

Пусть даны три точки $p_1$ , $p_2$ , $p_3$ . Найдём значение знаковой площади $S$ треугольника $p_1 p_2 p_3$ , т.е. площади этого треугольника, взятой со знаком плюс или минус в зависимости от типа поворота, образуемого точками $p_1$ , $p_2$ , $p_3$ : против часовой стрелки или по ней соответственно.

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

Вычисление

Воспользуемся понятием косого (псевдоскалярного) произведения векторов. Оно как раз равно удвоенной знаковой площади треугольника:

$a \land b = |a| |b| \sin \angle (a, b) = 2 S,$

где угол $\angle (a, b)$ берётся ориентированным, т.е. это угол вращения между этими векторами против часовой стрелки.

(Модуль косого произведения двух векторов равен модулю векторного произведения их.)

Косое произведение вычисляется как величина определителя, составленного из координат точек:

$2 S = \left| \matrix{ x_1 & y_1 & 1 \cr x_2 & y[...]$

Раскрывая определитель, можно получить такую формулу:

$2 S = x_1 (y_2 - y_3) + x_2 (y_3 - y_1) + x_3 (y_[...]$

Можно сгруппировать третье слагаемое с первыми двумя, избавившись от одного умножения:

$2 S = (x_2 - x_1) (y_3 - y_1) - (y_2 - y_1) (x_3 [...]$

Последнюю формулу удобно записывать и запоминать в матричном виде, как следующий определитель:

$2 S = \left| \matrix{ x_2 - x_1 & y_2 - y_1 \cr [...]$

Реализация

Функция, вычисляющая удвоенную знаковую площадь треугольника:

int triangle_area_2 (int x1, int y1, int x2, int y2, int x3, int y3) {
	return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}

Функция, возвращающая обычную площадь треугольника:

double triangle_area (int x1, int y1, int x2, int y2, int x3, int y3) {
	return abs (triangle_area_2 (x1, y1, x2, y2, x3, y3)) / 2.0;
}

Функция, проверяющая, образует ли указанная тройка точек поворот по часовой стрелке:

bool clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
	return triangle_area_2 (x1, y1, x2, y2, x3, y3) < 0;
}

Функция, проверяющая, образует ли указанная тройка точек поворот против часовой стрелки:

bool counter_clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
	return triangle_area_2 (x1, y1, x2, y2, x3, y3) > 0;
}