Как кластеризовать точки по принадлежности к разным (неизвестным) прямым?

Приблизительно так:
1. Берем группу близко лежащих точек.
2. Строим по группе точек прямую.
3. Выкидываем из группы точку (точки) которая слишком сильно выбивается из корреляции.
4. Добавляем к группе ближайшую не проверенную точку.
5. Повторяем с п.2 до тех пор пока точки не закончатся.
Так определяется направление одной из линий.
6. Все точки которые соответствуют найденной линии исключаются из общей массы точек и процесс повторяется с п.1
Таким образом будут найдены все линии.
7. Из массива линий нужно исключить линии состоящие из малого числа точек. Скорее всего это линии из точек выброса. А точки входящие в эти линии нужно исключить из общего массива точек.
8. После того, как все линии найдены, нужно найти входящие в них точки из общего массива точек (с учёт предыдущего пункта), т.к. точки могут входить в несколько линий, а из-за п.6 последняя линия не досчитается многих своих точек.
Замечания по п.3:
* Если в результате добавления одной точки выпадают 3 и более точек, то выкидывать нужно добавленную точку, а не те которые перестали подходить для линии.
* Если после добавления новой точки, ни кто из корреляции не выпадает, то и выкидывать ни кого не нужно.

Если времени не очень жалко, можно попробовать так:
Перебираем углы от 0 до 180 с шагом, например, 1 градус.
Проектируем точки на прямую, идущую под этим углом к горизонтали.
Ищем на проекции достаточно короткий отрезок, в который попало достаточно много точек.
Ищем методом наименьших квадратов прямую, наилучшим образом приближающую точки, попавшие в этот отрезок.

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

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