Рассчитать прямую линию от рассеянных точек

Question

У меня есть несколько рассеянных трехмерных точек (достаточно двухмерного решения).Я хочу найти различные прямые линии, проходящие через (по крайней мере, три точки составляют линию), которые лежат рядом (скажем, например, 10 единиц).Одна точка может быть частью разных линий.

Answer 1

Чтобы определить, находятся ли 3 точки (a, b, c) на линии, используйте перекрестные продукты (2D или 3D):

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

Если CrossProd(Vab, Vac) равно нулю, то точки (a, b, c) являются коллинеарными. На самом деле, перекрестное произведение пропорционально площади треугольника (a, b ,c), поэтому при необходимости можно установить небольшой ненулевой допуск.

Re. допуск.

Расстояние от b до линии Vac определяется как:

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

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

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

Тогда theta - это угол между двумя векторами, который можно сравнить с фиксированным допуском.