Лежат ли точки на эллипсе? (точки заданы неточно)

[Humanoid]

Как я понимаю, эллипс однозначно задаётся пятью точками.

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

Хмм... Теорема Паскаля - там шесть точек и не только эллипсы. Система уравнений - как в неё погрешность всунуть? Я озадачен...

[mihailm]

А с точными данными знаете как эллипс (или что получится) находить?

[svv]

Humanoid
Никак.
После небольшого сдвига из-за погрешностей Ваши точки будут лежать на некотором другом эллипсе точно. Теперь бы применить минус этот сдвиг, но о нем ничего не известно, потому что применив любой малый сдвиг, Вы опять получите некоторый эллипс, который потенциально может быть исходным.

[Humanoid]

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

-- менее минуты назад --

svv в сообщении #825677 писал(а):

Humanoid
Никак. После небольшого сдвига из-за погрешностей Ваши точки будут лежать на некотором другом эллипсе точно.

Не совсем понял мысль... Моя задача в том, чтобы определить, лежат ли точки приблизительно на каком угодно эллипсе. О первоначальном эллипсе я ничего не знаю.

[svv]

Так точки точно лежат на некотором новом эллипсе. Который, очевидно, и минимизирует сумму квадратов отклонений.

-- Ср фев 12, 2014 19:36:41 --

Humanoid писал(а):

Моя задача в том, чтобы определить, лежат ли точки приблизительно на каком угодно эллипсе.

Ответ сразу: да, лежат. Потому что первоначальные точки лежали, а потом их не очень сильно подвинули.

Чтобы точки не ложились на эллипс (а, скажем, на параболу или гиперболу), их надо в некотором смысле сильно сдвинуть.

-- Ср фев 12, 2014 19:43:55 --

Я правильно Вас понял, что Вам надо уметь отличать случай эллипса от параболы, гиперболы и т.д.? Потому что «на чем-то» пять точек всегда лежат.

[Humanoid]

Цитата:

Чтобы точки не ложились на эллипс (а, скажем, на параболу или гиперболу), их надо в некотором смысле сильно сдвинуть.

О! У меня весь полилайн необязательно из эллипсов состоит, мне как раз эллиптические участки и нужно найти. В силу чего и вопрос - есть ли способ определить, лежат ли пять точек приблизительно на эллипсе, вычислительно менее затратным способом, чем я выше написал? Вот к примеру теорема Паскаля для шести точек (я могу и больше точек взять) даёт простой геометрический ответ, но увы, она среагирует и на параболы с гиперболами... Может можно как-то первичную проверку провести по Паскалю, а потом определить, что именно коническое сечение получилось?

-- менее минуты назад --

Цитата:

Вам надо уметь отличать случай эллипса от параболы, гиперболы и т.д.?

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

[svv]

${\begin{vmatrix}x^{2}&xy&y^{2}&x&y&1\\x_{1}^{2}&x_{1}y_{1}&y_{1}^{2}&x_{1}&y_{1}&1\\x_{2}^{2}&x_{2}y_{2}&y_{2}^{2}&x_{2}&y_{2}&1\\x_{3}^{2}&x_{3}y_{3}&y_{3}^{2}&x_{3}&y_{3}&1\\x_{4}^{2}&x_{4}y_{4}&y_{4}^{2}&x_{4}&y_{4}&1\\x_{5}^{2}&x_{5}y_{5}&y_{5}^{2}&x_{5}&y_{5}&1\end{vmatrix}}=0$
Это уравнение кривой второго порядка, проходящей через заданные пять точек.
Подставляем в определитель координаты Ваших пяти точек. Затем, если разложить его по элементам верхней строки, получим уравнение кривой второго порядка:
$a_{11}x^{2}+2a_{12}xy+a_{22}y^{2}+2a_{13}x+2a_{23}y+a_{33}=0$
Теперь стандартными способами определяем тип кривой. Для этого нужны только коэффициенты $a_{11}, a_{12}, a_{22}$.

[Humanoid]

То есть, механизм строится на том, что "пять точек всегда лежат на какой-то кривой второго порядка", и осталось только определить, эллипс ли это. Кажется то что надо! :) Спасибо! :)

[svv]

Это уравнение, как везде предупреждают, при подстановке точек лишь в том случае не даст уравнение конкретной кривой, если из пяти точек какие-то четыре лежат на одной прямой. Тогда при раскрытии определителя получится тождество $0=0$, которое ничего не даёт.

См. здесь
http://ru.wikipedia.org/wiki/Кривая_второго_порядка
пункт «Кривая, заданная своими пятью точками»

[Алексей К.]

Humanoid в сообщении #825667 писал(а):

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

Я бы писал(а):

