Всем доброго времени суток!

Опять обращаюсь за помощью.

Имеется массив точек с координатами X,Y,Z. Мне необходимо посчитать объем, который занимают эти точки. При этом желательно, чтобы учитывалось, что фигура, которую образуют эти точки, может быть с дыркой.

Как это реализовать мне вообще не понятно... У меня есть конечно идеи типа построения между каждыми тремя точками треугольников, стороны которых не могут быть больше заданной величины (для устранения вероятности построения треугольника в дырке фигуры), потом что-то посчитать от этих треугольников, но короче дальше мысль у меня не развивается пока. 
Подскажите хотя бы куда копать...

Вот изображение как строится триангуляция на плоскости, примерно так же считается площадь любой выпуклой фигуры с ровными краями.


Тебе нужно тоже самое сделать, но в объёме.
С дыркой конечно прийдётся помучаться. Можно попробовать после построения фигуры, если она с дыркой, то разрезать её на две (или больше) так, что бы линия разреза шла через дыру, тогда вместо поиска объёма одной сложной фигуры (с дыркой) надо будет найти объём нескольких простых фигур без дыр. Лучше конечно свести всё к выпуклым фигурам.

Вот и я думал по поводу триангуляции. И как я понимаю другого выхода нет.
Буду делать триангуляцией. Спасибо большое за ответ!

Любое количество точек более 4 задаёт тело в пространстве НЕОДНОЗНАЧНО. 

Думаю, что наличие дырки делает задачу нерешаемой. Триангуляция позволит вычислить объем выпуклой фигуры (при условии, что точки могут находится не только на поверхности, но и в объеме). А вот допустимость любых "впуклостей",  а уж, тем более, дырок...

Нужны какие-то дополнительные условия, которые позволили бы строго определить, что считать дыркой.

Это сообщение отредактировал(а) _Y_ - 16.12.2012, 20:19

Akina прав, нужно указывать какие точки соеденены ребрами для однозначности. Плоский случай предложенный jorka как бы однозначен потому что двухмерные точки соединятся в порядке следования в массиве. т.е. указывается их порядок.
Для наглядности можно взять квадрат ABCD, его площадь = 1. А теперь из этих же точек составим фигуру ABDC (песочные часы) площадь которой будет в 2 раза меньше.

Это сообщение отредактировал(а) Prospekt - 16.12.2012, 22:24

Точки должны быть связанные тогда объем можно вычислить.  

Ссылка раз (но без дырки), ссылка два (произвольное тело). Ищите в алгоритмах для нефтегазовой промышленности

задача помоему называется построение минимальной выпуклой оболочки.
http://habrahabr.ru/post/144921/
http://algolist.manual.ru/maths/geom/convhull/