Сімнадцята лекція другого сезону відбудеться 24 березня о 18 годині у конференційній залі на третьому поверсі.
Лекцію ведуть: Ігор та Oracle.
Тема: Дерева відрізків.
На порядку денному:
- Основна ідея структури даних;
- Постановка класичних задач на дерева відрізків;
- Модифікації на способи реалізації;
- Багатовимірні випадки.
У мене питання по минулій лекції – задача про точку і відрізок:
Для того, щоб вектор, що виходить з даної точки був перпендикулярним до другого вектора, треба щоб скалярний добуток дорівнював 0. То я зрозумів.А от як тепер знайти саме ту точку на відрізку, на яку буде опущений той перпендикулярний вектор?
Так як я і розказував, треба записати рівняння прямої в параметричному вигляді (параметром буде альфа), тобто фактично виразити будь яку точку на прямій, як залежність від параметру альфа. Тоді давай розглянемо різницю того вектора(який є точкою в умові) та деякою точкою на прямій, в якій лежить даний відрізок. Знайдемо довжину цього вектора, або ще краще квадрат довжини. Тоді нам фактично треба знайти мінімум цієї довжини(це якраз і буде той самий перпендикуляр). Можна побачити що в нас буде залежність тільки від альфа в записаному виразі. Знаходимо значення альфа, в яких досягається нуль похідної. Після того точка може не попасти у відрізок, а лише на пряму. Тому далі альфа “обрізаємо” так щоб він потрапив у відрізок [0, 1], це якщо використовувати той запис, який я писав. То виглядає що це багато написано і багато роботи, але насправді це дуже просто пишеться.
Задавайте питання, не соромтесь, якщо щось незрозуміло буде, або навіть якщо після відповіді щось залишиться незрозумілим, то уточнюйте.
Можна уточнити умову . . . потрібно опустити перпендикуляр з точки на відрізок. А, якщо перпендикуляр опуститься лише на пряму, на якій лежить відрізок, то що робити?
Це було запитання стосовно домашнього завдання до лекції пятнадцять:
http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1306&
я думаю, що буде набагато простіше, коли просто-напросто взяти нормальний вектор до прямої, на якій лежить відрізок. тоді не потрібно буде брати ніяких похідних. далі знайти точку перетину прямих і зробити перевірку таку ж, як і для випадку, коли точка лежить на відрізку.
Безумовно Ваш метод теж працюватиме. Але він насправді вимагає більше коду, або принаймні якщо не більше – то коду, в якому легше помилитись, для прикладу в якомусь індексі. Тим більше метод який було розказано на лекції, та частково описаний тут, в коментарях, є більш загальнішим. Уявіть що вам потрібно розвязати ту саму задачу, але вже в просторі, при цьому ідея залишиться тою самою, єдине що принципово зміниться – це формула для скалярного добутку, тепер вона матиме три доданки. Ще підхід можна узагальнити і для інших, складніших задач. А похідну не так вже й складно знайти для виразів даного типу.