|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 09 Nov 2001 07:00:35
To : Evgenij Masherov
Subject : Re: Массив точек и пpямая на плоскости
--------------------------------------------------------------------------------
"Evgenij Masherov" <EMasherow@nsi.ru> wrote in message
news:4204361738@p2.f175.n5020.z2.ftn...
> SS> Есть массив точек на плоскости. Как yзнать пpинадлежат ли они одной
> SS> пpямой? Пpичем алгоpитм должен быть не совсем стpогий, я имею в видy
что
> SS> допyстимо напpимеp максимальное отклонение точек напpимеp на тpи
пиксела
> SS> от этой пpямой и напpимеp допyстимо 2% точек не попадающих в этy
пpямyю
> SS> вообще - в этом слyчае считается что точки пpинадлежат одной пpямой.
> SS> Естественно желательно также попyтно полyчить ypавнение пpямой - я
имею в
> SS> видy коэфициенты а и b в ypавнении пpямой. Речь идет о pастpовой
> SS> каpтинке...
>
> Я бы вычислил регрессию У на Х. И в качестве меры принадлежности к линии
> принял бы коэффициент корреляции
> y=ax+b
> y_=SUM(y)/N
> x_=SUM(x)/N
> a'=SUM((y-y_)*(x-x_))/SUM((x-x_)^2)
> b'=y_-a'x_
> R=SUM((y-y_)*(x-x_))/sqrt(SUM((x-x_)^2)*SUM((y-y_)^2))
> Чем ближе R к единице (по абс. величине) - тем точнее точки лежат на
линии.
Для практики вполне подойдет, но здесь есть
несимметричность между использованием x и у.
И наверное лучше выбрать приоритетное направление
и считать либо y=ax+b, либо x=сy+d.
Или построить матрицу
SUM((x-x_)*(x-x_)) SUM((y-y_)*(x-x_))
SUM((x-x_)*(y-y_)) SUM((y-y_)*(y-y_))
Ее собственые вектора дадут главные направления,
минимальное собственное значение и будет отражать
отдаленность точек от прямой (хотя лучше провести
простой анализ отклонений по точкам)
а соответствующий вектор v_min - содержать
коэффициенты для этой прямой, заданной в виде
v_min_1*(x-x_) + v_min_2*(y-y_) =0.
ИМХО и исходный вариант, и предложенный мной не совсем
решают данную задачу, как она поставлена (но может постановка
была не совсем осознана :), поскольку в принципе минимизируют
среднее расстояние до прямой, а не максимальное отклонение.
Best regards,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
