ru.algorithms

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

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

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

Тема:    Автор:    Дата:    Прекция тела на плоскость   Roman Ukhov   04 Jun 2002 13:13:59   Прекция тела на плоскость   Alexander Shmidt   05 Jun 2002 15:49:08