Объединить 2d линейные сегменты

Question

Я ищу способ объединить двухмерные отрезки. Сегмент линии состоит из двух векторных точек: начала отрезка и конечной точки отрезка.

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

Я думаю, что следующие 3 примера охватывают вид отрезков, которые я хочу объединить:

Спасибо

Answer 1

Это проблема вычислительной геометрии, в соответствующих учебниках могут быть некоторые решения, но имейте в виду, что эти проблемы обычно очень трудно решить, и конечная точность - это реальная проблема. Что касается этой проблемы (в 2D), то термин, который вы, вероятно, ищете, это то, что линии около коллинеарны . Как правило, чтобы определить, являются ли линии коллинеарными, сначала поместите их в векторное представление , а затем возьмите скалярное произведение между векторами, которое будет равно косинусу угла между линиями. Таким образом, если это значение близко к единице, они близки к коллинеарному и должны быть объединены.

Следующая проблема - определить, достаточно ли близки линии, чтобы их нужно было соединить. Вы можете сделать это, найдя линии, которые пересекаются , или найдя линии, у которых начальная и конечная точки очень близки ... В общем, это не так просто, но вы, вероятно, можете получить 95% из них способ.