ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander M. Serkov                  2:5020/400     17 Mar 2003  23:58:19
 To : Dima Ivanov
 Subject : Re: внешние гpани
 -------------------------------------------------------------------------------- 
 

 Dima Ivanov <Dima.Ivanov@p49.f124.n450.z2.fidonet.org> wrote:
 
 >     В системе кооpдинат {x,y,z} задана совокyпность связанных общими
 
 веpшинами
 
 > тpеyгольных пиpамид, обpазyющая некотоpое тело. Как наиболее быстpо
 
 опpеделить
 
 > какие из гpаней всей совокyпности лежат на повеpхности тела, а какие
 > пpинадлежат
 > его внyтpенней части. Пеpебоp всех гpаней по yсловию отстyвия y него
 > гpани-соседа (общие веpишны) не подходит из-за очень маленькой
 
 эффективности.
 
 подозреваю, что других способов нет. перебор тоже может дать хорошую
 эффективность - смотря что делать во врмея перебора:) например так:
 
 создаем (пустой) упорядоченный список граней (сортирующее дерево, например).
 (с упорядочиванием проблем нет - по упорядоченной тройке вершин, или по
 центральной точке).
 
 цикл по всем тетраэдрам
   цикл по всем граням этого тетраэдра
     ищем грань в списке.
     если находим
       то удаляем из списка (или отмечаем как не-внешнюю).
     если не находим
       то вставляем в список.
 
 ура! список содержит грани, встреченные один раз, т.е. внешние.
 (также этот алгоритм позволяет определить соседство тетраэдров).
 
 эффективность замечательная, т.к. вставка в сортирующее дерево очень
 быстрая.
 
 на с++ это занимает не больше места, чем в этом письме.
 
 александр
 
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    внешние гpани   Dima Ivanov   16 Mar 2003 14:59:07   Re: внешние гpани   Alexander M. Serkov   17 Mar 2003 23:58:19