Визначення центру кола або еліпса по його точкам

А нічого, що ява як би для обчислень не призначена? Ви знущаєтесь, або просто Java-ненависник? Де ви взагалі знайшли важкі обчислення? У людини до 25 точок, а МНК - метод зі складністю не більше куба! Це завдання я навіть на пакетних файлах вирішити зможу, не те що на Java.

Універсальний спосіб - метод найменших квадратів. Тобто змусити комп'ютер підібрати такі параметри еліпса щоб різниця між еліпсом і нашими точками була мінімальною. Краще критерій складно придумати - хоча іноді виходить не те, що очікуєш, але це скоріше говорить про те, що вихідні дані неправильні.

Алгоритм такий:
1. Вибираємо підходяще рівняння еліпса.
2. Пішeм цільову функцію (сума квадратів рівняння для кожної точки вихідних даних). За необхідності додаємо до цільової функції додаткові умови, типу невирождаемості еліпса в гіперболу. Типу, якщо умова порушується, спрямовуємо її в нескінченність.
3. Вибираємо мінімізатор (градієнтний спуск, нормальне рівняння т. Д.)
4. Якщо результати не влаштовують по швидкості або якості, повертаємося до п. 3 або до п. 1.

З приводу третього пункту. ВУкаіни чомусь вважається, що МНК - це коли рішення йде за допомогою нормального рівняння (складаємо матриці і вирішуємо (AtA) ^ - 1 * At * x = b без ітерацій в один присід). Це не так. Мінімізувати можна яким завгодно способом. Хоч генетичними алгоритмами. Нормальне рівняння добре тоді, коли член (AtA) ^ - 1 виходить маленької квадратної матрицею. Тобто коли параметрів мало, а точок дуже багато. Систему рівнянь для еліпса взагалі до виду A * x-b = 0 привести служно. Шукати відповідні статті як це робиться мені влом, тому я піду влоб, як мінімізатора взявши стандартний матлабовскій.

ВУкаіни чомусь вважається, що МНК - це коли рішення йде за допомогою нормального рівняння
Між іншим, виправдано вважається. Якщо вихідне рівняння - виду A * x-b = 0. то нормальне рівняння дає оптимальний результат.

Систему рівнянь для еліпса взагалі до виду A * x-b = 0 привести складно Я його до цього виду привів.

До речі, ваша програма поверне вам випадковий результат, оскільки ви взяли жахливу цільову функцію. Вона звертається в нуль при A = B = C = F = 0 незалежно від x0 і y0. Я-то написав таке рівняння, оскільки у мене перші три змінних були вже знайденими (константами). А вам треба було, як і мені в першому рівнянні, покласти F = 1.

PS
еліпс по восьми (?) точкам П'яти точок досить - якщо, звичайно ж, похибки дозволять.

колега
Боронь Боже. Найбільше не люблю замасковане хамство.
Між іншим, виправдано вважається. Якщо вихідне рівняння - виду A * x-b = 0, то нормальне рівняння дає оптимальний результат.
Якщо почати в відповідь займатися буквоїдством, "(t = MT M) -1 MT r" оптимальний результат не дає. Потрібно використовувати псевдообернена матриця, інакше можливий чисельний марення.
Друге. Все, що здатне вирішити з тим же якістю (тобто без введення регуляризації, інший метрики і т. Д.), Дасть цей же результат. Немає локальних мінімумів, щоб застрягти. Тобто про оптимальне рішення питання не стоїть - воно в разі такої простої лінійної задачі, якщо є, то є.
Питання стоїть в швидкості. При великих n спуск з прописаним градієнтом вигідніше, тому що o (n ^ 3), а Солвер з відомим градієнтом працює досить швидко. Я про це писав.
Між іншим, виправдано вважається.
Вважається абсолютно невиправдано - це спадщина епохи арифмометрів, коли змусити відділ дівчаток перемножать матриці було простіше, ніж закодувати і запустити спуск на ЕОМ. Як завжди, вУкаіни освіту з тієї епохи, тому народ крім нормальних рівнянь нічого не знає, і вважає це синонімом МНК.
З нормального рівняння можна вивести цікаві речі, але саме він для таких прикладних задач рідко потрібно, важливіше зрозуміти загальний принцип, щоб не лякатися, коли доведеться підганяти вже не еліпс, який-небудь еліпсоїд до 3д точкам.
Я його до цього виду привів.
Квадратичну форму? Ок. Раджу написати W. Gander - G. H. Golub - R. Strebel про своє відкриття, але зауважу, що в пості цього не було. В A * x = b ікси зліва, і ігреки (b) справа. Коли x і y зліва, а справа константа - це не те.
До речі, ваша програма поверне вам випадковий результат,
Лол. Хоча б треба було перевірити, чи не? Насправді ваш результат буде гірше (у мене відповідний еліпс, а в такому випадку - гіпербола). Тому то я танцюю від хорошого початкового умови - окружності. Я почала спускаюся по координатам x0, y0, F, потім - x0, y0, A, B, C, F. Ви змінюєте вид рівняння, причому класним способом - пропонуєте оголосити F константою, типу якщо функція має вироджений мінімум f (A = 0 , B = 0, C = 0, F = 0) ^ 2 = 0 це погано, а f (A = 0, B = 0, C = 0) ^ 2 = 1 - це нормально, хоча випадок абсолютно такий же.
Насправді таке виродження не є проблемою. Додаючи епсилон до A = 0, B = 0, C = 0 буде стрибок, в цей мінімум дуже складно потрапити з хорошим початковим приблежения (швидше за все - з будь-яким, крім тривіального «все нулі»).
Реальних проблем дві - виродження в гіперболу, про що я писав, і загальна нестійкість.
Солвер і рівняння потрібно підбирати під вихідні дані. Особливо - обмеження, наприклад, на розмір еліпса, умова того, щоб це був еліпс, і так далі. У більшості випадків їх можна написати. Якщо еліпс є майже окружністю (наприклад, Земля з космосу), мій спосіб з двома наближеннями хороший. Я можу зробити його краще, але не в форматі відповіді на питання. А ще дивуються, чому на Хабре неможливо як на stackoverflow.

Ах да, вибачте, ви звичайно ж мені не колега - колега не написав би таких міркувань.

Людина запитує, як це простіше зробити - а ви йому пропонуєте градієнтний спуск замість зворотної матриці. До слова, серед моїх знайомих програмістів матрицю кожен звернути зможе, а на згадку градієнта більшість зроблять круглі очі і запитають, що це таке. Гаразд би ще пропонували як альтернативу - раптом дійсно буде простіше - але немає, альтернатив ви не визнаєте.