|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 09 Nov 2001 10:56:43
To : Serge Kanilo
Subject : Re: Массив точек и пpямая на плоскости
--------------------------------------------------------------------------------
Fri Nov 09 2001 06:00, Serge Kanilo wrote to Evgenij Masherov:
>> SS> Есть массив точек на плоскости. Как yзнать пpинадлежат ли они одной
>> SS> пpямой? Пpичем алгоpитм должен быть не совсем стpогий, я имею в видy
SK> что
>> SS> допyстимо напpимеp максимальное отклонение точек напpимеp на тpи
SK> пиксела
>> SS> от этой пpямой и напpимеp допyстимо 2% точек не попадающих в этy
SK> пpямyю
>> SS> вообще - в этом слyчае считается что точки пpинадлежат одной пpямой.
>> SS> Естественно желательно также попyтно полyчить ypавнение пpямой - я
SK> имею в
>> 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 к единице (по абс. величине) - тем точнее точки лежат на
SK> линии.
SK> Для практики вполне подойдет, но здесь есть
SK> несимметричность между использованием x и у.
SK> И наверное лучше выбрать приоритетное направление
SK> и считать либо y=ax+b, либо x=сy+d.
SK> Или построить матрицу
SK> SUM((x-x_)*(x-x_)) SUM((y-y_)*(x-x_))
SK> SUM((x-x_)*(y-y_)) SUM((y-y_)*(y-y_))
SK> Ее собственые вектора дадут главные направления,
SK> минимальное собственное значение и будет отражать
SK> отдаленность точек от прямой (хотя лучше провести
SK> простой анализ отклонений по точкам)
SK> а соответствующий вектор v_min - содержать
SK> коэффициенты для этой прямой, заданной в виде
SK> v_min_1*(x-x_) + v_min_2*(y-y_) =0.
SK> ИМХО и исходный вариант, и предложенный мной не совсем
SK> решают данную задачу, как она поставлена (но может постановка
SK> была не совсем осознана :), поскольку в принципе минимизируют
SK> среднее расстояние до прямой, а не максимальное отклонение.
Hу, это очень древная проблема - какая из двух регрессионных кривых истинная
(задача - дама, желающая узнать, стоит ли ей худеть, строит регрессию роста
кинозвезд на вес, подставляет свои значения, и обнаруживает, что вес ея
избыточен, затем веса на рост - и обнаруживает, что ей стоит поправиться:).
Полагаю, что в поставленных условиях и регрессия у на х, и х на у ответят на
вопрос - лежат ли точки на одной прямой (ввиду того, что в этом случае к-т
корреляции будет близок к единице, и различия между моделями будут малы), в
общем же случае придется вводит дополнительную информацию (скажем, о
дисперсиях ошибок у и х или о их, дисперсий, соотношении) и собственные
значения - пригодятся...
С уважением
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
