Компьютерная геометрия с Qt Creator

аналитическая геометрия, C++ геометрия, Qt геометрия, QVector2D, геометрия, компьютерная геометрия, QVector4D, QVector3D

По средствам этой статьи хочу поделиться опытом по использованию компьютерной геометрии, который накопился у меня в процессе работы над диссертацией. Не все знают Qt Creator содержит инструменты для работы с геометрией (в частности QVector3D), подробного руководства к которым на русском языке нет. Поэтому здесь я постараюсь максимально кратко изложить необходимую теорию и её реализацию.

Точка и вектор

Для описания точки в Qt предусмотрены классы QVector2D, QVector3D и QVector4D (не путать с классом QVector) для двухмерного, трехмерного и четырёхмерного пространств соответственно. По сути это массивы из двух, трёх и четырёх переменных типа float с набором геометрических функций. Поэтому всё примеры буду приводить только для наиболее полезного на практике QVector3D.

QVector3D v1(1,1,1) v2(1,1,1), v3(1.1f,2.5f,3.8f);

В примере заданы 3 вектора. В скобрах записаны координаты х, у, z. Любую из компонент вектора можно получить или переопределить.

v3.setX(0.5);
v3.setY(0.6);
v3.setZ(0.7);
qDebug() << v3.x() << v3.y() << v3.z() << v3;

0.5 0.6 0.7 QVector3D(0.5, 0.6, 0.7)

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

где – длина (модуль) вектора. В QVector3D для этого есть две функции:

v1.normalize(); // функция, изменяющая переменные объект
qDebug() << v1 << v2.normalized(); // функция, не переменные объект

QVector3D(0.57735, 0.57735, 0.57735) QVector3D(0.57735, 0.57735, 0.57735)

В примере вектор, имевший длину корень из трёх, был пересчитан в единичный вектор (такие нормализованные вектора в геометрии необходимы для различных геометрических операций). Это легко проверить с помощью функции length(), возвращающей длину вектора.

float L = v1.length(); // длина вектора или расстояние от точки до начала координат

В некоторых задачах нам интересна не длина вектора, а её квадрат. Для этого предусмотрена функция lengthSquared(), уменьшающая количество вычислений

float L2 = v1.lengthSquared();

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

bool b = v1.isNull(); // проверка: является ли вектор нулевым?

Вектора можно складывать и вычитать (при этом складываются их соответствующие координаты). Также вектор можно умножить или разделить на число (получает вектор в n раз большей или меньшей длины). Внимательней следует относиться к операции умножения, т.к. выражение v1*v2 приведём к перемножению соответствующих координат векторов. Аналогично работает операция деления v1/v2. Геометрическая трактовка двух предыдущих операций – растяжение и сжатие системы координат по соответствующим осям на величины заданные в v2. Для реализации скалярного и векторного произведений предусмотрены функции dotProduct(v1, v2) и crossProduct(v1, v2).

QVector3D v11(1,0,0), v12(0,1,0);
qDebug() << v11*v12 <<  QVector3D::dotProduct(v11, v12) <<  QVector3D::crossProduct(v11, v12);

QVector3D(0, 0, 0) 0 QVector3D(0, 0, 1)

Напомню, что скалярное произведение двух векторов – число, определяемое как

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

где i, j, k – орты декартовой системы координат, прямые скобки (здесь и далее) – определитель матрицы. Результат данной операции – вектор, перпендикулярный к плоскости в которой лежат два вектора-сомножителя, или же нулевой вектор, если v1 и v2 коллинеарные. Модуль от векторного произведения равен произведению модулей сомножителей на синус угла между ними.
Векторы можно проверять на равенство. Два вектора равны тогда, когда равны все их соответствующие координаты. Однако следует помнить, что при сложных вычислениях может накапливаться погрешность. Поэтому разработчики предусмотрели возможность «мягкого» сравнения.

v2 = v1 + QVector3D(0.000001f, 0.000001f, 0.000001f);
qDebug() << (v1 == v2) << qFuzzyCompare(v1, v2);

false true

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

заложенном в функцию distanceToPoint(v2)

QVector3D v1(0,1,1), v2(1,0,1);
qDebug() << v1.distanceToPoint(v2);

1.41421

Для векторов смыслом последней операции является длина вектора их разности.

qDebug() << (v1-v2).length();

1.41421

Плоскость

Любая плоскость может быть задана тремя попарно несовпадающими своими точками T1, T2 и T3, не лежащими на одной прямой. Другой удобное описание – использование уравнения плоскости:

