Задача: чи перетнуться дві задані прямі, що лежать в одній площині?


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

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

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

Таку задачу можна розв’язати скориставшись наступним кодом:

public class Line { // Надмала одиниця, яку ми використовуємо для порівняння чисел з плаваючою точкою: static double epsilon = 0.000001; // Нахил прямої: public double slope; // Зрушення прямої по OY: public double yintercept; public Line (double s, double y) { slope = s; yintercept = y; } public boolean intersect (Line line2) {
return Math.abs (slope - line2.slope)  > epsilon || Math.abs (yintercept - line2.yintercept)  < epsilon; }}

У цьому розв’язанні лінія задаватиметься двома параметрами – зрушенням по осі X і нахилом по осі Y. Далі ми в два етапи перевіряємо, чи вважаються лінії паралельними.

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

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

Окрему увагу тут слід приділити полю epsilon. Чому б нам просто не порівняти пари значень одне з одним? Тут слід згадати про те, що числа з плаваючою точкою не забезпечують абсолютну точність, і при оперуванні з числами, що мають велику кількість знаків після коми, ми отримуватимемо великі погрішності, через які відповідь може спотворюватися.

Тому ми використовуватимемо для порівняння окрему малу одиницю (у математиці малі одиниці часто позначаються грецькою буквою “епсілон”): при оперуванні з таким числом зберігатиметься достатня точність, тому ми зможемо точніше визначати, чи є рівними числа. У нашому випадку виходить: якщо різниця двох чисел виявиться більше за досить малу величину, це означатиме, що вони різняться, тобто не дорівнюють одне одному.

Узято з книги “Кар’єра програміста. Як влаштуватися на роботу в Google, Microsoft або іншу провідну IT- компанію”

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *