Алгоритм наложения

← →
zorik © (2008-09-23 16:16) [0]

Есть 2 группы точек. Вторая относительно первой линейно преобразована, т.е. координаты умножены на коеффициент плюс сдвиг. Задача найти уравнения преобразования. Особенности:
- i-я точка первой группы не является i-й точкой второй группы
- точки после преобразования попадают не точно, т.е. надо найти уравнение при котором отклонения будут минимальными
- количество точек в группах не равное

Предметная область - оцифровка карт. У нас есть список обьектов с реальными координатами, мы оцифровываем их на карте (частично, все или даже те, для которых нет реальних координат), и получаем уравнения перевода.

Основная загвоздка в определении отношений между точками -- какая точка 1-й группы соответствует какой точке второй группы. Дальше задача решена. Минимальное отклонение и коефициенты расчитываються методом наименших квадратов

← →
KilkennyCat © (2008-09-23 17:28) [1]

Ну и в чем проблема? в бинарном поиске коэффициента?

← →
zorik © (2008-09-23 17:33) [2]

не перебором же их искать

← →
KilkennyCat © (2008-09-23 17:35) [3]

ну а как же еще?
Берем макс и мин пределы и делим на два, пока не попадаем.

← →
zorik © (2008-09-23 17:51) [4]

А B
0: [1, 5] [70, 60]
1: [5, 4] [50, 30]
2: [7, 9] [90, 110]
3: [3, 1] [30, 80]

B = 20 + 10*A (но этого мы не знаем)

Как найти что A[0]->B[3], A[1]->B[0], A[2]->B[2], A[3]->B[1]?

← →
Сергей М. © (2008-09-23 18:46) [5]

> zorik © (23.09.08 17:51) [4]

А чевой-то ты нарушаешь условия задачи ?

> количество точек в группах не равное

А у тебя равное ...

А вот так будет соответствовать:

0: [1, 5] [70, 60]
1: [5, 4] [50, 30]
2: [7, 9] [90, 110]
3: [3, 1] [30, 80]
4: [30, 80]

B[4] сводит на нет всю благую затею ...

← →
anonims (2008-09-24 13:29) [6]

ввести понятие направление для пары точек (x1,y1) (x2,y2) napr:=(x1-x2)/(y1-y2)

данное понятие для совпадающих пар точек на всех картах постоянно (с учетом ошибок измерения и вычисления)
и ишем не точки а пары точек удовлетворяюшие данному условию (напрвAB =направXY)

> zorik © (23.09.08 16:16)

> группы. Дальше задача решена. Минимальное отклонение и коефициенты
> расчитываються методом наименших квадратов

Если в группах разное кол-во точек, то какой наф МНК?

Тут остается только инвариантами оперировать.
Найти центры тяжести групп, описать вокруг них окружности,
заключающие, скажем, 95% точек и по их радиусам определить A.
Знак А определять по плотности точек в четырех квадрантах.

--
Regards, LVT.

Алгоритм наложения Найти похожие ветки