где A, B, С и D – коэффициенты, которые вычисляются через координаты точек T1, T2 и T3,

(A, B, C) – нормальный вектор к плоскости, D – свободный коэффициент. Полученный результат целесообразно нормировать

(a, b, c) – единичный нормальный вектор к плоскости, d – расстояние от плоскости до начала координат (с «плюсом», если нормальный вектор направлен в полуплоскость, содержащую начало координат, иначе – с «минусом»).
Нормальный вектор к плоскости можно вычислить с помощью статической функции normal(…), аргументами которой могут являться либо три точки (как показано выше), либо два неколлинеарных вектора. Очевидно, что два вектора могут быть заданы как T1 – T2, T2 – T3, а нормаль как их векторное проведение.

QVector3D v1(0,0,1), v2(0,1,0), v3(1,0,0); // корректно заданная плоскость
qDebug() << QVector3D::normal(v1, v2, v3), QVector3D::normal(v1 - v2, v2 - v3), QVector3D::crossProduct(v1 - v2, v2 - v3).normalized();

QVector3D(-0.57735, -0.57735, -0.57735) QVector3D(-0.57735, -0.57735, -0.57735) QVector3D(-0.57735, -0.57735, -0.57735)

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

QVector3D v01(0,0,10), v02(0,0,20), v03(0,0,30); // некорректно заданная плоскость
qDebug() << QVector3D::normal(v01, v02, v03) << QVector3D::normal(v01 - v02, v02 - v03);

QVector3D(0, 0, 0) QVector3D(0, 0, 0)

Приведённое описание плоскости является наиболее компактным (4 числа). Но наиболее удобным является описание плоскости одной точкой (T0) и нормальным вектором (6 чисел). Такое представление позволяет легко организовать следующие операции.

Принадлежность плоскость

Если точка T лежит на плоскости, то подставив в уравнение плоскости её координаты получим 0. В представлении через точку и вектор

Другими словами вектор T – T0 перпендикулярен нормальному вектору n.

В одном полупространстве

Плоскость делит пространство на два полупространства. Предыдущее выражение принимает положительные значения, если точка T лежит в одном из них и отрицательные, если в другом. Поэтому 2 точки T1 и T2 лежит в одном полупространстве если

Проекция точки T на плоскость

Расстояние от точки до плоскости

это расстояние от точки до её проекции на плоскость

Определяется оно с помощью функции distanceToPlane(…), аргументами которой являются параметры плоскости (точка и вектор или три точки).

QVector3D T(2,2,2);// точка
QVector3D n(-1,-1,-1), T0(1,1,1);// плоскость
qDebug() << T.distanceToPlane(T0,n) << QVector3D::dotProduct(T-T0, n);// неправильный расчёт: нормальный вектор не нормализован
qDebug() << T.distanceToPlane(T0,n.normalized()) << QVector3D::dotProduct(T-T0, n)/n.length();//правильный расчёт

-3 -3
-1.73205 -1.73205

Обратите внимание, что получаемое значение имеет знак в соответствии с там, в какой полуплоскости лежит T.

Зеркальное отражение точки T от плоскости

Прямая

Прямая в пространстве полностью описывается двумя (несовпадающими) точками T1 и T2. В Qt принято описывать прямую точкой T1 и направляющим вектором K = T2 – T1.

или

где (ΔX, ΔY, ΔZ) = K. Этот вектор также целесообразно нормировать

Принадлежность точки T прямой

Необходимо проверить вектора (T – T1) и k на коллинеарность (векторное произведение – нулевой вектор).

Проекция точки T прямую

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

Расстояние от точки T до прямой

В соответствии с изложенным выше

Расстояние от точки до прямой определяется функцией distanceToLine(…), аргументами которой являются точка и направляющий вектор прямой.

QVector3D T(2,2,2);// точка
QVector3D k(1,1,0), T1(0,0,1);// плоскость
QVector3D R = T - T1 - k*QVector3D::dotProduct(k, T - T1);
qDebug() << T.distanceToLine(T1,k) << R.length(); // неправильный расчёт: направляющий вектор не нормализован
R = T - T1 - k*QVector3D::dotProduct(k, T - T1)/k.lengthSquared();
qDebug() << T.distanceToLine(T1,k.normalized()) << R.length(); // правильный расчёт

3 3
1 1

Пересечение прямой и плоскости

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

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

Заключение

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