ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Shmidt                     2:464/34.74    06 Jun 2002  22:16:40
 To : Roman Ukhov
 Subject : Прекция тела на плоскость
 -------------------------------------------------------------------------------- 
 

       ><  Е  ><  Е  ><   Хау, бледнолицый  Roman!   ><  Е  ><  Е  ><
 
     (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
 
  Эй, уважаемые Roman Ukhov и Alexander Shmidt! Что за "Re: Прекция тела на
 плоскость", а где же яйца?!
  AS>> К задаче к поиску выпуклой оболочки. Только тут вместо точек -
  AS>> дуги. То, что фигура получится, в общем случае, не обязательно
  AS>> выпуклой, - не имеет значения.
 
  AS>> Идея та же:
 
  AS>> init: Выбираем отрезок(обозначим АВ), содержащий точку(А) с
  AS>> мимимальной игрековой координатой (пусть так). Если обе точки
  AS>> подходят под классификацию -
  AS>> пусть А - левая, а В - правая.
 
  RU> А шо если несколько отрезков содержат точку А?
 
 Сорри. Тогда инициализация аналогична для поиска выпуклой оболочки: ищем точку
 А, потом сортируем вектора по косинусу угла между векторами с началом в точке А
 и горизонталью и выбираем первый из них.
 
 Дальше все нормально должно быть:
 
  AS>> общий шаг:
  AS>> 1.Ищем отрезки, с концом в точке В. Далее считаем их векторами с
  AS>> началом в точке В.
  AS>> 2.Потом отсортировываем вектора по синусу (для выпуклой оболочки
  AS>> тут был бы косинус, но у нас немножко другой случай; если меня
  AS>> немножко проглючило - поправьте) угла между этим вектором и
  AS>> вектором АВ.
  AS>> 3.Выбираем вектор с минимальным значением, добавляем
  AS>> его в конечный список (содержащий решение).
  AS>> 4.Hайденный вектор
  AS>> становится новым АВ (там, где была точка В - соответственно,
  AS>> будет А, что останется - В).
  AS>> 5.goto 1, пока не залупимся.
 Good bye, mister Ukhov                          _
                                                /_|  _  _    _/
                                      Smith,   (  | (/ (- /) /   Smith...
                                                  _/
 ... Че-то меня этот Мастдай ваще не вставляет. Пойду поставлю что-нибудь другое
 --- Что за омлет, а где ВинАмп?
  * Origin: Подождем... твою тещу? Подождем... твою мать! (2:464/34.74)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Прекция тела на плоскость   Roman Ukhov   06 Jun 2002 16:21:32   Прекция тела на плоскость   Alexander Shmidt   06 Jun 2002 22:16:40