НОУ ІНТУЇТ | лекція | Проект "Опукла оболонка"

Аналітична геометрія і програмування

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

Ряд фактів з аналітичної геометрії та векторної алгебри є необхідною базою для вирішення сформульованих завдань, проте тільки знання елементів обчислювальної геометрії дозволяє отримати досить ефективні рішення. Найпростішим прикладом може служити завдання обчислення площі трикутника за відомими координатами його вершин. Відома з середньої школи формула Герона

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

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

відстань між двома точками на площині можна порахувати за відомою формулою , Яка і використовується в реалізації методу dist. Два об'єкти типу R2Point відповідають збігається точкам площині тоді і тільки тоді, коли попарно рівні їх координати, що дозволяє реалізувати метод equal.

public static double dist (R2Point a, R2Point b) {return Math.sqrt ((ax-bx) * (ax-bx) + (ay-by) * (ay-by)); } Public static boolean equal (R2Point a, R2Point b) {return ax == bx && ay == by; } Public static double area (R2Point a, R2Point b, R2Point c) {return 0.5 * ((ax-cx) * (by-cy) - (ay-cy) * (bx-cx)); }

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

Часто корисно використовувати запис цього визначення в координатах. якщо , а , То координати вектора знаходяться за формулою

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

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

public static boolean isTriangle (R2Point a, R2Point b, R2Point c) {return area (a, b, c)! = 0,0; } Public boolean inside (R2Point a, R2Point b) {return (ax <= x && x <= bx || ax> = x && x> = bx) && (ay <= y && y <= by || ay> = y && y> = by); }
Мал. 11.5. Освітленість ребра з точки

Перед тим, як реалізувати метод light, що дозволяє з'ясувати, освітлено чи ребро опуклої оболонки з точки , Дамо суворе визначення освітленості.

Визначення 11.3. ребро називається освітленим з точки , Якщо орієнтована площа трикутника, утвореного точками , і негативна, або якщо точка розташована на прямій, що проходить через точки і , Поза відрізка .

Зауважимо, що при такому формальному визначенні поняття освітленості ніяке ребро багатокутника не освітлене ні з однієї точки всередині або на кордоні багатокутника, що добре видно на малюнку Мал. 11.5 .

public boolean light (R2Point a, R2Point b) {double s = area (a, b, this); return s <0.0 || (S == 0.0 &&! Inside (a, b)); }

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

На першому кроці вирішення цього завдання необхідно з'ясувати, чи перетинаються обмежують прямокутники (bounding boxes) цих відрізків. Обмежує прямокутник - це мінімальний прямокутник зі сторонами, паралельними осям координат, що містить відрізок.

Нехай координати граничних точок першого відрізка рівні і , А другого - і . Тоді координати лівого нижнього кута прямокутника першого відрізка дорівнюватимуть , А правого верхнього кута - , де , , і . Аналогічно визначаються координати і лівого нижнього і правого верхнього кутів прямокутника другого відрізка.

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

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

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

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

Таким чином, відрізки і перетинаються тоді і тільки тоді, коли одночасно виконуються наступні три умови:

1) перетинаються обмежують їх прямокутники;

2)

3) .

Більш докладний виклад рішення цієї та низки інших подібних завдань може бути знайдено в розділі "Обчислювальна геометрія" книги [8] .