Учитывая двумерный граф с точками, найдите линию, которая проходит через наибольшее количество точек

Question

Эта проблема возникла из-за того, что вы взломали задачу 7, посвященную интервью по кодированию, для меня. Как для математика, это кажется простой проблемой наименьших квадратов, когда мы находим линию наилучшего соответствия.Хотя в решении они используют другой подход.

Мой вопрос заключается в следующем: является ли разработка метода наименьших квадратов достаточным решением или я не понимаю проблему под рукой?

Answer 1

Наименьших квадратов не является подходящим решением, его не волнует количество выровненных точек.Подгонка наименьших квадратов может вообще не содержать никакой точки.

Решение в ссылке по julian имеет поведение O (N²), предполагая, что хэш-карта имеет поведение O (N) для подсчета дубликатов.(С сортировкой O (N²Log N) может быть гарантировано.)

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

Answer 2

Вы можете использовать двойную плоскость.
Для любой точки p с координатами p_x, p_y вы можете преобразовать ее в двойную линию p * = (y = p_x x-p_y).
Для любой прямой l: y = mx + b вы можете преобразовать ее в двойственную точку l = (m, -b)

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

Подробнее см. Главу 8.2 Вычислительной геометрии М. де Берга и др.

Answer 3

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

То, как я вижу проблему, может быть решено более простым способом

Найдите линию

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

Вероятно, это будет O (n ^ 3), так как вы создаете линию и проверяете для каждой точки,который находится на линии или нет ..

Преобразование Хафа

Эффективным способом, вероятно, является использование Преобразование Хафа .Это выполняется за линейное время.

Каждая 2-мерная точка отображается на кривую в пространстве грубых параметров ... мы дискретизируем пространство грубых параметров на MxN, если у нас есть K точек, затем перечисление всех точек занимает время O (KN)мы находим максимум в пространстве параметров (это можно сделать в кратчайшие сроки при перечислении), поэтому в целом он может быть линейным, хотя я не совсем уверен в этом.

RANSAC

Я также нашел один хороший ресурс о RANSAC Алгоритме, который похож на выполнение аналогичной работы.Может быть, это может помочь /