Разложить отрезок по цветам пикселей

← →
Николай_Москва (2006-12-13 13:03) [0]

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

← →
Jeer © (2006-12-13 15:05) [1]

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

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

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

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

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

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

← →
Николай_Москва (2006-12-13 16:31) [2]

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

← →
Jeer © (2006-12-13 16:54) [3]

"Узнать хлеб на вкус можно лишь попробовав его" (С)

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

← →
MBo © (2006-12-13 17:04) [4]

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

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

← →
Vovan#2 (2006-12-13 17:40) [5]

Если бы поля также были описаны векторно, то можно было бы расчитать всё при помощи полигонов. Кстати, одноцветное поле в принципе можно трассировать в полигон. Сложность в выделении прямых в контуре.

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

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

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

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

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

← →
Сотрудник деканата (2007-02-28 17:37) [7]

Если все поля одного (или небольшого количества) цвета, то можно просто рисовать линию с методом Not или Xor, а потом искать на картинке цвет равный тому, который получится наложением цвета линии на цвет поля xor"ом или not"ом. - Будет очень-очень быстро (если нормально реализовать )).

Разложить отрезок по цветам пикселей Найти похожие ветки