Re: задачка

From

Sergey Andrianov (2:5020/1507.400)

To

Alexey Vorobyov

Date

2002-10-15T23:08:34Z

Area

RU.ALGORITHMS

Здравствуй, Alexey!

Однажды 14-Oct-02  в 21:22   Alexey Vorobyov (2:5095/1.82)
написал       All    по поводу
-=-   задачка  -=-

AV> Дайте пожалуйста ссылки или подскажите алгоpитм pешения следующей задачи:

AV> В тpехмеpном пpостpанстве дан набоp точек. Надо их соединить тетpаэдpами 
AV> так чтобы тетpаэдpы не пеpесекались и "внутpенние" тетpаэдpы сопpикасались 
AV> в тpех веpшинах.

	1. Произвольно выбираешь три точки (например, сначала две ближайшие, а затем ближайшую к ним же третью. 
	2. Через 3 выбранные точки проводишь плоскость.
	3. Находишь ближайшую точку к этой плоскости - это и будет первый тетраэдр. Остальные строишь на его гранях, для чего. 
	4. Для каждой из (свободных) граней тетраэдра находишь ближайшую "внешнюю точку, получая новый тетраэдр. 
	5. Выполняешь, начиная с 3 до тех пор, пока точки не кончатся. 

	На самом деле алгоритм, конечно, рекурсивный.


                  До свидания,  в  23:04 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)