1

Тема: Алгоритми побудови шляху по краям зображення

Які ви знаєте алгоритми побудови шляху (масив впорядкованих координат) на основі країв зображення?
типу як на картинці
https://image.prntscr.com/image/gmTCZyrnQzmTHqhsiDWKAA.png
на вхід маємо масив пікселів картинки

2

Re: Алгоритми побудови шляху по краям зображення

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

Подякували: LoganRoss, FakiNyan2

3

Re: Алгоритми побудови шляху по краям зображення

я так колись і робив, але то якось не дуже круто було. Мають бути крутіші алгоритми, котрі кращі за це.
Я вже надибав один, зветься marching squares, завтра буду розбиратися

4

Re: Алгоритми побудови шляху по краям зображення

http://s11.postimg.org/h9w5qro0z/fence.gif
отакий?

5

Re: Алгоритми побудови шляху по краям зображення

ping написав:

http://s11.postimg.org/h9w5qro0z/fence.gif
отакий?

ні

6

Re: Алгоритми побудови шляху по краям зображення

не такі страшні ті маршируючі квадрати, як я думав
https://cdn.discordapp.com/attachments/304621192134918146/324957838101184522/unknown.png
https://cdn.discordapp.com/attachments/304621192134918146/324957885396418564/unknown.png

тепер тілько треба зробити, аби воно якось вирішувало питання, коли два контури зливаються, рішення так-то вже є, але мені ліньки зараз його дороблювати.
https://cdn.discordapp.com/attachments/304621192134918146/324958150648135681/unknown.png

а озьдо 512 x 512
https://cdn.discordapp.com/attachments/304621192134918146/324960361960964106/unknown.png

Подякували: LoganRoss, 0xDADA11C7, ostap34PHP3

7

Re: Алгоритми побудови шляху по краям зображення

https://i.imgur.com/EB062xy.gif

х'юстон. у нас проблєма

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

проблема в тому, що воно не заходить в маленькі тріщинки, і деякі частини контуру залишаються незадіяними.
Коли шлях побудований, то алгоритм перевіряє інші пікселі, в пошуках червоних пікселів, бо на одній картинці може бути декілька контурів.
І от з тими незадіяними пікселями треба щось зробити.
1. Задіяти їх
2. Відкидати їх

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

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

Що думаєте?
Мені тре якомога швидший спосіб пошуку шляху, тому що картинки будуть змінюватися в рантаймі, і кожного разу треба буде будувати шлях.
З контуром особливих проблем нема, тому що мені потрібно буде змінити лише ту частинку контура, котра була змінена, тобто я можу побудувати bounding box, і малювати лише ту частину контура, котра знаходиться в ньому. Але після цього треба будувати шлях, а він з себе представляє масив точок, що мають координати, тому його доведеться будувати заново.

8

Re: Алгоритми побудови шляху по краям зображення

постало питання, як зрозуміти, ми знаходимось всередині контуру, чи ззовні?

9 Востаннє редагувалося FakiNyan (18.06.2017 16:10:40)

Re: Алгоритми побудови шляху по краям зображення

граюсь з бектрекінгом, бо старий алгоритм пошуку шляху поламався
http://i.imgur.com/Mdc9Ly3.gif

10

Re: Алгоритми побудови шляху по краям зображення

FakiNyan написав:

постало питання, як зрозуміти, ми знаходимось всередині контуру, чи ззовні?

Це відносно. Можна тільки визначити, чи точки "з різних боків лінії" (провести між ними пряму і знайти перетини цієї прямою лінії, якщо кількість непарна - з різних боків).

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

11

Re: Алгоритми побудови шляху по краям зображення

koala написав:
FakiNyan написав:

постало питання, як зрозуміти, ми знаходимось всередині контуру, чи ззовні?

Це відносно. Можна тільки визначити, чи точки "з різних боків лінії" (провести між ними пряму і знайти перетини цієї прямою лінії, якщо кількість непарна - з різних боків).

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