У меня есть два сегмента AB и CD (выделены красным). Эти два сегмента обращены друг к другу. Они не полностью параллельны, но и никогда не будут перпендикулярны друг другу.
Исходя из этого, мне нужно найти две нормали этих сегментов (обозначены синим), которые противостоят друг другу (т. е. две нормали находятся вне ABCD). Я знаю, как вычислить нормали сегментов, но очевидно, что каждый сегмент имеет две нормали, и я не могу понять, как программно выбрать нужные мне. Любое предложение?
Вычислите вектор v между серединами двух отрезков, направленных из AB в CD. Теперь проекция искомой нормали к AB на v должна быть отрицательной, а проекция искомой нормали к CD на v должна быть положительной. Поэтому просто вычислите нормали, сверьтесь с v и при необходимости отмените нормали, чтобы они удовлетворяли условию.
Вот это на Питоне:
# 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
Обратите внимание, что я предполагаю, что конечные точки определяют линии, удовлетворяющие условиям задачи. Я также не проверяю крайний случай, когда линии имеют одну и ту же среднюю точку; понятие «снаружи» в этом случае не применяется.
line 1 = (0,0) -> (1, 0.25) и line 2 = (1.25,-0.25) -> (2,2). Если я правильно понимаю ваш метод, я думаю, что это даст неправильную нормаль для строки 1.
- person Darren Engwirda; 21.09.2011
Я думаю, что есть два случая, чтобы рассмотреть:
Случай 1: пересечение между линиями происходит за пределами конечных точек любого сегмента.
В этом случае метод средней точки, предложенный @Michael J. Barber, точно сработает. Итак, сформируйте вектор между серединами сегментов, вычислите скалярное произведение ваших векторов нормалей с этим вектором средней точки и проверьте знак.
Если вы вычисляете нормаль для lineA, скалярное произведение нормали с вектором midB -> midA должно быть +ve.
Случай 2: пересечение между линиями происходит внутри конечных точек одного сегмента.
В этом случае сформируйте вектор между любой из конечных точек сегмента, который не включает точку пересечения, и самой точкой пересечения.
Скалярное произведение нормали для сегмента, который заключает точку пересечения, и этот новый вектор должен быть равен +ve.
Вы можете найти внешнюю нормаль для другого сегмента, потребовав, чтобы скалярное произведение между двумя нормалями было -ve (что было бы неоднозначно только в случае перпендикулярных сегментов).
Я предположил, что сегменты не коллинеарны и не пересекаются.
Надеюсь это поможет.
Вы можете уменьшить четыре комбинации для знаков следующим образом:
Вычислите скалярное произведение нормалей, отрицательный знак указывает на то, что обе они показывают снаружи или внутри.
Поскольку я предполагаю, что ваши нормали имеют единичную длину, вы можете обнаружить параллельность, если скалярное произведение имеет единицу. Положительное значение указывает, что оба изображения отображаются в одном направлении, отрицательное значение говорит о том, что оба изображения отображаются в разных направлениях.
Если нормали не параллельны: параметризуйте линии как x(t) = x0 + t * n для нормального n и вычислите t, для которых они пересекаются. Отрицательный t будет означать, что оба показываются снаружи. Достаточно, если вы сделаете это для одной из нормалей, так как вы сократили свои комбинации с 4 до 2 на шаге 1.
Если обе нормали параллельны: Рассчитайте время t, в течение которого нормали достигают средней точки между вашими сегментами. Как и в 2. достаточно, если вы сделаете это для одной из нормалей, так как вы сократили свои комбинации с 4 до 2 на шаге 1.
