Fitting lines through large point clouds
Based on the feedback and trying to find more effective approach I developed the following algorithm using a dedicated distance measure.

Following steps are performed:

1) Define a distance metric returning:

zero - if the points do not belong to a line

Euclidian distance of the points - if the points constitute a line according to the defined parameters, i.e.


their distance is higher or equal than the min_line_length and
their distance is lower or equal than the max_line_length and
the line consists of at least min_line_points points with a distance lower that line_width/2 from the line                        


2) Calculate distance matrix using this distance measure (use sample of the data for large data sets; adjust the line parameters accordingly)

3) Find the points A and B with maximum distance - break to step 5) if the distance is zero

Note that if the distance is higher than zero the points A and B are building a line based on our definition

4) Get all points belonging to the line AB and remove them from the distance matrix. Repeat the step 3) to find another line

5) Check the coverage of the point with the selected lines, if substantial number of points remains uncovered, repeat the whole algorithm with adjusted line parameters.

6) In case that data sample was used - reassign all points to the lines and recalculate the boundary points.

Following parameters are used:

line width - line_width/2 is the allowed distance of the point from the ideal line =   r line_width

minimum line length  - points with shorter distance are not considered to belong to the same line =  r min_line_length

maximum line length  - points with longer distance are not considered to belong to the same line =  r max_line_length

minimum points on a line - lines with less points are ignored = r min_line_points

With your data (after some fiddling with parameters) I got a good result covering all 30 lines.



More details can be found in the knitr script