Перевірка приналежності точки багатокутнику

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

З'ясувати приалежність точки стороні багатокутника доволі просто, скориставшись алгоритмом приналежності точки відрізку: якщо точка Метод трасування променя належить відрізку з координатами metod_trasyvannja_promenja2 та metod_trasyvannja_promenja3, то повинна виконуватись наступна рівність:

metod_trasyvannja_promenja4

Для визначення приналежності точки середині багатокутника скористаємось одним із стандартних методів, а саме: проведемо з даної точки пряму, паралельну осі metod_trasyvannja_promenja6 і підраховуємо, скільки сторін даного багатокутника вона перетинає. Якщо в результаті підрахунку було отримано непарну кількість сторін, то точка metod_trasyvannja_promenja5 міститься в середині багатокутника, якщо парна кількість або нуль — то точка metod_trasyvannja_promenja5 міститься за його межами.

metod_trasyvannja_promenja10

Графічне предаставлення алгоритму провірки приналежності точки багатокутнику

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

  1. Обидва ребра, що входять у вершину, лежать по одну сторону від прямої (на малюнку вершина metod_trasyvannja_promenja11). У такому випадку, кількість перетинів можна вважати рівним двом або нулю.
  2. Один з кінців ребра лежить строго нижче прямої, а інший кінець — вище або лежить на прямій (на малюнку вершини metod_trasyvannja_promenja81 та metod_trasyvannja_promenja12 відповідно). У такому випадку, число перетинів приймаємо рівним одиниці.

Після того, як основна ідея алгоритму відома, спробуємо застосувати його на конкретному прикладі, тобто створимо delphi-проект, який буде провіряти приналежність точки багатокутнику без врахування вище розглянутих умов 1 та 2. Для цього, відкриємо середовище програмування delphi, створимо новий проект, після чого, на головній формі розмістимо компоненти наступним чином:

Інтерфейс delphi-проекту "Провірка приналежності точки багатокутнику"

Інтерфейс delphi-проекту "Провірка приналежності точки багатокутнику"

Далі переходимо до обробника події OnClick компонента Button1 ("Побудувати багатокутник"), і в тілі процедури Button1Click запишемо код, з допомогою якого будемо заповнювати два динамічних масива X та Y випадковими значеннями з певного проміжку, після чого, за отриманими значеннями малювати на формі багатокутник:

var
// Координати вершин багатокутника
X, Y: array of integer;
// Координати точки
pX, pY, n: integer;
procedure TForm1.Button1Click(Sender: TObject);
var
i: integer;
begin
// Задамо розмірність динамічних масивів X, Y
n := SpinEdit1.Value;
SetLength(X, n);
SetLength(Y, n);
// Заповнюємо масиви X та Y даними та здійснюємо побудову багатокутника
randomize;
for i := 0 to n-1 do
begin
X[i] := RandomRange(100, Form1.Width — 100);
Y[i] := RandomRange(100, Form1.Height — 100);
if (i > 0) then
begin
Form1.Canvas.MoveTo(X[i-1], Y[i-1]);
Form1.Canvas.LineTo(X[i], Y[i]);
end;
if (i = n-1) then
begin
Form1.Canvas.MoveTo(X[i], Y[i]);
Form1.Canvas.LineTo(X[0], Y[0]);
end;
end;
end;

Далі, для обробника OnClick компонента Button2 ("Пбудувати точку"), запишемо код побудови точки:

procedure TForm1.Button2Click(Sender: TObject);
begin
// Зберігаємо координати точки в глобальні змінні pX та pY
pX := StrToInt(Edit2.Text);
pY := StrToInt(Edit1.Text);
// Здійснюємо побудову точки
Form1.Canvas.Ellipse(pX — 3, pY — 3, pX + 3, pY + 3);
end;

І на останньому кроці на обробник події OnClick компонента Button3 ("Провірити приналежність") реалізуємо алгоритм провікки приналежності точки побудованому випадковим чином багатокутнику. Відмітимо, що даний алгоритм базується на процедурі відшукання точки перетину кожної сторони багатокутника з деякою прямою. Яким чином реалізується дана процедура можна знайти за посиланням Знаходження точки перетину двох прямих заданих точками свого початку та кінця.

procedure TForm1.Button3Click(Sender: TObject);
var
i, j, k: integer;
A: array[1..2, 1..2] of real;
b: array[1..2] of real;
d, d1, d2, X, Y: real;
Xn, Yn: integer;
begin
// Задамо координати кінця вілрізка паралельного осі OX
Xn := Form1.Width;
Yn := pY;
// Здійснюєм побудову відрізка паралельного осі OX
Form1.Canvas.MoveTo(pX, pY);
Form1.Canvas.LineTo(Xn, Yn);
// В циклі здійснюємо підрахунок кількості перетинів прямої паралельної осі OX з сторонами багатокутника
k := 0;
for i := 0 to n-1 do
begin
if (i = (n — 1)) then
j := 0
else
j := i + 1;
// Алгоритм відшукання точки перетину двох прямих
A[1, 1] := Yn — pY; A[1, 2] := pX — Xn; b[1] := — (pY * Xn — pX * Yn);
A[2, 1] := mY[j] — mY[i]; A[2, 2] := mX[i] — mX[j]; b[2] := — (mY[i] * mX[j] — mX[i] * mY[j]);
d := A[1, 1] * A[2, 2] — A[2, 1] * A[1, 2];
d1 := b[1] * A[2, 2] — b[2] * A[1, 2];
d2 := A[1, 1] * b[2] — A[2, 1] * b[1];
if (Abs(d) > 0.1) then
begin
X := d1 / d;
Y := d2 / d;
if ((((X >= mX[i]) and (X <= mX[j]) and (X >= pX) and (X <= Xn))) or
(((X <= mX[i]) and (X >= mX[j]) and (X >= pX) and (X <= Xn)))) and
((Y — pY) = 0) then
k := k + 1;

end;
end;
if (k mod 2 = 0) then
StatusBar1.Panels[0].Text := 'Точка не належить багатокутнику!'
else
StatusBar1.Panels[0].Text := 'Точка належить багатокутнику!';
end;

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

Метод трасування променя на delphi

Результат роботи delphi-проекту "Провірка приналежності точки багатокутнику"

Скачати delphi-проект «Провірка приналежності точки багатокутнику».

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар