Как узнать, находится ли вектор справа

Позвольте мне сначала определить мою проблему,

Я работаю над проблемой внутренней навигации. Поэтому я построил граф для моделирования возможных путей. Я легко могу рассчитать кратчайший путь с помощью Дейкстры и нарисовать его на карте. Все идет нормально.

Но этого недостаточно,

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

Например:

"Turn Right"
"Turn Left"
"Go on from the left"

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

И вот что я должен решить это:

 1. A undirected weighted graph  
 2. The shortest path which contains vertices and edges   
 3. X and Y Coordinates of each vertices

Кстати, я сделаю это в .Net, используя технологию маяка.

Знаете ли вы, как разделить левый и правый края, чтобы я мог давать пользователю сообщения о направлении?

Спасибо.


asp.net vector math graph-theory indoor-positioning-system
person DELIGUCU    schedule 05.02.2016    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Самый простой способ, который я могу придумать, - это взять векторное произведение вектора, представляющего направление, в котором игрок смотрит/движется, и вектора, представляющего направление, в котором вы хотите, чтобы игрок шел. Должен ли игрок повернуть налево или направо, зависит от того, Y-координата результата положительна или отрицательна, но это зависит от хиральности системы координат. Я бы просто выбрал один и попробовал. Вы правы на 50%, и если вы ошибаетесь, это легко исправить.

Изменить:

изображение кросс-продукта

Здесь мы видим, что a×b указывает вверх, когда a находится справа от b. Однако мы также видим, что -a×b указывает вниз. Таким образом, если бы a указывало в противоположном направлении — влево, — тогда перекрестное произведение было бы направлено вниз.

person John Sensebe    schedule 05.02.2016
comment
Я не мог получить связь между перекрестным произведением и левым и правым. Не могли бы вы рассказать немного подробностей? - person DELIGUCU; 05.02.2016
comment
Добавил некоторые дополнительные пояснения. - person John Sensebe; 05.02.2016

arrow_upward
0
arrow_downward

Подход скалярного произведения не работает в двух измерениях. В этом случае вы хотите использовать знак определителя матрицы [A B], где A и B — ваши векторы-столбцы. Псевдокод будет

c = знак (det ([A B]))

Здесь, если c›0 означает, что B находится слева. Это будет переключаться в зависимости от порядка A и B в вашей матрице.

person plebmatician    schedule 06.05.2021