Здравствуйте, Mika Soukhov, Вы писали:
MS>Здравствуйте, Рома Мик, Вы писали:
MS>Народ, можно как нить по проще и понятнее (без воды 
). Я математику уже стал поздзабывать, так, плиз, еще и по доходчивее 
Да вроде никакой воды...
А расписать все подробно и по пунктам — это как код написать, а код написать — это за деньги и потом, или за большие деньги...
... << RSDN@Home 1.1 beta 2 >>
КО>>попали в сказку и кто-то подарил нам такую цепочку пикселов (массив пикселов от 1 до n, причем у каждого пиксела кроме концов ровно два соседа (если брать 8-связность)),
РМ>Ну составить такую цепочку было бы не проблематично, но ИМХО она и не нужна. И можно брать больше чем 8-связности.
Если честно, я плохо представляю себе, а как без цепочки?
Было бы классно знать более-менее конструктивный способ, использующий такой массив с утолщениями и аномалиями (а не цепочку):
"толщина" массива может быть 2 и более пикселя
могут быть самопересечения и вообще всякие утолщения, как на рисунке
буквы, пятна и прочие дефекты вырезаны не были
Я бы в принципе мог выложить код, который разбивает Микину картинку на примерно такие массивы
А связности — да, согласен, я порассматривал Микину картинку через лупу
— конечно, ужас
Но ты прав, отчаиваться не стоит — вон люди из Adobe как умеют, не говоря уже об орлах из Abbyy... Понятно, задача решаемая. Но сложная.
Так вот. Предлагаю взять такую связность:
01110
11111
11*11
11111
01110
Здесь для пиксела "*" соседними будут считаться пикселы "1". Так мы соединим разрывы в 1 пиксел, но не более (а этого и достаточно, остальные разрывы будем считать двумя кусками).
РМ>Совсем точно не найдем, найдем менее точно: кусочки кривой безье будут покороче, но все равно будут. А искать, я бы искал так: берем прямую, проходящую нашу точку и вращаем ее ( вариантов углов поворота не так много, так как прямая наша довольно коротка ), какой вариант покрывает наибольшее число точек нашей кривой, тот и есть искомое направление. Кроме того количество покрытых пикселей явно должно коррелировать с длиной вектора от первой ко второй точке. А более точного направления нам не надо, так как его просто и нет в природе, поскольку задана то нам только множество точек в которое можно вписать сколько хочешь кривых.
Да, вообще да. Я подумал, твой фокус с прямой можно оптимизировать. Подбирать ее не нужно — ее можно восстановить по алгоритму Брезенхема. Смотри — прямая рисуется как набор горизонтальных или вертикальных отрезков примерно равной длины. Я имею ввиду:
0000000*00
0000000*00
000000*-00
0000**0000
00+*000000
0000000000
Здесь на рисунке + это начало нашей будущей кривой, а звездочки — пикселы, которые надо покрыть. Минусом на рисунке отмечен пиксел, где цепочка начинает уклоняться от прямой. Смотрим — ага, первое время это состыкованные горизонтальные отрезки по два пиксела — вот и будем продолжать этот "паттерн" (узор), пока вписываемся в алгоритм Брезенхема. Как получим очередной отрезок неправильной длины (там, где минус — горизонтальная полоска из 1 пиксела, а не из двух) — значит цепочка отклонилась от прямой. Теперь то, что уже насчитали (от плюса до минуса) — часть нужной нам касательной прямой. Ее уравнение найти просто — она проходит через исходную точку (+ на рисунке) и угловой коэффициент — разделить разность игреков плюса и минуса на разность иксов.
КО>>Мои воздушные рассуждения о том, что поиск второго конца можно прерывать после нахождения третьего обнуления кривизны.
РМ>ИМХО поиск можно прерывать, когда например из десяти наскоро посчитанных точек кривой две окажутся вне множетсва точек.
Это эмпирика. К тому же мне кажется, ты как-то скромно берешь — с таким же успехом отлично можно и отрезками приближать.
КО>>Опять же, достаточно точно оценить кривизну в нашей дискретной задаче скорее всего не удастся.
КО>>Как искать удаление направляющих точек от концов кривой — вообще неясно (ну т.е. мне не ясно 
)
РМ>Я там выше писал про покрытие точек прямой, так вот их кол-во после какого-то несложного преобразования ( возможно по таблице, полученной эмпирически ) должно дать примерное значение, вокруг которого можно искать перебором или даже оставить так.
Да, но перебор все-таки достаточно большой...
РМ>Ну использование более чем 8-связности от маленьких разрывов убережет, а большие пусть и остаются — получится две линии вместо одной и все.
ОК.
КО>>изломы, самопересечения,
РМ>В принципе при вращении кривой эти штуки опредятся как два максимума только в одной стороне ( изломы ) два максимума с обеих сторон ( пересечения ). В изломах можно и прервать кривую, а в пересечениях продолжатьь в нужном направлении.
Щас, я не понял. Что ты имеешь ввиду? Здесь можешь поподробнее плз?
КО>>замкнутость в кольцо,
РМ>Где тут проблема?
ОК ОК согласен
КО>>толщина в 2 и больше пиксела (а толщина в два пиксела, зараза, сплошь и рядом встречается на приведенной картинке),
РМ>Не страшна. Какие проблемы она создает?
Да понимаешь — вот у нас массив пар (x,y) от 1 до 10000. Больше ничего не знаем. И что с этим делать?
Как ты поймешь, что кривую нужно направлять в "самую тонкую сторону"? И глянь на рисунок — там есть жирные перекрестки из пяти и больше таких "кишок"... Че с ними делать, я не знаю...
КО>>раздавленные комары, пыль и вообще все плохо 
РМ>Комаров я там не заметил, а пыль — можно просто выкидывать слишком мелкие куски.
Не знаю. Там кусок 6х6 — мы-то с тобой понимаем, что его надо выкинуть, а компу как объяснить?
КО>>О блин... Одни слабые места
РМ>Ну, это пессимистичный взгляд — люди и не такое оцифровывают...
Согласен, у страха глаза велики
РМ>Кстати не обязательно использовать именно Безье. Можно и квадратичными кривыми обойтись в данном случае, а считать и перебирать уже меньше.
Ну да, это Mika просто упомянул, что ему кривые Безье нужны — а так конечно, с квадратичными проблем гораздо меньше. Дело в том, что квадратичная кривая — это кривая Безье, у которой две направляющие точки совпадают, а следовательно, находятся на пересечении двух касательных прямых в концах кривой. Все наши рассуждения остаются, более того: как только мы отыщем касательные прямые в концах с достаточной точностью, сразу появится третья точка (в точке их пересечения) — и квадратичная кривая найдена.
Здравствуйте, Кирилл Осенков, Вы писали:
КО>>>попали в сказку и кто-то подарил нам такую цепочку пикселов (массив пикселов от 1 до n, причем у каждого пиксела кроме концов ровно два соседа (если брать 8-связность)),
РМ>>Ну составить такую цепочку было бы не проблематично, но ИМХО она и не нужна. И можно брать больше чем 8-связности.
КО>Если честно, я плохо представляю себе, а как без цепочки?
КО>Было бы классно знать более-менее конструктивный способ, использующий такой массив с утолщениями и аномалиями (а не цепочку):
Как определить направление в данной точке без цепочки я уже писал. Вторая проблема — это движение вдоль линии. Но имея направление, разве это проблема? Третья проблема — это выкидывать те точки, для которых кривая уже построена, так как при движении вдоль мы будем проходить не через все точки. Но в принципе и это не проблема, так как можно помечать все находящиеся рядом с проходимыми.
КО>Так вот. Предлагаю взять такую связность:
Ну это вопрос не принципиальный имхо, но я себе именно такую и представлял.
КО>Я подумал, твой фокус с прямой можно оптимизировать. Подбирать ее не нужно — ее можно восстановить по алгоритму Брезенхема.
Правильно, только надо для случаев с более чем единичной толщиной расширить. Т.е. рассамтривать не одну прямую, а множество возможных, потихоньку их одну за одной отбрасывая.
КО>>>Мои воздушные рассуждения о том, что поиск второго конца можно прерывать после нахождения третьего обнуления кривизны.
РМ>>ИМХО поиск можно прерывать, когда например из десяти наскоро посчитанных точек кривой две окажутся вне множетсва точек.
КО>Это эмпирика. К тому же мне кажется, ты как-то скромно берешь — с таким же успехом отлично можно и отрезками приближать.
Ну это я так, к примеру, а вообще изначально мне казалось, что надо всю кривую в масшатабе рисунка восстанавливать и чтобы она вся укладывалась в наши точки.
КО>>>Опять же, достаточно точно оценить кривизну в нашей дискретной задаче скорее всего не удастся.
КО>>>Как искать удаление направляющих точек от концов кривой — вообще неясно (ну т.е. мне не ясно )
РМ>>Я там выше писал про покрытие точек прямой, так вот их кол-во после какого-то несложного преобразования ( возможно по таблице, полученной эмпирически ) должно дать примерное значение, вокруг которого можно искать перебором или даже оставить так.
КО>Да, но перебор все-таки достаточно большой...
В том-то и штука, что перебор вокруг приблизительного значения, то есть сильно меньший, чем мог бы быть.
А вообще отказавшись от Безье, в пользу кривых второго порядка, можно избежать перебора вообще.
КО>>>изломы, самопересечения,
РМ>>В принципе при вращении кривой эти штуки опредятся как два максимума только в одной стороне ( изломы ) два максимума с обеих сторон ( пересечения ). В изломах можно и прервать кривую, а в пересечениях продолжатьь в нужном направлении.
КО>Щас, я не понял. Что ты имеешь ввиду? Здесь можешь поподробнее плз?
Если мы имеем излом, и попытаемся найти направление фокусом с кривой, то ничего не выйдет, направления будет два и односторонних, а для пересечения будет просто два направления. Оба случая можно корректно обработать.
КО>>>толщина в 2 и больше пиксела (а толщина в два пиксела, зараза, сплошь и рядом встречается на приведенной картинке),
РМ>>Не страшна. Какие проблемы она создает?
КО>Да понимаешь — вот у нас массив пар (x,y) от 1 до 10000. Больше ничего не знаем. И что с этим делать? Как ты поймешь, что кривую нужно направлять в "самую тонкую сторону"?
А фокус с прямой зачем?
КО>И глянь на рисунок — там есть жирные перекрестки из пяти и больше таких "кишок"... Че с ними делать, я не знаю...
Не начинать с перекрестков. А на ходу, когда уже известно предыдущее направление проще выбрать правильное.
КО>>>раздавленные комары, пыль и вообще все плохо
РМ>>Комаров я там не заметил, а пыль — можно просто выкидывать слишком мелкие куски.
КО>Не знаю. Там кусок 6х6 — мы-то с тобой понимаем, что его надо выкинуть, а компу как объяснить?
Выкидывать те, где не прошел фокус с кривой...
РМ>>Кстати не обязательно использовать именно Безье. Можно и квадратичными кривыми обойтись в данном случае, а считать и перебирать уже меньше.
КО>Ну да, это Mika просто упомянул, что ему кривые Безье нужны — а так конечно, с квадратичными проблем гораздо меньше. Дело в том, что квадратичная кривая — это кривая Безье, у которой две направляющие точки совпадают, а следовательно, находятся на пересечении двух касательных прямых в концах кривой. Все наши рассуждения остаются, более того: как только мы отыщем касательные прямые в концах с достаточной точностью, сразу появится третья точка (в точке их пересечения) — и квадратичная кривая найдена.
Во-во, и я о том же.
... << RSDN@Home 1.1 beta 2 >>
РМ>Как определить направление в данной точке без цепочки я уже писал. Вторая проблема — это движение вдоль линии. Но имея направление, разве это проблема? Третья проблема — это выкидывать те точки, для которых кривая уже построена, так как при движении вдоль мы будем проходить не через все точки. Но в принципе и это не проблема, так как можно помечать все находящиеся рядом с проходимыми.
Ну, от этих рассуждений до алгоритма еще довольно далеко (еще много неясностей), но путь ты указал — и я с тобой согласен. Теперь уже наверное можно пробовать кодить
P.S. Здесь очень важны дизайн и структуры данных — в процессе написания алгоритм будет сильно эволюционировать.
