Структури геометричних даних, основні операції - Програмування від
До лаcc Point містить елементи даних х і для зберігання координат окуляри. Компонентні функції забезпечують виконання операцій з визначення положення точки щодо заданого відрізка прямої лінії та обчислення відстані від заданої точки до прямої лінії. Додаткові компонентні функції розглядають поточну точку як вектор і перевантажують відповідні операції реалізації векторної арифметики, використовуючи ключове слово operator. Включено також компонентні функції, що повертають значення полярного кута та довжини.
К онструктор ініціалізує нову точку з координатами х і у:
Якщо аргумент не вказано, то за умовчанням ініціалізується точка на початку координат (О, О).
Можна ініціалізувати точку як дубль іншої точки. Наприклад, звернення Point p(q) ініціалізує нову точку р із тими самими координатами, як і точка q. У цьому випадку ініціалізація здійснюється копіруючим конструктором за замовчуванням (що існує в компіляторі" мови C++), який виконує копію з усіма елементами.
У векторне додавання та векторне віднімання виконується за допомогою операцій-функцій зі знаками операцій + і - відповідно:
О перація скалярного множення реалізована у вигляді дружньої функції класу Point, а не члена класу, оскільки її перший операнд не відноситься до типу Point. Оператора визначено так:
Про переція-функція operator[] повертає координату х поточної точки, якщо в зверненні як індекс координати було вказано значення О, або координату у при вказанні значення індексу 1:
Про перецію відносини == і != використовуються визначення еквівалентності двох точок:
Про перецію реалізують лексикографічний порядок відносин, коли вважається, що точка меншаточки b, якщо а.х У порядкування точок на площині може бути виконано нескінченним числом посібників. Тим не менш зручно використовувати операції П Перш, ніж переходити до інших компонентних функцій класу Point, розглянемо наступний простий приклад, який показує застосування об'єктів класу Point.
Ф ункція orientation повертає значення 1, якщо три точки, що обробляються, орієнтовані позитивно, -1, якщо вони орієнтовані негативно, або 0, якщо вони колінеарні.
Відносне положення точки та прямої лінії
Про дно з найважливіших операцій полягає у визначенні положення точки щодо спрямованого відрізка прямої лінії. Результат виконання операції показує, чи лежить точка зліва або праворуч від спрямованого відрізка прямої лінії або, якщо вона збігається з прямою лінією, розташовується вона після кінця спрямованого відрізка цієї прямої лінії, до початку, а якщо ні те, ні інше, то чи не збігається вона з початком чи з кінцем чи лежить поміж ними. Спрямований відрізок прямої лінії чітко поділяє площину на сім областей, що не перетинаються, і ця операція повідомляє, якій з цих областей належить точка.
 |
Для визначення положення поточної точки щодо відрізка прямої лінії p0p1, спрямованого від точки р0 до точки p1, використовується компонентна функція classify. Повертається значення типу перерахування, що вказує на положення поточної точки:
На початку перевіряється орієнтація точок p0, p1 і р2, щоб визначити, чи точка р2 розташовується зліва або справа, або вона колінеарна з відрізком p0p1. У разі необхідні додаткові обчислення, їли вектори a=pl-pO і b=р2-p0 мають протилежне напрям, точка р2 лежить позаду направленого відрізка p0p1якщо вектор а коротший за вектор b, то точка р2 розташована після відрізка p0p1. В іншому випадку точка р2 порівнюється з точками p0 і р1 для визначення, чи збігається з однією з цих кінцевих точок або лежить між ними.
Для зручності передбачена дещо інша версія компонентної функції classify, якою як аргумент передається ребро замість пари точок.
Про визначення відносного положення точки і прямої лінії використовується дуже часто. У деяких застосуваннях достатня більш груба класифікація (тобто достатньо індикації положення точки зліва або праворуч від прямої лінії, або просто фіксації збігу з нею). В інших застосуваннях потрібна повна схема цієї класифікації.
Система полярних координат забезпечує другий спосіб завдання положення точки на площині. Полярна вісь виходить із точки початку координат 0 і направлена у вигляді горизонтального променя вправо, як показано на рис. 2. Точка а є парою чисел (ra, Thetaa). Приймаючи точку a за вектор, що починається в точці початку координат, число ra визначає тин вектора, а Thetaa - його полярний кут (кут, що утворюється між вектором а і полярною віссю і відраховується в напрямку обертання проти годинникової стрілки).
Відповідність між парами чисел (ra, Thetaa) і точками не є однозначною: безліч пар можуть представляти ту саму точку. Пара (0, Theta) відповідає початку координат для будь-якого значення 0. Більше того, пари чисел (r, Theta + 360k) відповідають одній і тій самій точці для будь-якого цілого числа k.
Крапка може бути представлена як у декартових, так і в полярних
координатах і іноді буває необхідно переходити від однієї системи до іншої. Як очевидно з рис. 2, два вирази
здійснюють перетворення з полярнихкоординат (r, Theta) в декартові координати (х, у).
 |
Для зворотного перетворення координата відстані визначається як
Щоб виразити полярний кут Theta у функції від х і у зауважимо, що існує співвідношення tan Theta = y/x з якого випливає
Для використання цього виразу у функції polarAngle необхідно розрізняти квадранти на площині та враховувати випадок можливої рівності нулю координати х:
Зазначимо, що функція polarAngle повертає значення -1.0, якщо поточний вектор є нульовим вектором (інакше повертається невід'ємне значення). Цю обставину ми використовуємо згодом для спрощення опису функції порівняння, що базується на завданні полярного кута.
Компонентна функція length повертає довжину поточного вектора
Компонентна функція distance повертає значення відстані (зі знаком) від поточної точки до ребра. Цю функцію визначимо нижче.