Найти линии в облаке точек

Question

У меня есть массив очков. Я ЗНАЮ, что эти точки представляют много строк на моей странице.

Как я могу их найти? Нужно ли найти расстояние между облаками точек?

Спасибо Jonathan

Answer 1

Может быть, Hough Transform - это то, что вы ищете? Или линейная регрессия ?

[EDIT] Как оказалось, проблема состоит в том, чтобы идентифицировать линии внутри списка 2d координат, я бы поступил следующим образом.

Линейная регрессия может использоваться только для наилучшей линейной корректировки для набора точек, а не для обнаружения множества линий. Возможно, используйте hough, чтобы получить примерно линии, проверьте, совпадают ли много точек на этих линиях Посмотрите на точки, оставленные в стороне. Они должны принадлежать линии?

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

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

По крайней мере, проблема интересна !

Answer 2

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

1. Перейдите через все двухточечные линии и преобразуйте их в структуру, которая содержит:

   а) у-перехват

   б) уклон

   в) нижняя граница х

   г) верхняя граница x

2. Сортировка по y-перехвату и наклону.

Теперь вы знаете, что 2 линии могут перекрываться, только если они имеют одинаковый у-образный перехват и одинаковый наклон.

3. Для каждого набора линий с одинаковыми y-пересечением и наклоном проверьте, перекрываются ли x-границы. Если они есть, то у вас нет отдельных линий, у вас есть 1 строка с более чем 2 точками.

4. Обрабатывать вертикальные линии как особый случай.