Как найти две противоположные нормали или два отрезка? - PullRequest
Новая
       39

Как найти две противоположные нормали или два отрезка?

3 голосов
/ 21 сентября 2011

У меня есть два сегмента AB и CD (в красном). Эти два сегмента обращены друг к другу. Они не полностью параллельны, но никогда не будут перпендикулярны друг другу.

Исходя из этого, мне нужно найти две нормали этих сегментов (синим цветом), которые противоположны друг другу (т.е. две нормали находятся вне ABCD). Я знаю, как рассчитать нормали сегментов, но, очевидно, у каждого сегмента есть две нормали, и я не могу понять, как программно выбрать те, которые мне нужны. Любое предложение?

enter image description here

Ответы [ 3 ]

1 голос
/ 21 сентября 2011

Я думаю, что есть два случая для рассмотрения:

Случай 1 : пересечение между линиями происходит за пределами конечных точек любого сегмента.

В этом случае метод средней точки, предложенный @Michael J. Barber, сработает наверняка. Итак, сформируйте вектор между серединами сегментов, вычислите скалярное произведение ваших нормальных векторов с этим вектором средней точки и проверьте знак.

Если вы вычисляете нормаль для lineA, скалярное произведение нормали на вектор midB -> midA должно составлять +ve.

Случай 2 : Пересечение между линиями происходит внутри конечных точек одного сегмента.

В этом случае сформируйте вектор между одной из конечных точек сегмента, который не охватывает точку пересечения и саму точку пересечения.

Точечное произведение нормали для сегмента, который делает , заключает точку пересечения, и этот новый вектор должен быть +ve.

Вы можете найти внешнюю нормаль для другого сегмента, потребовав, чтобы скалярное произведение между двумя нормалями было -ve (что было бы неоднозначно только в случае перпендикулярных сегментов).

Я предположил, что сегменты не коллинеарны и не пересекаются.

Надеюсь, это поможет.

1 голос
/ 21 сентября 2011

Рассчитать вектор v между серединами двух сегментов, указывающими от AB к CD. Теперь проекция требуемой нормали на AB на v должна быть отрицательной, а проекция требуемой нормали на CD на v должна быть положительной. Поэтому просто вычислите нормали, сверьтесь с v и, если необходимо, отмените нормали, чтобы они удовлетворяли условию.

Вот оно в Python: 

# use complex numbers to define minimal 2d vector datatype
def vec2d(x,y): return complex(x,y)
def rot90(v): return 1j * v
def inner_prod(u, v): return (u * v.conjugate()).real

def outward_normals(a, b, c, d):
    n1 = rot90(b - a)
    n2 = rot90(d - c)
    mid = (c + d - a - b) / 2
    if inner_prod(n1, mid) > 0:
        n1 = -n1
    if inner_prod(n2, mid) < 0:
        n2 = -n2
    return n1, n2

Обратите внимание, что я предполагаю, что конечные точки определяют линии, соответствующие условиям в задаче. Также я не проверяю крайний случай, когда линии имеют одну и ту же среднюю точку; понятие «снаружи» в этом случае не применимо.

0 голосов
/ 21 сентября 2011

Вы можете уменьшить четыре комбинации для знаков следующим образом:

  1. Рассчитать скалярное произведение нормалей, отрицательный знак указывает, что оба показывают снаружи или внутри.

    Поскольку я предполагаю, что ваши нормали имеют единичную длину, вы можете обнаружить параллельность, если скалярное произведение имеет величину один. Положительное значение указывает, что оба показывают в одном направлении, отрицательное значение говорит, что оба показывают в разных направлениях.

  2. Если нормали не параллельны: параметризовать линии как x(t) = x0 + t * n для нормали n и вычислить t, для которого оба пересекаются. Отрицательный t укажет, что оба показывают снаружи. Достаточно сделать это для одной из нормалей, поскольку вы уменьшили свои комбинации с 4 до 2 на шаге 1.

  3. Если обе нормали совпадают: вычислите время t, за которое нормали достигают средней точки между вашими сегментами. Как в 2. достаточно, если вы делаете это для одной из нормалей, так как вы уменьшили свои комбинации с 4 до 2 на шаге 1.

...