Алгоритм "поиска" многоугольника

[Mihaylo]

Техническое решение: https://robotclass.ru/tutorials/opencv- ... gle-angle/

Математическое решение (из компьютерного зрения): характерные (ключевые) точки, детектор углов Харриса и т.п.
https://www.intuit.ru/studies/courses/1 ... ture/17983
Имея координаты ключевых точек, можете проанализировать наличие свойств прямоугольника между четверками точек. А потом ещё и проверить обходом

[kotenok gav]

Это совсем не то.

[Mihaylo]

Ах да, что-то я сфантазировал на счет прямоугольника.

Многоугольник "линзой", пересекаемый линией - это значит распознавание полигонов в условиях искажений и помех? Ну и такие задачи компьютерное зрение решает.

Если решили решать задачу в лоб, то тогда совет: находите узловые точки, в которых линии расходятся более, чем две стороны и запоминаете. Потом облако этих точек обрабатываете и фиксируете все связи между узловыми точками. Получится граф.
После этого другой алгоритм пробегает по всевозможным путям без повторения ребер и фиксирует замкнутые пути.

[arseniiv]

Mihaylo
Я так понял, всё же тут обычная трассировка растровой штуки в вектор, притом в одной из самых лучших постановок (чёрно-белая картинка, и поначалу не нужно упрощать полученное описание).

[kotenok gav]

Сейчас открываются обе картинки.



-- 27 апр 2020, 18:19 --

Хотя, я сейчас подумал, во втором проблем быть не должно. Но программа не работает на нем, посмотрю, в чем дело....

[arseniiv]

Ага, тоже вижу! Ну если получить контур дырки пока нет цели, то немного странно если внешний контур однозначно не определяется, если первоначально приземлиться на одну из его точек. Вы точно проводите контуры по границам пикселей (считая их квадратными), а не по их центрам?

[kotenok gav]

Ну попробуйте сами воспользоваться вашим алгоритмом вручную на первой картинке.

[arseniiv]

Я просто как обычно слишком штрихованно описал алгоритм.

Пусть мы как-то приземлились на границу фигуры, то есть в окрестности нас есть и закрашенные, и пустые пиксели. Будем теперь делать такие шаги, пока не придём назад в ту же точку $r_0$:

• Если «вектор скорости» $v$ направлен не так, что по левую сторону от него (если его отложить от текущей точки $r$) закрашенный пиксель (а справа пустой), поворачиваем его (на 90°) ровно так чтобы был направлен как надо, притом предпочитаем поворачивать в сторону, обратную направлению обхода — в данном случае по часовой стрелке — это защита от влезания внутрь.
• Смещаемся теперь $r := r + v$.

Выбор направления поворота (или сразу уж нового направления сдвига) можно притом «скомпилировать» в простой поиск в словаре по значениям $\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}$ пикселей в окрестности точки и направлению $v$, всего там будет $16\times 4$ записей. Если обозначить закрашенность как 1, пустоту как 0, то правило поворота, если сейчас $v$ направлен вверх, в точности таково:

abcd  теперь пойдём
-------------------
0000  невозможно
1000  невозможно
1100  невозможно
0100  невозможно
0110  направо
1110  направо
1010  прямо
0010  налево
0011  невозможно
1011  невозможно
1111  невозможно
0111  невозможно
0101  прямо (невозможно если начали обходить против часовой)
1101  налево (невозможно если начали обходить против часовой)
1001  налево (невозможно если начали обходить против часовой)
0001  направо (невозможно если начали обходить против часовой)

(код Грэя я себе для удобства перечисления взял). То есть тут даже всего четыре возможных окрестности оказывается (сразу я этого не увидел). Или восемь, если нам не важно иметь одно и то же направление обхода для всех случаев.

-- Пн апр 27, 2020 18:50:06 --

И да, только при рассмотрении этого примера я понял, какой именно подводный камень имелся в виду (для обхода которого я добавил «предпочитаем поворачивать в сторону, обратную направлению обхода»), так что спасибо, что заставили таки его рассмотреть.

[kotenok gav]

Спасибо!

arseniiv в сообщении #1458256 писал(а):

а справа не пустой

Вы хотели сказать "пустой"?

Но, как я понял ваш алгоритм, он обойдет только по "самой граничной" части границы, и не обойдет по "лесенке" внутри....

[arseniiv]

Да, лесенку надо обходить отдельно, это будет граница (точнее, часть двух границ) дырок (в моём понимании). Для обхода лесенки надо встать в какую-нибудь точку одной дырки, дойти до границы уже изнутри, обойти её, потом встать в другой дырке и там повторить. По идее так будет лучше, чем придумывать обход, каким-то образом создающий сразу всё. Кроме того если мы будем всегда держать закрашенное по левую руку, то мы обойдём дырки в обратную сторону по отношению к внешней границе фигуры, что для некоторых геометрических алгоритмов потом полезно (но Inkscape, думаю, не заморачивается и принимает список вершин полигона что прямой, что перевёрнутый, хотя внутри при рисовании он скорее всего где-нибудь ориентирует его одним способом).

kotenok gav в сообщении #1458273 писал(а):

Вы хотели сказать "пустой"?

Да, спасибо, поправлю.

[kotenok gav]

arseniiv в сообщении #1458278 писал(а):

что для некоторых геометрических алгоритмов потом полезно (но Inkscape, думаю, не заморачивается и принимает список вершин полигона что прямой, что перевёрнутый, хотя внутри при рисовании он скорее всего где-нибудь ориентирует его одним способом).

Это все делается не для других алгоритмов потом или Inkscape, а для возможности закрашивать фигуру в SVG.

Вероятно, действительно можно сначала закрасить там фигуру, а затем нарисовать лесенку. Но тогда надо, чтобы алгоритм вместе с полигоном возвращал и сами лесенки.

[arseniiv]

Ну мне кажется в SVG должна быть конструкция вида «такой-то контур, из которого вычтены такие-то». Попробуйте взять фигуру, продырявить её другой фигурой/фигурами с помощью вычитания, и превратить результат в контур или как там это зовётся. Потом если нажать на этот контур инструментом редактирования вершин, должно быть видно, что там три контура. (Не проверял.) Да, во, можно взять два простых полигона, одним другой продырявить, превратить в контуры и посмотреть код результата — может будет видно, как представить его.

Ещё конечно можно пойти трудным путём, которым опять же скорее всего рендерер занимается — представлением многосвязной полигональной области как объединения непересекающихся выпуклых многоугольников (или сразу треугольников), но такой низкий уровень скорее всего спускаться нет нужды, раз уж полагаемся на богатство SVG.

-- Пн апр 27, 2020 20:49:50 --

Во, глядите: https://stackoverflow.com/a/11878784/3071700.

[kotenok gav]

arseniiv в сообщении #1458304 писал(а):

Ну мне кажется в SVG должна быть конструкция вида «такой-то контур, из которого вычтены такие-то». Попробуйте взять фигуру, продырявить её другой фигурой/фигурами с помощью вычитания, и превратить результат в контур или как там это зовётся. Потом если нажать на этот контур инструментом редактирования вершин, должно быть видно, что там три контура. (Не проверял.) Да, во, можно взять два простых полигона, одним другой продырявить, превратить в контуры и посмотреть код результата — может будет видно, как представить его.

Э... Не понял, если честно. Что значит "продырявить" и "вычитать"?

[arseniiv]

А, это уже не нужно. Я дальше нашёл пример, как записать сразу область с дырками и островами в них, определяемую границами этих дырок

— нужно просто по очереди определить все эти границы, правильно ориентированные относительно друг друга (заполненная часть должна быть для всех них непосредственно по одну и ту же сторону при движении по границе) в атрибуте d одного и того же элемента path. Там синтаксис не сильно сложнее синтаксиса для polygon: код каждого контура начать с M и координат первой точки, разделённых пробелами, потом перечислить все остальные точки, начиная каждую с L, и координаты так же разделяя пробелами, и заканчивать каждый контур Z (пробелы вокруг букв можно ставить, а можно нет).

-- Пн апр 27, 2020 21:14:02 --

Вот тут есть точная спецификация синтаксиса: https://www.w3.org/TR/SVG11/paths.html#PathData.

-- Пн апр 27, 2020 21:16:46 --

(В том месте не написано о механизме раскраски, это где-то в другом.)

[kotenok gav]

А как это применить для нашего круга с лесенкой?