Головна > Програмування > Бібліотека для геометричних обчислень

Бібліотека для геометричних обчислень

Библіотека GEOMLIB призначена для різноманітних геометричних обчислень на площині та перерахунку координат для малювання на екрані. Для будь-яких версій Delphi.

Періодично мені було потрібно щось таке порахувати і набридло постійно шукати алгоритми. Тому було вирішено зібрати все в одному юніті раз і назавжди :) Бібліотеку можна використовувати для движків 2D ігор, розрахунків координат малювання різних графіків, креслень і т.п. Представлена тільки алгоритмічна частина, сама “малювалка” залишається на совісті програміста *. Потрібно так само розуміти, що бібліотека була розроблена в першу чергу для практичного застосування в іграх та інших додатках, а не для вирішення теоретичних завдань з геометрії.

_____________________
* У бібліотеці є тільки одна функція, побічно зав’язана на TCanvas, це перерахунок багатокутника в масив “екранних” координат (цілих чисел), який може бути
переданий безпосередньо функцій Canvas.Polygon або Canvas.Polyline.

Реалізовано різні види обчислень, а саме:

  1. Перетворення класичних / екранних координат туди і назад;
  2. Перетворення декартових координат в полярні і назад;
  3. Обчислення кутів, відстаней;
  4. Знаходження входжень, перетинів (точок перетину);
  5. Модифікатори;
  6. Обчислення площі фігур;
  7. Різні допоміжні штуки (див. у коді);

ООП не використовується, тільки функціональний код. Бібліотека реалізує такі сутності **, як:

  1. Точка (в декартових і полярних координатах);
  2. Відрізок;
  3. Пряма (тобто саме нескінченна пряма);
  4. Коло;
  5. Багатокутник (може бути так само використаний графічно як полілінія або масив точок);
  6. Описуючий прямокутник;

_____________________
** У бібліотеці є функції, які працюють з такими сутностями, як трикутник і вектор, але окремих типів для них немає. Трикутник задаеться просто трьома координатами, а вектор двома – “початковою” та “спрямовуючою”.

Зверніть увагу, що всі координати задаються в класичному вигляді, як на мал. 1. При перерахунку координат в “екранні” вони перетворюються в цілочисельні і модифікуються таким чином, щоб класичий вигляд правильно відобразився на екрані. При нульовому зміщенні початку осей координат відносно екрану, точка їх перетину буде відображатися в центрі (мал. 2).

мал. 1

мал. 2

TViewport – структура, що описує параметри області відображення (екрану), такі як ширина, висота, масштаб і зміщення початку осей координат щодо її центру.
Зміщення обчислюється в екранних координатах, тобто рухаємо центр осей з права на ліво і зверху вниз. масштаб повинен обов’язково бути додатним числом більше 0, інакше викликається виняток!

Кути визначаються як показано нижче. Задаються в радіанах, для градусів використовуйте перерахунок через функцію DegToRad.

мал. 3. Додатний кут

мал. 4. Від’ємний кут

мал. 5. Кути обох знаків

При перевірках різних перетинів, з метою оптимізації і прискорення обчислень, рекомендується до кожного об’єкту, такого як відрізок або багатокутник заздалегідь порахувати описуючий прямокутник і спочатку перевіряти перетин об’єктів по перетинанню їх описуючих прямокутників, тому що це значно швидше. І тільки при перетині останніх – вже перевіряти відповідними функціями. Для “нерухомих” об’єктів, чиї координати не змінюються, описуючі прямокутники
краще порахувати заздалегідь і при перевірках використовувати вже готові дані.

Перевірка перетину багатокутників здійснюється в два етапи – спочатку перевіряється входження хоча б однієї вершини першого багатокутника в другій (це швидше працює, але не перевіряє ситуацію коли перетинаються сторони, без входження вершин) і тільки якщо попередній алгоритм не дав позитивного результату – перевіряється по     перетину сторін (повільніше, але дає остаточну відповідь). обидва алгоритма представлені як окремо, так і у вигляді універсальної функції.

Функція PolygonToViewportCoord призначена для автоматизації перетворення вершин багатокутника в масив “екранних” точок (TPoint). Ця функція робить тільки перерахунок, вона не працює з пам’ятью, створити буфер необхідного розміру потрібно заздалегідь.

Прямі визначені загальним рівнянням (Ax + By + C = 0), найефективнішим з точки зору найбільш частих обчислень, а саме – визначення півплощини, в якій лежить будь-яка точка щодо цієї прямої. І звідси вже робляться всі інші перевірки, такі як перевірка перетину прямої з відрізком, многоугольником, і т.п. Можна задати пряму різними способами, але в підсумку все перераховується в вищевказаний вигляд.

Перевірка опуклості багатокутника робиться шляхом перетворення кожної сторони в пряму і визначення положення наступної вершини прилеглої сторони відносно цієї прямої. Якщо вершин всього 3 – то результат повертається відразу тому що очевидно, що трикутник може бути тільки опуклим.

При створенні кола обов’язково вказуйте його радіус як додатне число більше 0, інакше всякі перевірки перетинів або входжень будуть видавати False. Окремі модифікатори для кола не реалізовані, для цього пропонується використовувати модифікатори точки (центр кола).

У деяких функціях перевірка числа на нуль, здійснюється з урахуванням округлення до 1E-12. Тобто “дуже маленькі числа” сприймаються як нуль. Це зроблено з метою уникнути помилок при не зовсім коректних результатах математичних операцій над числами, які іноді трапляються. Така ж сама ситуація може виникнути при порівнянні двох чисел – в результаті обчислень два числа, які начебто повинні бути рівні, дуже слабо відрізняються. Для їх порівняння використовується спеціальна функція.

У бібліотеці є також функції перетворення координат в полярні і назад.

Функції були протестовані, але зрозуміло, не виключається наявність в них помилок, які, можливо, виникають у дуже рідкісних випадках. Якщо що таке знайдете – повідомляйте, будемо ремонтувати.

Всі алгоритми знайдені на безмежних просторах Інтернету, в різних програмерських форумах, вікіпедіях та шкільних підручниках з геометрії :)

Призначення функцій див. в коментарях до вихідного тексту.

Завантажити бібліотеку

Програмування , , , , ,

  1. Ще немає коментарів.
  1. Немає ще трекбеків.
Вам потрібно увійти, для коментування