Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Разложить отрезок по цветам пикселей [D7, WinXP]

Николай_Москва © (2006-12-13 13:03:00)
Привет!
Хочу узнать, существует ли простой алгоритм для решения одной задачи (постановку упрощаю - сама программа будет намного сложнее):
Существует рисунок, загруженный в Image. На нем отрисовано некоторое поле, закрашенное определенным цветом. Области рисунка, на которые не попадает поле, закрашены другим цветом. Существует некоторый массив отрезков (заданы координатами начала и конца x1, y1, x2, y2). Все отрезки последовательно будут отрисованы на рисунке с полем. Интересует следующий вопрос:
Как при рисовании каждого отрезка [х1, y1], [x2, y2] определить , попадает ли он в одно или другое поле (отличие полей по цвету), попадает полностью или частично и т.д.
Вариант решения задачи "в лоб" - анализировать все точки попиксельно, между [x1, y1] и [x2, y2] подряд или с каким-то шагом, при этом, как всегда учесть случаи, когда x1 и x2 совпадают и прочие условия. Хочу узнать, может существует более оптимальный вариант алгоритма.
Спасибо.

Сотрудник деканата (2007-02-28 17:37:00) [1]
Если все поля одного (или небольшого количества) цвета, то можно просто рисовать линию с методом Not или Xor, а потом искать на картинке цвет равный тому, который получится наложением цвета линии на цвет поля xor'ом или not'ом. - Будет очень-очень быстро (если нормально реализовать )).

ors_archangel (2006-12-16 08:52:00) [2]

> Возможно, заранее нужно прочтитать рамки или даже грубые
> полигоны, которые точно принадлежать одному из полей.

Например, можно сделать quad-tree: делим исходный прямоугольник на четыре, если подпрямоугольник полностью одного цвета, то отмечаем это, иначе - признак смешанного цвета запоминаем, рекурсивно делим полученные прямоугольники, дальше при анализе каждого отрезака возможно ускорение, если области не слишком перемешаны, т.к. проверки будут происходить не попиксельно, а кусками - прямоугольниками, это довольно просто, не если число отрезков не велико, то предрасчёт может оказаться черезчур затратным :(

Vovan#2 (2006-12-13 17:40:00) [3]
Если бы поля также были описаны векторно, то можно было бы расчитать всё при помощи полигонов. Кстати, одноцветное поле в принципе можно трассировать в полигон. Сложность в выделении прямых в контуре.

> Как при рисовании каждого отрезка [х1, y1], [x2, y2] определить , попадает ли он в одно или другое поле (отличие полей по цвету), попадает полностью или частично и т.д.

Вот тут вопрос. Определить нужно до рисования отрезка или можно после? Если после, то можно совместить приятное с полезным. Иначе методом пикселей будет двойная работа. (Я так полагаю, требуется всё-же до рисования, иначе проблемы нет)

Оптимизация. Быстрый алгоритм линии. Возможно, заранее нужно прочтитать рамки или даже грубые полигоны, которые точно принадлежать одному из полей. Опять же, всё это нужно потестить на скорость - не обязательно это спасение.

MBo (2006-12-13 17:04:00) [4]
возможно, подойдет какая-нибудь бибилиотека работы с полигонами, например

http://www.cs.man.ac.uk/~toby/alan/software/index.html

Jeer (2006-12-13 16:54:00) [5]
"Узнать хлеб на вкус можно лишь попробовав его" (С)

Работа с пикселями:
- *.Pixels[x,y]
- *.ScanLine[row] (быстрее)

Николай_Москва (2006-12-13 16:31:00) [6]
отрезок может пересекаться несколькими полями, т.е. некоторые его точки будут входить в поле, а некоторые нет. Конечно, будут случаи, когда отрезок будет полностью в поле или нет.
Все в виде карты (просто не стал подробно писать) поэтому длины отрезков (это участки трасс) будут в несколько сотен км. Поля или их фрагменты будут и большие и маленькие. В программе, ес-но, все будет в масштабе...
Критерий оптимальности - я с рисованием на канве работал мало, метод решения "в лоб", который я представляю написан выше. Но возможно, существуют функции в составе каких-либо библиотек, которые облегчат или затруднят такой или подобный анализ. Если нет, то не буду тратить время на поиск. А если есть - хорошо бы знать, т.к. у заказчика иногда аппетит приходит во время еды.

Jeer (2006-12-13 15:05:00) [7]

> сама программа будет намного сложнее):

Радует, что людей интересуют сложные задачи.

> может существует более оптимальный

Критерий оптимальности не озвучен.

> Вариант решения задачи "в лоб" - анализировать все точки
> попиксельно

Почему нельзя решать вопрос о принадлежности области только лишь конечных точек ?

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »