Комп'ютерна геометрія з 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);

> хибно правда

Відстань між двома точками визначається виразом

закладеному у функцію 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,577)

Якщо описані вище вимоги до вихідних даних не виконані, результатом буде нульовий вектор

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 площині, і встановити, чи лежить на ній пряма.

Висновок

Дякуємо всім, хто дочитав статтю до кінця. У майбутньому я планую розвинути цю тему. Тому, якщо у вас є питання на тему пишіть їх у коментарях.