Тема: фунція з координатами
підкажіть, яка функція визначає, чи належить певна точка до сектораю Дана є точка яка перевіряється і вершини сектора
Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → C#, .NET → фунція з координатами
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
підкажіть, яка функція визначає, чи належить певна точка до сектораю Дана є точка яка перевіряється і вершини сектора
кхе кхе, ну от давайте розберемо одновимірний варіант. Є пряма, відрізок на прямій - це сектор, а точка на прямій - це точка. Очевидно, точка буде належати цьому сектору, якщо вона не менша за початок відрізку, та не більша за кінець відрізку. В двовимірному варіанті те ж саме, тільки компонентів координат більше. Тобто перебираєте першу компоненту всіх координат сектора та обираєте найменшу та найбільшу, і так зі всіми іншими компонентами. Далі у вас має вийти дві координаті, максимальна та мінімальна, а потім звіряєте їх з координатою точки, якщо всі компоненти координати точки не більші максимальної та не менші мінімальної відповідної компоненті максимальної та мінімальної координати, то все ок, точка в секторі.
Ви продовжуєте називати багатокутники секторами?
Тут все зовсім не так просто: уявіть собі багатокутник, "закручений" у спіраль. Правда, не так легко сказати, де знаходиться довільна точка - всередині чи ззовні такого багатокутника?
Для простих фігур, типу трикутника, можна скористатися такою властивістю: якщо взяти рівняння прямої a*x+b*y+c=0 і підставити точку на прямій, воно буде виконуватися; якщо взяти точку в одній півплощині, то буде a*x+b*y+c < 0, а в другій - a*x+b*y+c > 0. Відповідно, якщо правильно складати рівняння, то всі точки всередині будуть давати один знак, а зовні - інший.
Отже, якось так: беремо найлівішу точку, оскільки від неї вся фігура вправо - то області лівіше неї зовнішня, а правіше ліній, що йдуть з неї - внутрішня. Ідемо по вершинах і шукаємо три вершини поспіль, що творять трикутник без точок (вершин і нашої шуканої) всередині. Видаляємо центральну вершину цього трикутника з фігури. Зрештою у нас лишиться або трикутник із шуканою точкою всередині (і тоді вона належить фігурі), або залишиться дві точки, і тоді не належить.
Звісно, якщо при кожній зміні фігури перевіряти, чи найбільші і найменші координати з точок фігури містять шукану точку, то все буде трохи швидше.
А пан FakiNyan перевіряє, чи потрапляє точка до прямокутника зі сторонами, паралельними вісям, описаного навколо нашої фігури. Наприклад:
http://не-дійсний-домен/g158o33qt/image.png
Точка чудово вписується за координатами, але лежить за межами трикутника.
Ще один варіант спав на думку, адекватніший. У нас є множина відрізків (сторін). Проведемо пряму, скажімо, вертикальну (x=x0), що проходить через нашу точку. Знайдемо точки перетинів цієї прямої зі сторонами (щоб знайти перетин, треба підставити x0 в рівняння сторін і перевірити, чи потрапляє розв'язок між кутами). А тепер у нас є одновимірний варіант - у всіх цих перетинів одна координата (x0) спільна, треба тільки полічити, у скільки перетинів координата y більша (чи менша), ніж в нашої точки. Якщо кількість парна - точка лежить іззовні, якщо непарна - всередині.
Так, ще корисна дрібниця: якщо є дві точки (x1, y1) і (x2, y2), то рівняння прямої, що проходить крізь них, буде
( x - x2 )* ( y1 - y2 ) = ( y - y2 ) * ( x1 - x2 )
Щоб перевірити, чи лежить точка прямої між двома точками на прямій, достатньо порівняти тільки одну координату.
Ще один варіант спав на думку, адекватніший. У нас є множина відрізків (сторін). Проведемо пряму, скажімо, вертикальну (x=x0), що проходить через нашу точку. Знайдемо точки перетинів цієї прямої зі сторонами (щоб знайти перетин, треба підставити x0 в рівняння сторін і перевірити, чи потрапляє розв'язок між кутами). А тепер у нас є одновимірний варіант - у всіх цих перетинів одна координата (x0) спільна, треба тільки полічити, у скільки перетинів координата y більша (чи менша), ніж в нашої точки. Якщо кількість парна - точка лежить іззовні, якщо непарна - всередині.
Ось варіант, коли і парна кількість, і непарна, але точка все-одно не в багатокутнику.
P.S. Гадаю потрібно ділити фігуру на трикутники та шукати в них.
1. Не проблема - точка згори потрапляє на 2 сторони, отже, буде врахована двічі. Кількість і зверху і знизу парна - точка ззовні.
2. Кількість і зверху і знизу парна - точка ззовні.
точка згори потрапляє на 2 сторони, отже, буде врахована двічі.
Ммм... наче так все підходить. Залишилось розрулити ситуацію, коли вертикальна пряма буде повністю співпадати з однією стороною.
P.S. Цікаво, де автор теми? )
В такому разі кількість парна, але, дійсно, це потребує окремої гілки.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися