Распознавание типа графа по заданному набору точек

Question

Я пытаюсь разработать программу, которая рисует графики с заданным набором точек (x, y), и она также должна распознавать кривую (прямую линию, гиперболу, параболу) только с помощью точек.Есть ли алгоритм для этого?

Answer 1

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

Если пять точек коллинеарны, у вас есть прямая линия. (Или вырожденная коника? Но если вы ожидаете прямые линии, это должно указывать на прямую линию.)

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

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

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

Чтобы найти уравнение для этой коники (Ax ^ 2 + Bxy + Cy ^ 2 + Dx + Ey + F = 0), взгляните на эту страницу , в частности формулу в DETAILS раздел. Введите свои пять значений x и y, вычислите определитель матрицы в терминах x и y, и это даст вам формулу вашей коники. Затем посмотрите здесь , чтобы выяснить, какая у вас коника, основываясь на значениях A, B и C.

Если у вас более 5 точек, выберите пять точек (желательно, чтобы три не были коллинеарными), найдите конику и убедитесь, что остальные точки лежат на конике.

Answer 2

Вы можете сделать это, наблюдая за экстремальной функцией, но, возможно, это не оптимальное решение для этой проблемы (я имею в виду такую ​​проблему в функции параболы y = sqrt (x * x-1) ). Для прямой линии вы можете вычислить y = ax + b по двум случайным точкам и проверить, какие другие точки соответствуют этому условию, если да. Это прямая линия, если нет, вы можете проверить 2 других исключения или ничего из этого. Может быть, кто-нибудь еще найдет решение для следующих 2 случаев?