forum.boolean.name - Сравнение кривых

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Сравнение кривых (http://forum.boolean.name/showthread.php?t=11754)

Horror

17.01.2010 22:58

Сравнение кривых

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

Randomize

17.01.2010 23:03

Ответ: Сравнение кривых

Предлагаю простой способ:
Переносишь 1ую точку второй кривой на 1ую точку первой.
Пробегаешься циклом по остальным точкам и cравниваешь дистанцию от данной точки первой кривой до данной точки второй кривой. И если она больше допустимой погрешности то они не равны.

Тоесть допустим:
2 кривые
2 массива.
В одной кривой 5 звеньев.

Перемещение второй к первой:

PHP код:


		
			
x_d=Curve1[i].x-Curve2[i].x; // смещение



for(i=0;i<5;i++)

{

 Curve2[i].x-=x_d; // перемещаем

}

Сравнение:

PHP код:


		
			
for(i=0;i<5;i++)

{

 if (Distance(Curve1[i].x,Curve1[i].y,Curve2[i].x,Curve2[i].y)>max_dist)

 {

    // Они не равны

   Exit;

 }

}

Дистанцию находить так:

PHP код:


		
			
Sqr(((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)))

Если нужен код в B3D, то могу и в нём написать.

impersonalis

17.01.2010 23:22

Ответ: Сравнение кривых

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

Horror

18.01.2010 01:01

Ответ: Сравнение кривых

>Предлагаю простой способ:
>Переносишь 1ую точку второй кривой на 1ую точку первой.
>Пробегаешься циклом по остальным точкам и cравниваешь дистанцию
>от данной точки первой кривой до данной точки второй кривой. И если
>она больше допустимой погрешности то они не равны.
Поэтому я и написал что массивы имеют разную длину)
я думал какнить повставлять в массив с меньшим числом новые точки,
но это както по хитрому... надо
(оО кое-что уже придумал)

>а если прямые имеют разный масштаб? Подобие подразумевает,
>что символ набранный разным кеглем должен счиаться одинаковым
масштаб один! и положение одной кривой над другой - близко наложенно)

ABTOMAT

18.01.2010 01:57

Ответ: Сравнение кривых

масштаб выровнять несложно! (габаритные прямоугольники подогнать да и все дела)
а сравнивать думаю так
построить жирные линии между точками
чем жирнее тем больше погрешность
то есть построить обе фигуры жирными линиями
и наложить
если совпало N % то значит можно считать эквивалентными

а вот если поворот имеет место быть, то тогда хз
сходу на ум ничего не приходит :(
кстати как ты сей массивець точек получил ? :( Из растровой картинки али как?

Horror

18.01.2010 20:24

Ответ: Сравнение кривых

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

ZanoZa

20.01.2010 22:05

Ответ: Сравнение кривых

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

IGR	20.01.2010 22:15

Ответ: Сравнение кривых

я вот погуглил немного и узнал что с подобными задачами на УРА справляются нейросети !! к тому же достаточно простой структуры !! :)

Часовой пояс GMT +4, время: 23:44.