![]() |
|
![]() ![]() ![]() |
|
Elfet |
|
|||
![]() Белый и Пушистый ![]() ![]() ![]() ![]() Профиль Группа: Awaiting Authorisation Сообщений: 3776 Регистрация: 2.4.2003 Репутация: нет Всего: 16 |
Приветствую!
Забил мозг уже не могу решить простую задачку: нужно определить угол между 2-я векторами, так что бы слева направо был положительным, а справа налево отрицательным. Короче что бы учитывался поворот в одну и в другую сторону. Меня хватило только на это:
Заранее спасибо! |
|||
|
||||
Akina |
|
|||
Советчик ![]() ![]() ![]() ![]() Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
А нет тут "слева направо". Первый вектор можно крутить ко второму в любом из направлений.
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
Elfet |
|
|||
![]() Белый и Пушистый ![]() ![]() ![]() ![]() Профиль Группа: Awaiting Authorisation Сообщений: 3776 Регистрация: 2.4.2003 Репутация: нет Всего: 16 |
ДА, точно. Мне короче надо определить находится ли точка внутри полигона. Это я пытаюсь сделать подсчётом углов. Если точка внутри, то 360, снаружи - 0. Как так бы подсчитать?
|
|||
|
||||
cardinal |
|
|||
![]() Инженер ![]() ![]() ![]() ![]() Профиль Группа: Экс. модератор Сообщений: 6003 Регистрация: 26.3.2002 Где: Германия Репутация: 5 Всего: 99 |
Elfet, всегда можно поделить полигон на треугольники, а дальше вот например http://forums.realcoding.net/index.php?showtopic=5943 -------------------- Немецкая оппозиция потребовала упростить натурализацию иммигрантов В моем блоге: Разные истории из жизни в Германии "Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие |
|||
|
||||
maxdiver |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Можно посчитать atan'ом углы и посмотреть. А можно воспользоваться алгеброй: знак их косого произведения (или, как ещё говорят, знаковая площадь треугольника) скажет нам, по или против часовой стрелки направлена эта тройка.
|
|||
|
||||
Earnest |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Экс. модератор Сообщений: 5962 Регистрация: 17.6.2005 Где: Рязань Репутация: 7 Всего: 183 |
Если нужно олределить точку внутри полигона, проще теоремой Жордана воспользоваться, чем косинусы считать. Там тривиальные операции, и с невыпуклыми она прекрасно работает.
-------------------- ... |
|||
|
||||
Rickert |
|
|||
![]() Ситхи не пройдут! ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 3356 Регистрация: 11.7.2006 Где: Лакрима Репутация: 1 Всего: 52 |
Есть два нормализованых вектора vec и vec2.
-------------------- Ни что не внушает сна крепче, чем день приисполненный трудов! |
|||
|
||||
Bitter |
|
|||
![]() Опытный лентяй ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1209 Регистрация: 15.8.2004 Где: Харьков, Ukraine Репутация: 4 Всего: 27 |
Earnest, расскажи подробнее, пожалуйста
|
|||
|
||||
Elfet |
|
|||
![]() Белый и Пушистый ![]() ![]() ![]() ![]() Профиль Группа: Awaiting Authorisation Сообщений: 3776 Регистрация: 2.4.2003 Репутация: нет Всего: 16 |
ок, спасибо!
![]() |
|||
|
||||
Earnest |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Экс. модератор Сообщений: 5962 Регистрация: 17.6.2005 Где: Рязань Репутация: 7 Всего: 183 |
Да все просто: ищем пересечения горизонтального полу-луча, проходящего через точку, со сторонами полигона. В зависимости от четности числа пересечений принимаем решение. Вот код. Причем, если полигон сложный (с дырками или многосвязный), это тоже будет работать, только нужно добавить внешний цикл по контурам полигона.
Где-то у меня валялась страничка, где все это очень хорошо изложено, но не могу найти. Но вроде я уже писала про это в форуме, поищи. -------------------- ... |
|||
|
||||
maxdiver |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Earnest
Только пожалуй сюда надо добавить аккуратный разбор случая, когда полулуч пройдёт ровно через вершину: в зависимости от того, куда смотрят стороны при этой вершине, - это пересечение надо считать или не надо. |
|||
|
||||
Earnest |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Экс. модератор Сообщений: 5962 Регистрация: 17.6.2005 Где: Рязань Репутация: 7 Всего: 183 |
Нет, это нормально работает и в случае прохождения луча через вершину.
На страничке, о которой я говорила, был подробный разбор, деталей я уже не помню, а восстанавливать влом. Единственная неопределенность - когда точка на границе; это не обрабатывается (результат неопределен). -------------------- ... |
|||
|
||||
maxdiver |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Согласен, будет работать правильно: там на Y-координате проверяется принадлежность полуинтервалу, а не отрезку, поэтому если луч будет проходить через вершину, он учтётся только для верхней стороны.
|
|||
|
||||
Dims |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1016 Регистрация: 21.11.2006 Репутация: 1 Всего: 11 |
Можно посчитать через векторное произведение. Длина вектора векторного произведения равна произведению длин сомножителей на синус угла между ними. Порядок имеет значение.
То есть, надо два вектора заменить единичными (для этого каждый поделить на его длину), затем векторно перемножить, взять длину полученного вектора и посчитать от неё арксинус. |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |