Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Угол между векторами. 
:(
    Опции темы
Elfet
Дата 29.9.2009, 22:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Белый и Пушистый
****


Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16



Приветствую! 
Забил мозг уже не могу решить простую задачку: нужно определить угол между 2-я векторами, так что бы слева направо был положительным, а справа налево отрицательным.
Короче что бы учитывался поворот в одну и в другую сторону.
Меня хватило только на это:
Код

    float cos = (x1*x2 + y1*y2) / sqrt((x1*x1 + y1*y1) * (x2*x2 + y2*y2));
    return acos(cos) / (2 * M_PI) * 360;

Заранее спасибо!


--------------------
PM MAIL WWW Skype   Вверх
Akina
Дата 29.9.2009, 22:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454



А нет тут "слева направо". Первый вектор можно крутить ко второму в любом из направлений.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
Elfet
Дата 29.9.2009, 23:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Белый и Пушистый
****


Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16



ДА, точно.  Мне короче надо определить находится ли точка внутри полигона. Это я пытаюсь сделать подсчётом углов. Если точка внутри, то 360, снаружи - 0. Как так бы подсчитать?


--------------------
PM MAIL WWW Skype   Вверх
cardinal
Дата 30.9.2009, 00:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Инженер
****


Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 5
Всего: 99



Цитата(Elfet @  29.9.2009,  21:28 Найти цитируемый пост)
Мне короче надо определить находится ли точка внутри полигона.

Elfet, всегда можно поделить полигон на треугольники, а дальше вот например
http://forums.realcoding.net/index.php?showtopic=5943


--------------------
Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино".  А. и Б. Стругацкие
PM   Вверх
maxdiver
Дата 30.9.2009, 01:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18



Можно посчитать atan'ом углы и посмотреть. А можно воспользоваться алгеброй: знак их косого произведения (или, как ещё говорят, знаковая площадь треугольника) скажет нам, по или против часовой стрелки направлена эта тройка.
PM MAIL WWW ICQ   Вверх
Earnest
Дата 30.9.2009, 07:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 7
Всего: 183



Если нужно олределить точку внутри полигона, проще теоремой Жордана воспользоваться, чем косинусы считать. Там тривиальные операции, и с невыпуклыми она прекрасно работает.


--------------------
...
PM   Вверх
Rickert
Дата 30.9.2009, 08:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Ситхи не пройдут!
****


Профиль
Группа: Комодератор
Сообщений: 3356
Регистрация: 11.7.2006
Где: Лакрима

Репутация: 1
Всего: 52



Есть два нормализованых вектора vec и vec2.
Код
float dot = dotMultiplyFunction(vec, vec2);
if (dot > 1.0)
  dot = 1.0;
if (dot < (-1.0))
  dot = -1.0;
float res = acos(dot);



--------------------
Ни что не внушает сна крепче, чем день приисполненный трудов!
PM MAIL WWW Skype GTalk   Вверх
Bitter
Дата 30.9.2009, 13:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный лентяй
***


Профиль
Группа: Завсегдатай
Сообщений: 1209
Регистрация: 15.8.2004
Где: Харьков, Ukraine

Репутация: 4
Всего: 27



Earnest, расскажи подробнее, пожалуйста
PM MAIL ICQ Skype   Вверх
Elfet
Дата 30.9.2009, 13:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Белый и Пушистый
****


Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16



ок, спасибо! smile


--------------------
PM MAIL WWW Skype   Вверх
Earnest
Дата 30.9.2009, 15:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 7
Всего: 183



Цитата(Bitter @  30.9.2009,  14:37 Найти цитируемый пост)
Earnest, расскажи подробнее, пожалуйста 

Да все просто: ищем пересечения горизонтального полу-луча, проходящего через точку, со сторонами полигона. В зависимости от четности числа пересечений принимаем решение. Вот код. Причем, если полигон сложный (с дырками или многосвязный), это тоже будет работать, только нужно добавить внешний цикл по контурам полигона.
Код

bool PtInsidePlgn (const CPointD& pt, const poly_type& pts)
{
    poly_type::const_iterator i = pts.begin(),j = i++;
    bool bInside = false;
    for ( ; i != pts.end(); j = i++) 
    {
        if ((((i->y <= pt.y) && (pt.y < j->y)) || ((j->y <= pt.y) && (pt.y < i->y))) 
                        && (pt.x < (j->x - i->x) * (pt.y - i->y) / (j->y - i->y) + i->x))
            bInside = !bInside;
    }
   return bInside;   
}

Где-то у меня валялась страничка, где все это очень хорошо изложено, но не могу найти. Но вроде я уже писала про это в форуме, поищи.



--------------------
...
PM   Вверх
maxdiver
Дата 1.10.2009, 00:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18



Earnest
Только пожалуй сюда надо добавить аккуратный разбор случая, когда полулуч пройдёт ровно через вершину: в зависимости от того, куда смотрят стороны при этой вершине, - это пересечение надо считать или не надо.
PM MAIL WWW ICQ   Вверх
Earnest
Дата 1.10.2009, 06:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 7
Всего: 183



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


--------------------
...
PM   Вверх
maxdiver
Дата 2.10.2009, 21:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18



Согласен, будет работать правильно: там на Y-координате проверяется принадлежность полуинтервалу, а не отрезку, поэтому если луч будет проходить через вершину, он учтётся только для верхней стороны.
PM MAIL WWW ICQ   Вверх
Dims
Дата 4.10.2009, 13:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1016
Регистрация: 21.11.2006

Репутация: 1
Всего: 11



Можно посчитать через векторное произведение. Длина вектора векторного произведения равна произведению длин сомножителей на синус угла между ними. Порядок имеет значение.

То есть, надо два вектора заменить единичными (для этого каждый поделить на его длину), затем векторно перемножить, взять длину полученного вектора и посчитать от неё арксинус. 
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0948 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.