Алгоритм провірки приналежності точки відрізку

В процесі розробки delphi-проектів, в основу яких закладено взаємодію користувача з графічними примітивами (точками, лініями, еліпсами, прямокутниками), доволі часто виникає потреба виконувати певні дії з активними об'єктами, тобто з об'єктами над яким, наприклад, містииться курсор чи було натиснуто кнопку миші. В такому випадку, перед нами постає задача визначення приналежності точки певному об'єкту. Відмітимо, що з такою проблемою ми зустрічалися при розробці проектів, які реалізують алгоритми на графах, а саме при візуалізації графа. Тобто, при видалення ребра ми розглядали задачу на приналежність точки відрізку, де в якості точки брались координати мишки, а я якості  відрізка — ребро графа. А при переміщенні чи видаленні вершин — задачу на приналежність точки еліпсу.

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

identity_point_interval10

і при цьому, абсциса точки identity_point_interval6 повинна задовольняти одну з нерівностей: identity_point_interval7 або identity_point_interval8. В інакшому випадку точка identity_point_interval6 буде міститись на прямій, але лівіше або правіше відрізка identity_point_interval9.

Для того, щоб уникнути випадку ділення на нуль і можливості використання формули для будь-яких вхідних даних, рівність (1) можна переписати у наступному вигляді:

Приналежність точки прямій

Отже, відкриємо Borland Delphi, створимо новий проект, та добавимо в розділ опису змінних даного модуля чотири глобальні змінні цілого типу. Після цього, напишемо функцію, яка перевірятиме приналежність довільної точки відрізку, заданому координатами свого початку і кінця.

var
X1, X2, Y1, Y2: integer;
function TForm1.point_identity(X1, Y1, X2, Y2, X3, Y3: integer): boolean;
var
res: boolean;
r1, r2, r3: real;
begin
r1 := ((X3 — X1) * (Y2 — Y1));
r2 := ((Y3 — Y1) * (X2 — X1));
r3 := r1 — r2;
if (abs(r3) <= 100) and (((X3 > X1) and (X3 < X2)) or ((X3 > X2) and (X3 < X1))) then
res := true
else
res := false;
point_identity := res;
end;

Далі, на подію OnPaint форми Form1 напишемо код, який використовуючи функцію RandomRange буде генерувати координати початку та кінця відрізка, та малювати його на канві форми. Відмітимо, що на відміну від функції Random, delphi-функція RandomRange дає можливість вказати діапазон, в межах якого необхідно згенеровати довільне ціле число.

procedure TForm1.FormPaint(Sender: TObject);
begin
Randomize;
X1 := RandomRange(100, Form1.Width — 100);
Y1 := RandomRange(100, Form1.Height — 100);
Form1.Canvas.MoveTo(X1, Y1);
X2 := RandomRange(100, Form1.Width — 100);
Y2 := RandomRange(100, Form1.Height — 100);
Form1.Canvas.LineTo(X2, Y2);
end;

І на останньому кроці, на подію OnMouseMove головної форми проекту напишемо код, який використовуючи вище реалізовану функцію point_identity, буде провіряти приналежність точки координатами якої є положення курсора мишки до намальованого відрізка і вже в залежності від цього, змінювати курсор мишки.

procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X, Y: Integer);
begin
if (point_identity(X1, Y1, X2, Y2, X, Y)) then
Form1.Cursor := crHandPoint
else
Form1.Cursor := crDefault;
end;

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

identity_point_interval12

Інтерфейс delphi-проекту який здійснює провірку приналежності точки відрізку

Скачати delphi-проект який здійснює провірку приналежності точки відрізку.

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

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