1

Тема: фунція з координатами

підкажіть, яка функція визначає, чи належить певна точка до сектораю Дана є точка яка перевіряється і вершини сектора

2

Re: фунція з координатами

То Вам треба написати таку функцію?

3

Re: фунція з координатами

кхе кхе, ну от давайте розберемо одновимірний варіант. Є пряма, відрізок на прямій - це сектор, а точка на прямій - це точка. Очевидно, точка буде належати цьому сектору, якщо вона не менша за початок відрізку, та не більша за кінець відрізку. В двовимірному варіанті те ж саме, тільки компонентів координат більше. Тобто перебираєте першу компоненту всіх координат сектора та обираєте найменшу та найбільшу, і так зі всіми іншими компонентами. Далі у вас має вийти дві координаті, максимальна та мінімальна, а потім звіряєте їх з координатою точки, якщо всі компоненти координати точки не більші максимальної та не менші мінімальної відповідної компоненті максимальної та мінімальної координати, то все ок, точка в секторі.
http://не-дійсний-домен/6tlc1.png

4 Востаннє редагувалося koala (22.01.2014 00:43:21)

Re: фунція з координатами

Ви продовжуєте називати багатокутники секторами?
Тут все зовсім не так просто: уявіть собі багатокутник, "закручений" у спіраль. Правда, не так легко сказати, де знаходиться довільна точка - всередині чи ззовні такого багатокутника?
Для простих фігур, типу трикутника, можна скористатися такою властивістю: якщо взяти рівняння прямої a*x+b*y+c=0 і підставити точку на прямій, воно буде виконуватися; якщо взяти точку в одній півплощині, то буде a*x+b*y+c < 0, а в другій - a*x+b*y+c > 0. Відповідно, якщо правильно складати рівняння, то всі точки всередині будуть давати один знак, а зовні - інший.
Отже, якось так: беремо найлівішу точку, оскільки від неї вся фігура вправо - то області лівіше неї зовнішня, а правіше ліній, що йдуть з неї - внутрішня. Ідемо по вершинах і шукаємо три вершини поспіль, що творять трикутник без точок (вершин і нашої шуканої) всередині. Видаляємо центральну вершину цього трикутника з фігури. Зрештою у нас лишиться або трикутник із шуканою точкою всередині (і тоді вона належить фігурі), або залишиться дві точки, і тоді не належить.
Звісно, якщо при кожній зміні фігури перевіряти, чи найбільші і найменші координати з точок фігури містять шукану точку, то все буде трохи швидше.

А пан FakiNyan перевіряє, чи потрапляє точка до прямокутника зі сторонами, паралельними вісям, описаного навколо нашої фігури. Наприклад:
http://не-дійсний-домен/g158o33qt/image.png
Точка чудово вписується за координатами, але лежить за межами трикутника.

Подякували: FakiNyan1

5

Re: фунція з координатами

Прихований текст

koala я знав, що не все так просто

6 Востаннє редагувалося koala (22.01.2014 09:44:06)

Re: фунція з координатами

Ще один варіант спав на думку, адекватніший. У нас є множина відрізків (сторін). Проведемо пряму, скажімо, вертикальну (x=x0), що проходить через нашу точку. Знайдемо точки перетинів цієї прямої зі сторонами (щоб знайти перетин, треба підставити x0 в рівняння сторін і перевірити, чи потрапляє розв'язок між кутами). А тепер у нас є одновимірний варіант - у всіх цих перетинів одна координата (x0) спільна, треба тільки полічити, у скільки перетинів координата y більша (чи менша), ніж в нашої точки. Якщо кількість парна - точка лежить іззовні, якщо непарна - всередині.

7 Востаннє редагувалося koala (22.01.2014 09:40:46)

Re: фунція з координатами

Так, ще корисна дрібниця: якщо є дві точки (x1, y1) і (x2, y2), то рівняння прямої, що проходить крізь них, буде
( x - x2 )* ( y1 - y2 ) = ( y - y2 ) * ( x1 - x2 )

Доказ:

Це рівняння є рівнянням прямої; підстановка наших точок перетворює вираз на істиний. Отже, ці точки лежать на прямій. Через дві точки на площині можна провести рівно одну пряму. Отже, це наша пряма.

Щоб перевірити, чи лежить точка прямої між двома точками на прямій, достатньо порівняти тільки одну координату.

8

Re: фунція з координатами

koala написав:

Ще один варіант спав на думку, адекватніший. У нас є множина відрізків (сторін). Проведемо пряму, скажімо, вертикальну (x=x0), що проходить через нашу точку. Знайдемо точки перетинів цієї прямої зі сторонами (щоб знайти перетин, треба підставити x0 в рівняння сторін і перевірити, чи потрапляє розв'язок між кутами). А тепер у нас є одновимірний варіант - у всіх цих перетинів одна координата (x0) спільна, треба тільки полічити, у скільки перетинів координата y більша (чи менша), ніж в нашої точки. Якщо кількість парна - точка лежить іззовні, якщо непарна - всередині.

Ось варіант, коли і парна кількість, і непарна, але точка все-одно не в багатокутнику.
http://replace.org.ua/misc.php?action=pun_attachment&amp;item=419&amp;download=0&amp;secure_str=4061t2195

P.S. Гадаю потрібно ділити фігуру на трикутники та шукати в них.

Post's attachments

Untitled.png 10.86 kb, 300 downloads since 2014-04-16 

9

Re: фунція з координатами

1. Не проблема - точка згори потрапляє на 2 сторони, отже, буде врахована двічі. Кількість і зверху і знизу парна - точка ззовні.
2. Кількість і зверху і знизу парна - точка ззовні.

10

Re: фунція з координатами

koala написав:

точка згори потрапляє на 2 сторони, отже, буде врахована двічі.

Ммм... наче так все підходить. Залишилось розрулити ситуацію, коли вертикальна пряма буде повністю співпадати з однією стороною.

P.S. Цікаво, де автор теми? )

11

Re: фунція з координатами

В такому разі кількість парна, але, дійсно, це потребує окремої гілки.