Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 05.03.2011, 17:12
Новичок

Отправить личное сообщение для Wilko Посмотреть профиль Найти все сообщения от Wilko
 
Регистрация: 05.03.2011
Сообщений: 3

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

Линия любого цвета, толщина >=1 пиксель, цвет фона белый.
  #2  
Старый 07.03.2011, 02:35
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

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

Сам недавно оперировал с изображением так...
  #3  
Старый 07.03.2011, 03:33
гocть

 
Сообщений: n/a

Сообщение от Wilko Посмотреть сообщение
Допустим, у нас есть изображение линии на белом фоне.
ну тогда в чем проблема просто вывести все точки отличные от белых?
  #4  
Старый 07.03.2011, 04:58
Новичок

Отправить личное сообщение для Wilko Посмотреть профиль Найти все сообщения от Wilko
 
Регистрация: 05.03.2011
Сообщений: 3

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

 
Сообщений: n/a

найди все не-белые точки, восстанови методом наименьших квадратов параметры прямой, и уже по уравнению считай со своим шагом
  #6  
Старый 07.03.2011, 07:18
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

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

Я, правда, не пытался писать подобные алгоритмы. Но примерно суть решения задачи построил именно так
  #7  
Старый 07.03.2011, 15:49
Новичок

Отправить личное сообщение для Wilko Посмотреть профиль Найти все сообщения от Wilko
 
Регистрация: 05.03.2011
Сообщений: 3

Все хорошо, вот только трассировать нужно не всегда прямую линию. Нашел алгоритм, но уж очень он замудреный с точки зрения математики((
  #8  
Старый 10.03.2011, 13:10
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Более оптимальный алоритм определения принадлежности точки полигону, чем трассировка wDevil Математические алгоритмы 6 10.12.2009 17:57
Помогите с кодом для утончения линии в делфи!!! гость Реализация, исходники, языки 0 01.05.2008 19:34
Изгиб (bend) линии в 2D Colombo Обработка изображений, звук, графика 2 05.02.2007 15:51
решение линии японского кроссворда iposov Задачи 1 14.10.2006 03:22