IPB
ЛогинПароль:

> Компиляция правил для данного раздела

1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Вектора в полуплоскости
сообщение
Сообщение #1


Fanat
***

Группа: Пользователи
Сообщений: 261
Пол: Мужской
Реальное имя: Сергей

Репутация: -  5  +


Подскажите алгоритм (наверно, скорее формулу) определения находятся ли все (допустим 3) вектора в одной полуплоскости.
Например (1,1) (1,2) (-1,1) находятся, а (1,1), (-1,0), (1,-1) нет.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Fanat
***

Группа: Пользователи
Сообщений: 261
Пол: Мужской
Реальное имя: Сергей

Репутация: -  5  +


Цитата(Fanat @ 20.12.2008 14:08) *

Подскажите алгоритм (наверно, скорее формулу) определения находятся ли все (допустим 3) вектора в одной полуплоскости.
Например (1,1) (1,2) (-1,1) находятся, а (1,1), (-1,0), (1,-1) нет.


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

Буду делать так. Может можно лучше.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Fanat @ 20.12.2008 14:08) *
алгоритм (наверно, скорее формулу) определения находятся ли все (допустим 3) вектора в одной полуплоскости.
Нет, скорее алгоритм smile.gif.
Идешь в цикле по всем векторам Ai.
Производишь поворот системы координат (от исходного положения) на угол, который текущий вектор Ai составляет с осью Х. После такого поворота его Y-компонента занулится:
(Aix, Aiy) -> (Aix', 0) .
Все остальные вектора также подвергнутся преобразованию:
(Ajx, Ajy) -> (Ajx', Ajy') .
Проходишь в цикле по всем остальным (кроме i-того и последнего) векторам и смотришь произведение:
mj = Ajy' * Aj+1y'
Если все такие произведения неотрицательны:
mj <=0 ,
то все вектора лежат в одной полуплоскости, причем сечение плоскости производится вектором Ai. Если нет - продолжить внешний цикл.

Вроде так. Замучился индексы проставлять.. smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Fanat
***

Группа: Пользователи
Сообщений: 261
Пол: Мужской
Реальное имя: Сергей

Репутация: -  5  +


Цитата(Lapp @ 21.12.2008 9:57) *

Нет, скорее алгоритм smile.gif.
Идешь в цикле по всем векторам Ai.
Производишь поворот системы координат (от исходного положения) на угол, который текущий вектор Ai составляет с осью Х. После такого поворота его Y-компонента занулится:
(Aix, Aiy) -> (Aix', 0) .
Все остальные вектора также подвергнутся преобразованию:
(Ajx, Ajy) -> (Ajx', Ajy') .
Проходишь в цикле по всем остальным (кроме i-того и последнего) векторам и смотришь произведение:
mj = Ajy' * Aj+1y'
Если все такие произведения неотрицательны:
mj <=0 ,
то все вектора лежат в одной полуплоскости, причем сечение плоскости производится вектором Ai. Если нет - продолжить внешний цикл.

Вроде так. Замучился индексы проставлять.. smile.gif


Спасибо...думаю, пригодится smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 21:40
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name