Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Определение направления обхода в замкнутом контуре
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
~erwin~ ~erwin~ вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.10.2006
По умолчанию 29.10.2007, 20:21

Помогите пожалуйста решить такую задачку
Есть замкнутый контур который состоит из отрезков прямых, каждый отрезок имеет коорд начала и конца (т.е. по сути является вектором)
требуется определить направление обхода в таком контуре. Контур самопересечений не имеет.
Все отрезки (вектора) следуют друг за другом.
В общем каким образом зная координаты точек контура определить в какую сторону он ориентирован (по часовой стрелке или против часовой стрелке)?
Ответить с цитированием
  (#2 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,270
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 29.10.2007, 21:19

Берем точку внутри контура и считаем относительно нее изменение азимута.
Ответить с цитированием
  (#3 (permalink)) Старый
~erwin~ ~erwin~ вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.10.2006
По умолчанию 29.10.2007, 21:44

не понял...
во-первых что такое "изменение азимута"?
во-вторых как его считать?

есть мысль делать это через векторное произведение исходя из того что если векторное произведение двух векторов > 0 то соответственно поворот от первого вектора ко второму осущ против часовой стрелки, в противном случае наоборот
Ответить с цитированием
  (#4 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,270
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 29.10.2007, 22:28

Кстати, весьма здравая идея - посчитать суммарный угол поворота самих векторов.
Просто считать знак поворота ничего не даст, так как при сложной форме контура могут быть повороты в обе стороны. Надо считать именно углы и суммировать. Тогда знак суммарного угла поворота будет показывать направление обхода.
Ответить с цитированием
  (#5 (permalink)) Старый
~erwin~ ~erwin~ вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.10.2006
По умолчанию 29.10.2007, 22:35

Цитата:
Кстати, весьма здравая идея - посчитать суммарный угол поворота самих векторов.
Просто считать знак поворота ничего не даст, так как при сложной форме контура могут быть повороты в обе стороны. Надо считать именно углы и суммировать. Тогда знак суммарного угла поворота будет показывать направление обхода.
имеются в виду углы между двумя соседними векторами?
или углы между вектором и положительной полуосью ОХ?

я пробовал реализовать такую штуку: найти сумму углов м/д всеми соседними векторами т. е. угол_между (1 и 2) + угол_между (2 и 3) и тд
но все равно получилась такая штука что внезависимости от направления обхода в контуре сумма углов равна 360 градусов

или я чего-то не помимаю?
может на примере рассмотрим простом?
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,270
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 30.10.2007, 03:30

Надо учитывать направление поворота, то есть считать угол положительным, если в порядке обхода контура поворот от первого вектора ко второму происходит против часовой стрелки, и отрицательным - в противоположном случае.

Собственно, на простых контурах и должно получиться +360 или -360, по знаку и направление обхода определяется.
А если контур, например, завязан восьмеркой, должен ноль получиться.
Ответить с цитированием
  (#7 (permalink)) Старый
~erwin~ ~erwin~ вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.10.2006
По умолчанию 30.10.2007, 08:00

Цитата:
Надо учитывать направление поворота, то есть считать угол положительным, если в порядке обхода контура поворот от первого вектора ко второму происходит против часовой стрелки, и отрицательным - в противоположном случае.

Собственно, на простых контурах и должно получиться +360 или -360, по знаку и направление обхода определяется.
А если контур, например, завязан восьмеркой, должен ноль получиться.
контур самопересечений не имеет, посемувсякой шняги типа восьмерок не будет

Все, кажись понял как нада правильно сделать. Суть в чем: берем два соседних вектора и для них определяем направление поворота через векторное произведение, затем через скалярное произведение определяем угол поворота. Таким обрвзом мы получим значение угла с нужным знаком.
Сегодня вечером проверю это решение и отпишусь работает или нет.
Ответить с цитированием
  (#8 (permalink)) Старый
~erwin~ ~erwin~ вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.10.2006
По умолчанию 05.11.2007, 23:13

все никак руки не доходили отписаться
в общем проблема нахождения обхода контуру решена как раз таки через векторные и скалярные произведения
то есть для каждой пары векторов находим cos угла между ними и собственно сам угол
также находим векторное произведение - если оно положительно то поворот против часовой стрелки, если отрицательно - то почасовой
ну и в зависимости от направления поворота каждый угол будет либо положителен либо отрицателен
все найденные углы складываем с учетом их знаков, если сумма равна +360 значит обход противчасовой стрелки
если -360 значит по часовой
Ответить с цитированием
  (#9 (permalink)) Старый
~erwin~ ~erwin~ вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.10.2006
По умолчанию 05.11.2007, 23:23

попутно возник еще один вопрос:
объясните как устроен габаритный тест в двухмерном пространстве, точнее как он алгоритмически реализуется
Ответить с цитированием
  (#10 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 05.11.2007, 23:37

Что за габаритный тест?


импортирован с progz.ru
Ответить с цитированием
  (#11 (permalink)) Старый
~erwin~ ~erwin~ вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.10.2006
По умолчанию 06.11.2007, 23:28

Цитата:
Что за габаритный тест?
габаритный тест это такая штука для опредения пересечения объектов
каждый объект заключается в прямоугольную оболочку, как бы вписывается в прямоугольник
пересечение проверяется следующим образом: если прямоугольные оболочки не пересекаются то и сами объекты не пересекаются
в противном случае - сами объекты могут пересечься
По сути габаритный тест сводится к определению пересечения 2-х прямоугольников

Вот как это аналитически решить зная координаты прямоугольников я не знаю
Ответить с цитированием
  (#12 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 07.11.2007, 00:53

Ну как.. Ищешь максимальную иксовую компоненту - это координата правой грани прямоугольника. С минимальной компонентой- левая грань прямоугольника. Тоже самое и для y-компоненты и верхней с нижней гранями.


импортирован с progz.ru
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
~erwin~ ~erwin~ вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.10.2006
По умолчанию 07.11.2007, 07:39

Цитата:
Ну как.. Ищешь максимальную иксовую компоненту - это координата правой грани прямоугольника. С минимальной компонентой- левая грань прямоугольника. Тоже самое и для y-компоненты и верхней с нижней гранями.
и?
Ответить с цитированием
  (#14 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,270
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 07.11.2007, 08:01

Эволюция найденных способов решения

1. Пересечение отрезков будет, если хотя бы один конец второго попадает внутрь первого и наоборот (8 сравнений).

2. Выбираем в качестве первого отрезка тот, который имеет наименьшую левую границу. Тогда пересечение отрезков будет, если левый конец второго попадает внутрь первого (4 сравнения).
Код:
(X_left_1 < X_left_2 && X_left_2 < X_right_1) || (X_left_2 < X_left_1 && X_left_1 < X_right_2)
3. Пересечения НЕ будет, если один из отрезков целиком левее или правее другого. Соответственно, берем отрицание этого утверждения (2 сравнения).
Код:
(X_left_2 < X_right_1) && (X_left_1 < X_right_2)
Пересечение прямоугольников будет при пересечении отрезков по каждому измерению
Ответить с цитированием
  (#15 (permalink)) Старый
batman batman вне форума
Member
 
Сообщений: 105
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2007
Talking 14.11.2007, 07:47

Цитата:
в общем проблема нахождения обхода контуру решена как раз таки через векторные и скалярные произведения
то есть для каждой пары векторов находим cos угла между ними и собственно сам угол
также находим векторное произведение - если оно положительно то поворот против часовой стрелки, если отрицательно - то почасовой
ну и в зависимости от направления поворота каждый угол будет либо положителен либо отрицателен
все найденные углы складываем с учетом их знаков, если сумма равна +360 значит обход противчасовой стрелки
если -360 значит по часовой
- что за фигня !!!

Ты имеешь вектор n, относительно которого и определяется против- или по- часовой ведётся обход
(если контур лежит на XoY , n =(0,0,1) )
далее находишь векторное произведение векторов , соответствующих 2 смежным отрезкам
получившийся вектор скалярно умножаешь на n и по знаку этого произведения(+ -) определяешь по- или против часовой ведётся обход
ВСЁ!!!

Если задача из обл. комп. графики, то n - "вектор взгляда" или нормаль к экрану
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Определение предмета victor1963 Вопросы начинающих программистов 0 24.01.2012 19:55
Устаранить зачыкливание в процедуре обхода графа в глубину. savelev Pascal 0 26.12.2010 11:47
маршрут обхода слонов _Студент_ Prolog 0 12.12.2010 23:29
Реализация обхода графа KYC1989 Prolog 22 16.12.2009 21:15
Разработать программу обхода шахматной доски bIRKA Lisp 0 19.05.2009 20:55
Подскажите анонимайзер для обхода Firewall. sarsed Любые вопросы от новичков 1 28.10.2008 08:32
Ведущий менеджер направления игры и приложения ludi Работа 1 27.06.2008 21:58
Метод грэхама обхода выпуклой оболочки оля-kzn Алгоритмы 3 01.06.2006 03:53
В компанию приглашается Руководитель нового направления. imported_sky Работа 1 29.11.2005 11:44
Задаются координаты вершин многоугольника в порядке обхода Julia_L Алгоритмы 20 01.10.2005 11:28



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов