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

[kotenok gav]

Скажем, у нас есть картинка, и на ней пикселями задан многоугольник (причем он может быть и не совсем многоугольником, скажем, "линза", деленная линией пополам).
Какой можно сделать алгоритм нахождения порядка "отрисовки" вершин многоугольника, для того, чтобы потом использовать это как polygon в SVG?

Гугл молчит.
Сам пытался пробовать делать алгоритм хождения в противоположном направлении (т.е. направление, откуда пришел) "поворачивая" такую стрелку в противоположном направлении против часовой, и смотря, где она пересеклась с многоугольником, и алгоритм хождения в "прямом" направлении, поворачивая стрелку по часовой. Но есть примеры, где оба этих алгоритма не работают.

[arseniiv]

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

Или не то?

[kotenok gav]

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

То есть есть какое-то связное множество, склеенное из квадратиков квадратной сетки, и вы ходите по их центрам, пытаясь получить ломаную, которая будет содержать все центры квадратиков этого множества?

Да, правильно. Только не центров, а просто квадратиков (это пиксели) и надо, чтобы ломаная содержала вершины в правильном порядке.

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

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

Хм, хорошая идея. Надо будет подумать.

-- 25 апр 2020, 00:59 --

В случае многоугольника, похоже, так получится. А в случае

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

"линза", деленная линией пополам

?

[arseniiv]

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

А потом вы собирались упрощать границу? А то больно задача на трассировку растровой картинки похожа. Если так, то по алгоритмам трассировки по идее должна быть какая-то литература… я только не знаю какая, не интересовался.

[kotenok gav]

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

Похоже, это и есть трассировка, спасибо!
Погуглю.

[arseniiv]

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

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

Ну да, до четырёх, но ведь только те соседи, которые «дышат воздухом», нам интересны.

[kotenok gav]

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

Ну да, до четырёх, но ведь только те соседи, которые «дышат воздухом», нам интересны.

Скажем, в такой линзе у начальной точки будут четыре соседа, в одном из которых мы уже были. Если мы будем выбирать следующего соседа случайно, есть риск не пойти по какой-то линии.

[arseniiv]

Да, всё-таки я наверно не понял как она выглядит… Нарисуйте как-нибудь.

[kotenok gav]

Линзой я называю что-то типа такого:
https://hostingkartinok.com/show-image.php?id=138731750ff610c1e30b8abc4caaf05f

[arseniiv]

[kotenok gav]

Еще будут проблемы с таким:
https://hostingkartinok.com/show-image.php?id=42e2ad14cc7d13a956b2b3ddbcad4d7b

-- 25 апр 2020, 03:05 --

Странно, у меня открывается.

[wrest]

В качестве идеи. "Правильный порядок" -- такой, при котором длина (периметр) минимальна и нет самопересечений.

[arseniiv]

Если переходить по прямой ссылке типа https://s8.hostingkartinok.com/uploads/images/2020/04/42e2ad14cc7d13a956b2b3ddbcad4d7b.png, фаерфокс говорит такое:

Цитата:

Ошибка при установлении защищённого соединения

При соединении с s8.hostingkartinok.com произошла ошибка.

• Страница, которую вы пытаетесь просмотреть, не может быть отображена, так как достоверность полученных данных не может быть проверена.
• Пожалуйста, свяжитесь с владельцами веб-сайта и проинформируйте их об этой проблеме.

Может быть это проблема с предлагающим провайдерам блокировать всё подряд роскомнадзором, не знаю.

-- Пт апр 24, 2020 21:45:26 --

Если вставить её в img, то форум пишет «не удалось определить размеры изображения», хм. Ожидалось бы наверно что не должен.

P. S. Ссылка в посте ниже тоже не открывается.

[kotenok gav]

Прямая ссылка на первую картинку:
https://s8.hostingkartinok.com/uploads/ ... aaf05f.png

-- 25 апр 2020, 03:17 --

А вот вторая у меня тоже не открывается.

[wrest]

kotenok gav
На радикал залейте :)