Как рассчитать, если 2 линии направлены в сторону или в сторону?

10

Учитывая 4 точки, описывающие 2 отрезка, как рассчитать, если линия A направлена ​​к линии B или от нее?

Две линии имеют фиксированную длину и могут быть измерены как расстояние от x1 / y1 до x2 / y2.

введите описание изображения здесь

Robinicks
источник
Чем отличается случай с кривой Безье от случая с прямыми линиями? Есть ли у вас кривая, которая могла бы полностью охватить другую линию (чтобы каждое направление указывало «на»)?
bummzack
1
Вы, вероятно, должны уточнить свои условия. В геометрии «линия» проходит бесконечно в любом направлении, в отличие от линии или отрезка, поэтому 2 линии всегда пересекаются, если они не параллельны. О ком ты спрашиваешь? Вы нарисовали стрелку, которая указывает направление, которое для меня подразумевает отрезок или не более половины линии. А каково ваше определение "к" и "далеко"?
Хакворт
Кривая Безье может быть сложнее представить в равенстве, необходимом для решения теста пересечения лучевой линии. Кстати, я бы поменял слово, обозначающее твою стрелку, на «луч». Вы можете получить более быстрый ответ. Я отвечу на это, если у меня будет время во время обеда, если никто больше не будет. Если нет, то это чрезвычайно распространенная задача в играх. Google "Тест пересечения отрезка лучевой линии". Я подозреваю, что тест кривой Безье похож, но я никогда не пробовал.
Брэндон
3
Вы должны разделить свой вопрос на две части. Часть с отрезками очень проста. Часть с кривыми Безье чрезвычайно сложна и имеет только приблизительное численное решение.
Сэм Хочевар
Я разделил свой вопрос на 2, как и просил. Вторая часть находится здесь: gamedev.stackexchange.com/questions/21463/…
Robinicks

Ответы:

11

Позвольте Aи Bбыть две точки на черной линии. ПозволятьC и Dбыть вашим синим сегментом. Знак zкоординаты перекрестного произведения AB^ACговорит о том, Cнаходится ли он «слева» или «справа» от черной линии. Аналогичным образом, перекрестное произведение AB^CDговорит вам, направлено ли CD«влево» или «вправо» от черной линии.

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

Поэтому должен работать следующий псевдокод:

z1 = (xB-xA)*(yC-yA) - (yB-yA)*(xC-xA);
z2 = (xB-xA)*(yD-yC) - (yB-yA)*(xD-xC);
z3 = z1 * z2;

if (z3 < 0)
    ; /* Pointing towards (BUT maybe even crossing) */
else if (z3 > 0 || z2 != 0)
    ; /* Pointing away */
else
    ; /* Parallel */

Боюсь, мне нужно время, чтобы написать правильное решение для кривой Безье. Следующая ситуация в сторону или в сторону?

Проблема?

Сэм Хоцевар
источник
Я полагаю, что для кривой вы можете найти касательную кривой в точке, ближайшей к вашему отрезку, и использовать ее так же, как при тестировании других отрезков. Наверное, немного сложнее, чем кажется :)
notlesh
@stephelton: снова посмотрите на второе изображение для кривых Безье, указывающих на кривую, которая изгибается в сторону. Или рассмотрим кривую с касательной, параллельной, возможно, пересекающемуся сегменту, но которая изгибается к сегменту и пересекается.
Каскабель
+1 за троллфейс и хорошую математику :). Однако ваша диаграмма «в направлении» на самом деле все еще имеет «прочь» - просто переместите начальную точку над линией.
Джонатан Дикинсон
@JonathanDickinson спасибо, я обновил изображение, чтобы сделать его немного более понятным, каков мой опрос!
Сэм Хочевар
2

Предполагая, что начальной точкой является зеленый круг, а конечной точкой является красная стрелка

Вычислите расстояние между начальной точкой как DS и черным сегментом и сделайте то же самое для конечной точки (красная стрелка) как DE. Если DS> DE, то сегмент направлен в сторону. если DE> DS, это указывает далеко. Если оба равны, два параллели.

Вы можете найти, как вычислить расстояние от точки до отрезка здесь , и до квадратичной кривой Безье здесь . Однако, в зависимости от формы кривой Безье, она может вернуть странные результаты (кривая может пересекать себя)

Равашоль
источник
DS> DE гарантированно работает только для прямых. Это может потерпеть неудачу для Безье. Кроме того, вы не знаете его определение «по направлению». Если расширение стрелки будет пересекать линию, определяемую двумя точками, а не отрезком, определенным теми же точками, будет ли оно все еще «в направлении»?
Хакворт
Я говорю о двух сегментах, а не о линиях, поэтому здесь нет «расширения стрелки». Кроме того, не имеет значения, куда указывает стрелка, поскольку мы говорим о расстояниях здесь. Самая близкая точка на черной линии может быть начальной / конечной точкой черной линии, это не имеет значения. Эти два сегмента могут быть коллинеарными, этот метод все равно будет работать как задумано. Для кривых Безье, о которых я упоминал, это даст странные результаты в зависимости от формы кривой.
Ravachol