задачка о соединении точек тетраэдрами

From

Anthone Tikhonov ()

To

Alexey Vorobyov

Date

2002-10-16T14:02:31Z

Area

RU.ALGORITHMS

From: "Anthone Tikhonov" <ia26@vtb.ru>

 AV> В тpехмеpном пpостpанстве дан набоp точек. Надо их соединить тетpаэдpами
 AV> так чтобы тетpаэдpы не пеpесекались и "внутpенние" тетpаэдpы
 AV> сопpикасались в тpех веpшинах.
А в чем проблема-то? По-моему, все достаточно просто.
Правда соединить так точки можно разными способами, но если нужен один любой,
то я бы сделал так - 
1) Ищем 2 близколежащие точки (можно взять самые ближайшие) (A,B)
2) Ищем точку, ближайшую к середине полученного отрезка (C)
3) Если внутрь полученного треугольника 
  попадает еще точка, то берем ее за C, выполняем опять п.3
4) Ищем точку ближайшую к центру ABC  (D)
5) Если внутрь тетраэдра ABCD попадает точка, 
  берем за D ее, опять п.5
6) ABCD - первый тетраэдр, выполняем процедуру для каждой 
  из его сторон с п.4, только т. D надо искать в правильной 
  полуплоскости

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)