Трассировка растровой линии

[Wilko]

Необходимо разработать алгоритм "трассировки" или обхода растровой линии.
Допустим, у нас есть изображение линии на белом фоне. Необходимо пройти вдоль этой линии(с некоторым шагом), и получить таблицу значений X/Y, которые соответствуют точкам на линии. Вся проблема в том, что проход по X или Y осям не подходит, т.к. при горизонтальных/вертикальных линиях точки не будут учитываться. Также будут пропускаться пиковые значения.

Линия любого цвета, толщина >=1 пиксель, цвет фона белый.

[Vertex]

Дабы облегчить задачу, можно хранить изображение в 32 битах - RGB+Alpha. Сначала любое цветное изображение сдублировать в Альфа-маску, а там уж всё остальное делать.

Сам недавно оперировал с изображением так...

Допустим, у нас есть изображение линии на белом фоне.

ну тогда в чем проблема просто вывести все точки отличные от белых?

[Wilko]

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

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

[Vertex]

У меня как-то была идея трассировки линии по первым ступеням.
Т.е. трассируем первые три-четыре ступени с поиском периодичности. Затем вычисляем соотношения x/y и уже циклом бежим по этому вектору, сверяясь с трассируемой линией. Таким образом можно искать линии точечной толшины.
То же самое и с окружностями.

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

[Wilko]

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

[lordKelvin]

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