Re[5]: Нужен алгоритм лассо - Алгоритмы

Помогите пожалуйста, очень нужен алгоритм Лассо, как в Photoshop. Сперва я думал, что халява, но вот текущая моя реализация выпуклые области обрабатывает нормально, а восьмерку — неправильно :((. Может кто знает алгоритм?

И еще, на всякий случай. Наверное пригодится алгоритм для Magic Wand в Photoshop ( заливка области, ограниченной данным цветом, при клике мышкой в середине этой области ). Как это делать? У меня есть предположение, использовать волну, но пока не факт, что будет работать :((.

Заранее спасибо.

Здравствуйте Red_Rat, Вы писали:

RR>Помогите пожалуйста, очень нужен алгоритм Лассо, как в Photoshop. Сперва я думал, что халява, но вот текущая моя реализация выпуклые области обрабатывает нормально, а восьмерку — неправильно :((. Может кто знает алгоритм?

RR>И еще, на всякий случай. Наверное пригодится алгоритм для Magic Wand в Photoshop ( заливка области, ограниченной данным цветом, при клике мышкой в середине этой области ). Как это делать? У меня есть предположение, использовать волну, но пока не факт, что будет работать :((.

Или я что-то не понимаю....

Волшебная палка работает насколько я понимаю по простому принципу, как заливка.

Алгоритм, соответственно любой заливки.

Единственное отличие, это то что область заливания не ограничивается одним цветом, а лежит в пределах(tolerance в опциях). То есть мы кликнули по какому-то цвету и он имеет значение RGB(r,g,b). То рекурсия будет идти, пока

sqrt((r-rc)^2+(g-gc)^2+(b-bc)^2)>tolerance, где RGB(rc,gc, bc) -- цвет проверяемой точки.

Здравствуйте PSP, Вы писали:

PSP>Здравствуйте Red_Rat, Вы писали:

RR>>Помогите пожалуйста, очень нужен алгоритм Лассо, как в Photoshop. Сперва я думал, что халява, но вот текущая моя реализация выпуклые области обрабатывает нормально, а восьмерку — неправильно :((. Может кто знает алгоритм?

RR>>И еще, на всякий случай. Наверное пригодится алгоритм для Magic Wand в Photoshop ( заливка области, ограниченной данным цветом, при клике мышкой в середине этой области ). Как это делать? У меня есть предположение, использовать волну, но пока не факт, что будет работать :((.

PSP>Или я что-то не понимаю....

PSP>Волшебная палка работает насколько я понимаю по простому принципу, как заливка.

PSP>Алгоритм, соответственно любой заливки.

PSP>Единственное отличие, это то что область заливания не ограничивается одним цветом, а лежит в пределах(tolerance в опциях). То есть мы кликнули по какому-то цвету и он имеет значение RGB(r,g,b). То рекурсия будет идти, пока

sqrt((r-rc)^2+(g-gc)^2+(b-bc)^2)>>tolerance, где RGB(rc,gc, bc) -- цвет проверяемой точки.

Спасибо за инфу, я magic wand реализовал, а вот как делать лассо до сих пор не знаю. Первый вопрос остается в силе :). Буржуи на codeguru тоже не спешат отвечать :((.
Thanks.

Здравствуйте Red_Rat, Вы писали:

RR>Здравствуйте PSP, Вы писали:

PSP>>Здравствуйте Red_Rat, Вы писали:

RR>>>Помогите пожалуйста, очень нужен алгоритм Лассо, как в Photoshop. Сперва я думал, что халява, но вот текущая моя реализация выпуклые области обрабатывает нормально, а восьмерку — неправильно :((. Может кто знает алгоритм?

RR>а вот как делать лассо до сих пор не знаю. Первый вопрос остается в силе :). Буржуи на codeguru тоже не спешат отвечать :((.

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

Здравствуйте PSP, Вы писали:

PSP>А нельзя ли поподробнее, что именно там непонятно. А то я себе лассо представляю только лишь как точный выбор нужной области.

Кажется уже надумали алгоритм для лассо. Вроде на бумаге будет работать :). Сначала все точки, обведенные мышкой на картинке, надо соединить, например белыми линиями в какой-нибудь черной картинке. Потом использовать волну или другую заливку, но источник должен быть вне этой области, закрашивается вся картинка кроме контура. Затем стоит инвертировать и опять добавить границу. Будет то что надо. А чтобы волна нормально работала надо картинку в которой рисуем линии сделать немного больше исходной и тогда всегда можно будет начинать с точки 0, 0.

Спасибо за помощь.

Здравствуйте Red_Rat:

Если я правильно понял, тебе хотел алгоритм который закрашивал бы не выпуклые области. Один и способов это скан лайн. Делается просто. Вначале строим баундинг бокс нашей области (x0, y0) — (x1, y1). Теперь в цикле для y в пределах от y0 до y1, идем по горизонтальной линии (x изменяется от x0 до x1) и считать пересечения с гранями области. Попутно, если в текущий момент у нас нечетное число пересечений с краем области, закрашивая точку (x, y).

Здравствуйте Sashko, Вы писали:

На таком фоне:

- - - - - - - - - - - - - - - - - - - - -
- - - - * * * * - - - - - * * * * - - - -
- - - * - - - - * - - - * - - - - * - - -
- - * - - - - - - * - * - - - - - - * - -
- - * - - - - - - - * - - - - - - - * - -
- - * - - - - - - * - * - - - - - - * - -
- - - * - - - - * - - - * - - - - * - - -
- - - - * * * * - - - - - * * * * - - - -
- - - - - - - - - - - - - - - - - - - - -

Срежется и закрасит так:

- - - - - - - - - - - - - - - - - - - - -
- - - - * * * * - - - - - * * * * - - - -
- - - * @ @ @ @ * - - - * @ @ @ @ * - - -
- - * @ @ @ @ @ @ * - * @ @ @ @ @ @ * - -
- - * @ @ @ @ @ @ @ * - - - - - - - * @ @
- - * @ @ @ @ @ @ * - * @ @ @ @ @ @ * - -
- - - * @ @ @ @ * - - - * @ @ @ @ * - - -
- - - - * * * * - - - - - * * * * - - - -
- - - - - - - - - - - - - - - - - - - - -

А это не совсем то что надо... :-(

Здравствуйте Sashko, Вы писали:

S>Здравствуйте Red_Rat:

S>Если я правильно понял, тебе хотел алгоритм который закрашивал бы не выпуклые области. Один и способов это скан лайн. Делается просто. Вначале строим баундинг бокс нашей области (x0, y0) — (x1, y1). Теперь в цикле для y в пределах от y0 до y1, идем по горизонтальной линии (x изменяется от x0 до x1) и считать пересечения с гранями области. Попутно, если в текущий момент у нас нечетное число пересечений с краем области, закрашивая точку (x, y).

Я писал, что уже нашел алгоритм и описывал его суть. А такой алгоритм я пробовал реализовать с самого начала, но он не работал. Может конечно ручки кривые :)).
Исходно я имел границу области, соединенную линиями, вернее знал все координаты линий границы.
Потом сортировал, чтобы один раз пройти по каждой горизонтальной строке, пересекающей область.
Начинал проходить с каким то данным y. Сортировал все пересечения границ слева направо.
Проходя по строчке я считал что точка внутри области, если нечетное число пересечений, и вне если нечетное.
Но это не работает например для области 8 лежащей горизонтально. То есть именно в том месте где пересекаются две линии крест накрест происходит абзац, и часть области справа от пересечения становится незакрашенной. Еще у меня были глюки на границах области сверху и снизу, возможно еще посередине для сложных областей. Там тоже непонятно, что считать пересечением с границей, чтобы подсчитывать число четных и нечетных. Я пробовал оставлятьь только крайние точки границы, но глюки оставались.

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

Удачи.

Здравствуйте adontz, Вы писали:

A>На таком фоне:
A>

A>- - - - - - - - - - - - - - - - - - - - -
A>- - - - * * * * - - - - - * * * * - - - -
A>- - - * - - - - * - - - * - - - - * - - -
A>- - * - - - - - - * - * - - - - - - * - -
A>- - * - - - - - - - * - - - - - - - * - -
A>- - * - - - - - - * - * - - - - - - * - -
A>- - - * - - - - * - - - * - - - - * - - -
A>- - - - * * * * - - - - - * * * * - - - -
A>- - - - - - - - - - - - - - - - - - - - -
A>

A>Срежется и закрасит так:
A>

A>- - - - - - - - - - - - - - - - - - - - -
A>- - - - * * * * - - - - - * * * * - - - -
A>- - - * @ @ @ @ * - - - * @ @ @ @ * - - -
A>- - * @ @ @ @ @ @ * - * @ @ @ @ @ @ * - -
A>- - * @ @ @ @ @ @ @ * - - - - - - - * @ @
A>- - * @ @ @ @ @ @ * - * @ @ @ @ @ @ * - -
A>- - - * @ @ @ @ * - - - * @ @ @ @ * - - -
A>- - - - * * * * - - - - - * * * * - - - -
A>- - - - - - - - - - - - - - - - - - - - -
A>

A>А это не совсем то что надо... :-(

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

- - - - - - - - - - - - - - - - - - - - -
- - - - * * * .- - - - - * * * * - - - -
- - - * - - - - . - - - * - - - - * - - -
- - * - - - - - - . - * - - - - - - * - -
- - * - - - - - - - * - - - - - - - * - -
- - * - - - - - - * - . - - - - - - * - -
- - - * - - - - * - - - . - - - - * - - -
- - - - * * * * - - - - - . . * * - - - -
- - - - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - -
- - - - * * * *- - - - - . . * * - - - -
- - - * - - - - * - - - . - - - - * - - -
- - * - - - - - - * - . - - - - - - * - -
- - * - - - - - - - * - - - - - - - * - -
- - * - - - - - - . - * - - - - - - * - -
- - - * - - - - . - - - * - - - - * - - -
- - - - * * . . - - - - - * * * * - - - -
- - - - - - - - - - - - - - - - - - - - -

Здравствуйте Sashko, Вы писали:

S>Ты не прав. В центральной точке ты делаешь не одно а два пересечения. Область она задана своими гранями (ты же когда область выделяешь то ведешь мышкой, и описываешь контур) а не просто набором точек, поэтому в центральной точке ты делаешь два пересеченья, вот и все.

S>

S>- - - - - - - - - - - - - - - - - - - - -
S>- - - - * * * .- - - - - * * * * - - - -
S>- - - * - - - - . - - - * - - - - * - - -
S>- - * - - - - - - . - * - - - - - - * - -
S>- - * - - - - - - - * - - - - - - - * - -
S>- - * - - - - - - * - . - - - - - - * - -
S>- - - * - - - - * - - - . - - - - * - - -
S>- - - - * * * * - - - - - . . * * - - - -
S>- - - - - - - - - - - - - - - - - - - - -
S>

S>- - - - - - - - - - - - - - - - - - - - -
S>- - - - * * * *- - - - - . . * * - - - -
S>- - - * - - - - * - - - . - - - - * - - -
S>- - * - - - - - - * - . - - - - - - * - -
S>- - * - - - - - - - * - - - - - - - * - -
S>- - * - - - - - - . - * - - - - - - * - -
S>- - - * - - - - . - - - * - - - - * - - -
S>- - - - * * . . - - - - - * * * * - - - -
S>- - - - - - - - - - - - - - - - - - - - -
S>

Да, согласен, если мышкой.
А если COLORMASK ??? Откуда там мышам, крысам и бурундукам взятся неизместно.

Здравствуйте adontz, Вы писали:

A>А если COLORMASK ??? Откуда там мышам, крысам и бурундукам взятся неизместно.

Вообще то нужен был алгоритм когда у тебя область как раз задается контуром, и
метод скан лайнов для этого подходит. Что же касается colormask, то здесь все
значительно проще. Есть два варианта, первый, тебе нужно вырезать все что
покрашено каким-то определенным цветом (colorkey или еще как его обзывают).
Тут проблем нет:

template <class _CTy>
void RgnCutter(_CTy transp, DDSURFACEDESC& ddsd, CRgnCutter::CRectRgn& rects)
{
        _CTy *pLine = (_CTy*)ddsd.lpSurface;
//      _CTy transp = *pLine;

        for (DWORD y = 0; y < ddsd.dwHeight; y++)
        {
                _CTy *pCurrent = pLine;
                for (DWORD x = ddsd.dwWidth;;)
                {
                        // look for start of scanline
                        for (; x && *pCurrent == transp; x--, pCurrent++);

                        if (x == 0)
                                break;

                        // remember the position of scanline's start
                        DWORD startx = ddsd.dwWidth - x;

                        // look for end of scanline
                        for (; x && *pCurrent != transp; x--, pCurrent++);

                        RECT r;

                        // fill this rect with valid values
                        r.left = startx;
                        r.right = ddsd.dwWidth - x;
                        r.top = y;
                        r.bottom = y + 1;

                        rects.AddRect(r);
                }
                ((BYTE*&)pLine) += ddsd.lPitch;
        }
}

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

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

Если сильно думать не хочется (или просто нет время да и большого желанья
изобретать велосипед) то можно поискать функцию Pylogon в сорцах Wine, или
взять XFree там то же есть такая функция, как то XFillPylogon, хотя могу и
ошибаться.

Когда в университете учился нам книжку рекомендовали читать по компьютерной
графике (по 2D), там как раз многие алгоритмы рассматривались, по заливкам, по
построению линий использую только целочисленные вычисления (как то на Б
фамилия автора алгоритма была, немец по моему). Там и закраска полигона была и
закраска областей. Может кто вспомнит такую книгу да посоветует
интересующимся.

	От:	Red_Rat
	Дата:	07.10.01 19:10
	Оценка:

	От:	PSP
	Дата:	08.10.01 15:30
	Оценка:

	От:	Red_Rat
	Дата:	15.10.01 07:04
	Оценка:

	От:	PSP
	Дата:	15.10.01 11:07
	Оценка:

	От:	Red_Rat
	Дата:	16.10.01 06:19
	Оценка:

От:	Sashko	http://www.dc.baika.ru/
Дата:	10.11.01 02:33
Оценка:

От:	adontz	http://adontz.wordpress.com/
Дата:	10.11.01 11:58
Оценка:

	От:	Юнусов Булат
	Дата:	10.11.01 12:17
	Оценка: