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

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

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

metod_trasyvannja_promenja4

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

Читати повністю

Знаходження точки перетину двох прямих заданих двома точками

Нехай маємо дві прямі задані точками свого початку та кінця (перша пряма задана точками Точка перетину двох прямих таline_intersection2 і друга — line_intersection3 та line_intersection4 відповідно), для яких необхідно визначити координати точки їх перетину. Очевидне рішення даної задачі полягає в тому, щоб вирішити систему з двох лінійних рівнянь, які описують задані прямі.

Отже, якщо задані дві точки Точка перетину двох прямих і line_intersection2, то з курсу аналітичної геометрії відомо, що рівняння прямої, яке проходить через ці точки, можна записати у наступному вигляді:

line_intersection6

Отриманий вираз слід перетворити до вигляду загального рівняння прямої: line_intersection7. Для цього, звільнимо рівняння (1) від дробів, розкриємо дужки та згрупуємо доданки при невідомих.

Читати повністю

Алгоритм побудови графіка функції двох змінних

Графік функції двох змінних Графік функції двох змінних можна собі уявляти у вигляді деякої поверхні в тривимірному просторі. Для наочного зображення поверхні будемо використовувати наступний алгоритм: проведемо в просторі площину grafik_funkcii_3d4, паралельну осям grafik_funkcii_3d5 і grafik_funkcii_3d6. Тоді перетин даної площини з поверхнею функції є деяка крива — графік функції однієї змінної grafik_funkcii_3d7. (правда, розташований цей графік під певним кутом до площини екрану). Змінюючи значення константи з деяким кроком, ми отримаємо сімейство таких кривих.

Графік функції 3D

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

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

Читати повністю

Побудова графіка функції в середовищі програмування delphi використовуючи компонент Chart

При створенні delphi-проектів, які реалізують розглядувані на даному сайті чисельні методи, доволі часто виникає необхідність виводу графічного представлення певної функції. Наприклад, при програмній реалізації знаходження екстремума функції, ми здійснювали побудову графіка даної функції, і таким чином виконували перевірку правильності роботи того чи іншого методу. Алгоритм побудови графіка функції на канві форми, було розглянуто за посиланням Побудова графіка функції в середовищі програмування delphi. Согодні розглянемо дещо простіший спосіб, який базується на використанні спеціального компонента для виведення готовиг графічних зображень, а саме компонент Chart. Зокрема, даний компонент (знаходиться на закладці Additional палітри компонентів delphi) дозволяє будувати різноманітні діаграми та графіки.

Читати повністю

Малюємо графік функції однієї змінної в середовищі програмування delphi

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

Для побудови графіка по заданому аналітичному опису функції необхідно обчислити масив значень аргументу і масив відповідних значень функції. Крок зміни аргументу залежить від кількості точок на які розбивають діапазон зміни аргументу і обчислюється за наступною формулою:

Побудова графіка функції

де Побудова графіка функції — крок зміни аргумента; Побудова графіка функції — максимальне значення аргумента; Побудова графіка функції — мінімальне значення аргумента; Побудова графіка функції — задана кількість точок графіка.

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

Читати повністю

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

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

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

Читати повністю

Перехід від одного плану перевезень в транспортній задачі до іншого використовуючи цикл перахунку

Перерозподіл перевезень в транспортній задачі з метою поліпшення рішення відбувається по циклу (відомий як цикл перерахунку). Даний цикл в транспортній таблиці являє собою сукупність клітинок, з'єднаних замкнутою ламаною лінією, яка в кожній клітинці робить поворот на 90 градусів, і обов'язковою вимогою є те, що в кожному рядку і кожному стовпці, по яких проходить цикл, повинно бути дві і тільки дві вершини. Також слід відмітити, що кожен цикл перерахунку складається з парного числа вершин, одна з яких міститься у вільній клітинці, а інші — у заповнених. Якщо відрізки ламаної лінії перетиноються, то точка перетину вершиною не вважається. Для кожної вільної клітини можна побудувати цикл перерахунку і при чому єдиний.

Графічне представлення циклу перерахунку

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

Читати повністю

« Попередня сторінкаНаступна сторінка »