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

[kotenok gav]

Вау, круто! Посмотрю завтра на моем примере.

[kotenok gav]

Ваша программа возвращает "M 121 36 L 121 37 L 122 37 L 123 37 L 124 37 L 124 38 L 123 38 L 122 38 L 122 39 L 123 39 L 124 39 L 125 39 L 126 39 L 127 39 L 128 39 L 128 40 L 129 40 L 130 40 L 131 40 L 131 39 L 132 39 L 133 39 L 133 38 L 134 38 L 135 38 L 136 38 L 137 38 L 138 38 L 139 38 L 139 37 L 140 37 L 140 36 L 139 36 L 138 36 L 137 36 L 137 35 L 136 35 L 135 35 L 134 35 L 134 34 L 135 34 L 136 34 L 137 34 L 138 34 L 138 35 L 139 35 L 140 35 L 141 35 L 141 34 L 141 33 L 140 33 L 140 32 L 141 32 L 141 31 L 140 31 L 139 31 L 139 30 L 138 30 L 138 29 L 138 28 L 137 28 L 137 27 L 136 27 L 136 26 L 135 26 L 134 26 L 134 25 L 133 25 L 132 25 L 131 25 L 130 25 L 129 25 L 128 25 L 127 25 L 127 26 L 126 26 L 125 26 L 125 27 L 124 27 L 123 27 L 123 28 L 122 28 L 122 29 L 121 29 L 121 30 L 121 31 L 121 32 L 121 33 L 121 34 L 121 35 L 122 35 L 122 36 z M 121 35 L 120 35 L 119 35 L 118 35 L 118 36 L 119 36 L 120 36 L 121 36 z". Это почти то, что надо, но не совсем... Вот результирующая картинка: https://jsfiddle.net/b8dfqw60/ Посмотрите на нее и исходную попиксельно.

[kotenok gav]

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

Ну, можно попробовать использовать не SVG, а canvas. Тогда надо решить несколько другую задачу - найти координаты всех точек внутри нашей фигуры (или, что эквивалентно, найти алгоритм определения, принадлежит ли точка ее внутренности).

Кажется, это очень просто! Вот мы рассматриваем ряд пикселей. Сначала не закрашиваем, затем, когда встречаем пиксель фигуры, начинаем красить, следующий пиксель фигуры - перестаем красить, и так далее... Но такой алгоритм работает не всегда - скажем, если в ряду несколько пикселей фигуры подряд (но это легко лечится), или если в ряду "пиксель-угол", скажем, если у нас картинка треугольника...

[kotenok gav]

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

или если в ряду "пиксель-угол", скажем, если у нас картинка треугольника

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

[arseniiv]

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

и загляните в тему о алгоритме "поиска" многоугольника, конечно же

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

Я заглянул, но не понял опять, чего требуется.

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

Я говорил о сообщении post1466838.html#p1466838...

Хм, хм, ну я всё равно не понял, неужели там что-то лишнее заливается или что-то недозаливается?..

[kotenok gav]

Я точно не помню уже, что там не так, но, кажется, проблема была в "лесенке" (в оригинале оно было примерно так:
....+
...+.
..+..
.+...
+...., а становится так:
....+
...++
..++.
.++..
++...).

[arseniiv]

Хм, странно. Точно дело не в обводке (stroke)? (У вас в примере она включена; вообще ей можно задавать произвольную толщину и не помню, какие в SVG умолчания на этот счёт.) Заливка сама по себе должна была залить только нужные пиксели, обводка это уже сущность хитрая и в моей модели квадратных пикселей не учтённая.

[kotenok gav]

Хм... Без обводки действительно работает, кажется, спасибо! Только тогда возникает встречный вопрос: можно ли написать алгоритм, который выводит path, который сам является правильной обводкой (ну, т.е., этот path будет выводить пиксели границы)?

[arseniiv]

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

[kotenok gav]

Не, я говорил не совсем об обводке, а об исходном контуре...

[arseniiv]

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