Как сформулировать такую ​​проблему математически?(поиск продолжения строки)

Question

У меня есть массив «линий», каждая из которых определяется 2 точками. Я работаю только с отрезками, лежащими между этими точками. Мне нужно искать строки, которые могли бы продолжать друг друга (относительно некоторого угла) и лежать на одной линии (с некоторым смещением)

Я имею в виду что-то вроде 3 строк

Я решил некоторую математическую задачу (формулировка которой является моим вопросом) и понял, что есть линии, которые можно назвать относительно одной линией (с некоторым углом K и смещением J)

И, конечно, под математической формулировкой я подразумевал какую-то математическую формулу, такую ​​как

Answer 1

Что вы пробовали до сих пор?

Я думаю, один из способов - найти пары строк, где:

1. направления похожи |theta_1 - theta_2| < eps для некоторых eps
2. есть хотя бы одна пара конечных точек, где точки близки

В зависимости от размера вашей проблемы вы можете просто проверить все пары линий на наличие условий

Answer 2

1. Сортировка всех ваших сегментов по углу (в диапазоне от 0 до Pi) и построение отсортированной карты угла к сегменту.
2. Определите некоторый порог разности углов, ниже которого два сегмента могутсчитаться параллельным.Выполните итерацию по вашей карте и для каждого сопоставления рассмотрите смежные сопоставления по обе стороны от угла (необходимо выполнить обтекание), которые считаются параллельными.
3. В каждом наборе почти параллельных сегментов посмотрите, являются ли они "продолжениями"друг от друга.

Два отрезка (A, B) и (C, D) приблизительно коллинеарны, если все возможные пары из 4 точек примерно параллельны.Вы можете использовать тот же тест, что и выше.

Псевдокод:

Angle(A,B)
    return Atan((B.y-A.y) / (B.x-A.x)) // use atan2 if possible, but needs wrapping

NearlyParallel(angle1, angle2)
    delta = Abs(angle1-angle2)
    return (delta < threshold) or (delta > Pi-threshold)

Collinear(A,B, C,D)
    // Assume NearlyParallel(Angle(A,B), Angle(C,D)) == true
    return NearlyParallel(Angle(A,C), Angle(B,D)) and NearlyParallel(Angle(A,D), Angle(B,C))

Answer 3

Начиная с: A = a2 - a1, где a1 и a2 - это угол двух линий.

Мы можем сделать это:

tan (A) = tan (a1 - a2) = (tan (a2) - tan (a1)) / (1 + tan (a1) tan (a2))

Если tan (a2) больше, чем tan (a1), то tan (A) будет острым углом между двумя линиями. Затем вы можете проверить загар (A) на предмет вашей терпимости.

Итак, я думаю, что формула будет:

tan (A) = (tan (a2) - tan (a1)) / (1 + tan (a1) tan (a2)), когда tan (a2)> tan (a1)

Но я не математик