Calculate straight line from scattered points

I have some scattered 3D points (2d solution is sufficient). I want find different straight lines passing through (at least three points makes开发者_运维知识库 line) which are laying nearby (say for example 10 units). A single point could be part of different lines.

To determine whether 3 points (a,b,c) are in a line, use cross-products (2D or 3D):

V = (Vx, Vy, Vz)
Vab = b - a
Vac = c - a 
CrossProd (V,W) = (VyWz - VzWy, VzWx - WzVx, VxWy - WxVy)

If CrossProd(Vab, Vac) is zero, then the points (a, b, c) are colinear. Actually the cross product is proportional to the area of the triangle (a, b ,c), so you can set a small non-zero tolerance if needed.

Re. tolerance.

The distance from b to the line Vac is given by:

d = length(CrossProd(Vab, Vac))/ length(Vac)

You can probably compare this with an absolute tolerance given your problem description. Alternatively you might use:

sin(theta) = length(CrossProd(Vab, Vac))/ length(Vac)/ length(Vab)

Then theta is the angle between the two vectors and can be compared with a fixed tolerance.