Більше

Вимірювання прямолінійності сегмента кривої (представленої у вигляді полілінії)


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

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

Я шукав відповіді, але не знайшов нічого дійсно корисного. Буду вдячний за будь -які підказки.


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

Наприклад, припустимо, ви маєте намір проводити систематичний пошук по всій з’єднаній складовій контуру, представленої у вигляді послідовності точок P (0), P (1),…, P (n). Це буде зроблено шляхом ініціалізації одного покажчика (індексу в послідовності) s = 0 ("s" для "початку"), а іншого вказівника f (для "фінішу") буде найменшим індексом, для якого відстань (P (f), P (s))> = 100, а потім просування s до такої відстані (P (f), P (s+1))> = 100. Це створює полілінію -кандидата (P (s), P (s+ 1)…, P (f-1), P (f)) для оцінки. Оцінивши його "придатність" для підтримки мітки, ви б збільшили s на 1 (s = s+1) і продовжили збільшувати f до (скажімо) f 'і s до s', поки ще раз кандидатська полілінія не перевищить мінімальну виходить діапазон 100, представлений у вигляді (P (s '), ... P (f), P (f+1), ..., P (f')). При цьому вершини P (s)… P (s'-1) випадають з попереднього кандидата і до нього додаються вершини P (f+1),…, P (f '). Дуже бажано, щоб фітнес можна було швидко оновлювати, знаючи лише про скинуті та додані вершини. (Ця процедура сканування буде продовжуватися до s = n; як зазвичай, f має бути дозволено "обертатися" від n назад до 0 у процесі.)

Це міркування виключає багато можливих показників придатності (звивистість, звивистість тощо), які в іншому випадку можуть бути привабливими. Це спонукає нас віддати перевагу заходам на основі L2, оскільки вони, як правило, можуть швидко оновлюватися, коли основні дані дещо змінюються. Проводячи аналогію з аналізом основних компонентів, ми пропонуємо взяти до уваги наступну міру (де мале краще, як вимагається): використовувати менші з двох власних значень матриці коваріацій координат точки. Геометрично це є одним із показників "типового" відхилення сторін у бік вершин у розділі-кандидаті полілінії. (Одне з тлумачень полягає в тому, що його квадратний корінь-це менша піввісь еліпса, що представляє другі моменти інерції вершин полілінії.) Він буде дорівнювати нулю лише для множин колінеарних вершин; в іншому випадку воно перевищує нуль. Він вимірює середнє відхилення в бік відносно базової лінії 100 пікселів, створеної початком і кінцем полілінії, і тому має просту інтерпретацію.

Оскільки матриця коваріацій становить лише 2 на 2, власні значення швидко знаходять шляхом розв’язання одного квадратного рівняння. Більш того, коваріаційна матриця - це сума внесків з кожної з вершин у полілінії. Таким чином, він швидко оновлюється, коли точки випадають або додаються, що призводить до алгоритму O (n) для n-точкового контуру: це буде добре масштабуватися до дуже детальних контурів, передбачених у додатку.

Ось приклад результату цього алгоритму. Чорні точки - це вершини контуру. Суцільна червона лінія є найкращим кандидатом на відрізок полілінії довжиною від кінця до кінця більше 100 у цьому контурі. (Візуально очевидний кандидат у верхньому правому куті недостатньо довгий.)


У спільноті комп’ютерної графіки часто доводиться знаходити обмежувальну рамку навколо об’єкта. Отже, це добре вивчена проблема з швидкими алгоритмами. Наприклад, див. Статтю про мінімальні обмежувальні рамки Вікіпедії. Ви можете знайти прямокутник із мінімальною площею навколо вашої полілінії, а потім використовувати співвідношення сторін прямокутника, висоту/довжину. Щоб отримати більш точне вимірювання, можна подивитися на відхилення полілінії від центральної лінії цього обмежувального прямокутника.


Я не знаю, чи це допомагає, чи навіть вважається це відповіддю, але коли я сидів тут і думав над питанням, яке я щойно опублікував, у мене з’явилася думка:

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

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

Я впевнений, що це не надто допомагає, і те, що я говорю англійською, набагато складніше в будь -якій мові програмування, яку ви використовуєте, але це може бути початком?


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

Це рішення має бути дійсно простим у реалізації.


Оновлення: Як Майк правильно помітив, це буде дорівнює Sinuosity.


Шукаючи "кривизну" та "полілінію", я отримав цю інформацію Як я можу знайти кривизну полілінії ?. Там він запропонував повернутися до визначення кривизни- K = DF/Ds. Тут поFвін має на увазіфі, абоТу позначенні Вікіпедії тут (http://en.wikipedia.org/wiki/Curvature).

Скажімо, у вас є послідовність з трьох точок, p0, p1 і p2. обчислити відстаньsміж p0 і p1, дельта дельта s (Ds), припускаючи, що точки близькі один до одного. Тоді вам потрібна дельта T (DT), що є зміною одиничного тангенціального вектора між p0 і p1. може бути складний спосіб, але грубий метод, який я можу придумати, взяти два бектори p0-> p1, p1-> p2, нормалізувати кожен, щоб мати довжину одиниці, потім взяти векторне віднімання цих двох, а потім визначити величину. ТобтоDT. Поділ дає кривизнуK0_1. візьміть p1, p2 і p3 для обчисленняK1_2і так далі.

Мені цікаво, однак, якщо ви отримаєте контур як полілінію, а не як візуалізовані пікселі. Ви сказали 100 пікселів, тому я трохи хвилююся.


Перегляньте відео: Полилинии в Автокаде. Всё о полилиниях в AutoCAD (Жовтень 2021).