Версия для печати темы

Автор: Fanat 20.12.2008 18:08

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

Автор: Fanat 20.12.2008 19:56

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

Буду делать так. Может можно лучше.

Автор: Lapp 21.12.2008 13:57

Нет, скорее алгоритм .
Идешь в цикле по всем векторам Aⁱ.
Производишь поворот системы координат (от исходного положения) на угол, который текущий вектор Aⁱ составляет с осью Х. После такого поворота его Y-компонента занулится:
(Aⁱ_x, Aⁱ_y) -> (Aⁱ_x', 0) .
Все остальные вектора также подвергнутся преобразованию:
(A^j_x, A^j_y) -> (A^j_x', A^j_y') .
Проходишь в цикле по всем остальным (кроме i-того и последнего) векторам и смотришь произведение:
m_j = A^j_y' * A^j+1_y'
Если все такие произведения неотрицательны:
m_j <=0 ,
то все вектора лежат в одной полуплоскости, причем сечение плоскости производится вектором Aⁱ. Если нет - продолжить внешний цикл.

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

Автор: Fanat 21.12.2008 16:39

Спасибо...думаю, пригодится