Дано: Три точки полилинии на плоскости, которая, возможно, ранее являлась дугой окружности (результат вычислений другого алгоритма). Координаты точек имеют небольшую погрешность (несколько больше, чем у double).
Задача: Определить, лежат ли эти точки на одной окружности (надо учитывать погрешность)

[Humanoid]

Ну, этот случай будет выкинут ещё при предварительном анализе (точки возле одной прямой, или по разные стороны от прямой), который заодно исключит вариант того, что определитель будет колобродить около нуля (из-за погрешностей), и ускорит обработку.

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

Дело в шляпе, буду кодить. :)

На самом деле задача состояла в логических операциях над полигонами, исходные геометрии которых могут содержать не только прямые сегменты. Решать оную приходится полилайнами, но вот разрезав дугу, желательно и на выходе получить дугу, а не полилайн.

P.S.
Интересно, существует ли какой-то способ восстановить из полилайна сегменты кубических кривых Безье? Любой вырезанный из кривой Безье кусок тоже есть кривая Безье, вопрос, как её определить среди остальных точек и выполнить обратную задачу, то есть получить кривую из точек, а не точки из кривой?

-- менее минуты назад --

Цитата:

Определить, лежат ли эти точки на одной окружности

Хмм... Три то точки всегда лежат... Имеет ли значение последовательность точек для кривой второго порядка? У меня они идут либо по, либо против часовой стрелки, а не вперемешку.

[Алексей К.]

Humanoid в сообщении #825750 писал(а):

Имеет ли значение последовательность точек для кривой второго порядка?

Не имеет, если не заморачиваться об ориентации. И вряд ли возможно об определении ориентации сразу позаботиться. Можно только проверить по уже найденной неявной кривой.

В отличие от окружности в случае трёх точек. Там угол поворота от вектора $P_1P_2$ к вектору $P_2P_3$, положительный или отрицательный, немедленно определяет знак кривизны и ориентацию окружности (хотя можно искать радиус, по-другому, игнорируя знаки, ориентируясь на стандартное неявное уравнение). Если не ошибаюсь, $k=\dfrac{2\sin\rho}{|P_1P_3|}$, гдe $\rho$ --- вышеупомянутый угол. Переиндексируете точки --- получите (возможно) другой знак кривизны.

Humanoid в сообщении #825750 писал(а):

Если быть совсем честным, то механизм стоит на том, что при малом смещении точек кривая не поменяет тип, и, следовательно, если была эллипсом ранее, эллипсом и останется.

Если быть не просто честным, а до конца честным, то надо понимать, что это не так. По-честному, можно лишь надеяться, что смены типа не случится. Ну, в параболу совсем маловероятно, а в гиперболу... Why not? Не исключено, что из, например, инвариантов этой кривой можно оценить степень надежды-уверенности непосредственно в сантиметрах (типа "в пределах 1.72 мм гуляйте, точки, как хотите"). Но это для математических педантов, сейчас не модно.

-- 13 фев 2014, 01:46:35 --

Цитата:

Если быть совсем честным, то механизм стоит на том, что при малом смещении точек кривая не поменяет тип, и, следовательно, если была окружностью ранее, в прямую не превратится.

[Алексей К.]

Вариант 1, скучный:
эллипсность конфигурации из 5 точек легко определяется (или очевидна) визуально, и тогда ни о чём вышеобсуждаемом заморачиваться не стоит. Всё будет хорошо (или мне ночью так кажется).

Вариант 2, поинтереснее:
по внешнему виду не определить эллипс ли это, или другая коника: уж больно маленькая дуга рассматривается. Тогда вышеобсуждаемое сильно напоминает плохо поставленную задачу, или плохой способ решения некой другой, нормально поставленной задачи (в данном контексте неизвестной).
Напрашивается пример из области допускового контроля: на чертеже --- номинальная кривая, описанная как малая дуга именно эллипса, конкретного, заданного. На реальной изготовленной детали решили измерить координаты пяти точек (ПЯТИ, чтоб с МНК не возиться, чтоб попроще эллипс сосчитать), и проверить допуски. Ой, если это всё так --- как же это неправильно и неграмотно, даже с определением параметров эллипса по МНК, и даже по двадцати двум точкам!

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

На всякий случай уточню: я не говорил, что задача плохо поставлена. Я лишь сказал, что это "сильно напоминает плохо поставленную задачу".

[vlad_light]

Ivan Markovsky, Alexander Kukush, and Sabine Van Huffel: "Consistent least squares fitting of ellipsoids"
Это оно или нет?

[Алексей К.]

(vlad_light)

И про эллипсы есть куча статей. Так, ссылка в первом сообщении темы «Аппроксимация эллипса» до сих пор не протухла, а в ней, помнится, куча других была. Но нужны ли автору least squares --- мы не знаем. Это только моя слабая гипотеза

,