| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Объем фигуры, построенной по точкам |
| Автор: Dementor 15.12.2012, 22:54 |
| Всем доброго времени суток! Опять обращаюсь за помощью. Имеется массив точек с координатами X,Y,Z. Мне необходимо посчитать объем, который занимают эти точки. При этом желательно, чтобы учитывалось, что фигура, которую образуют эти точки, может быть с дыркой. Как это реализовать мне вообще не понятно... У меня есть конечно идеи типа построения между каждыми тремя точками треугольников, стороны которых не могут быть больше заданной величины (для устранения вероятности построения треугольника в дырке фигуры), потом что-то посчитать от этих треугольников, но короче дальше мысль у меня не развивается пока. Подскажите хотя бы куда копать... |
| Автор: jorka 15.12.2012, 23:17 |
Вот изображение как строится триангуляция на плоскости, примерно так же считается площадь любой выпуклой фигуры с ровными краями. Тебе нужно тоже самое сделать, но в объёме. С дыркой конечно прийдётся помучаться. Можно попробовать после построения фигуры, если она с дыркой, то разрезать её на две (или больше) так, что бы линия разреза шла через дыру, тогда вместо поиска объёма одной сложной фигуры (с дыркой) надо будет найти объём нескольких простых фигур без дыр. Лучше конечно свести всё к выпуклым фигурам. |
| Автор: Dementor 15.12.2012, 23:32 |
| Вот и я думал по поводу триангуляции. И как я понимаю другого выхода нет. Буду делать триангуляцией. Спасибо большое за ответ! |
| Автор: Akina 16.12.2012, 20:17 | ||
Любое количество точек более 4 задаёт тело в пространстве НЕОДНОЗНАЧНО. |
| Автор: _Y_ 16.12.2012, 20:18 |
| Думаю, что наличие дырки делает задачу нерешаемой. Триангуляция позволит вычислить объем выпуклой фигуры (при условии, что точки могут находится не только на поверхности, но и в объеме). А вот допустимость любых "впуклостей", а уж, тем более, дырок... Нужны какие-то дополнительные условия, которые позволили бы строго определить, что считать дыркой. |
| Автор: Prospekt 16.12.2012, 20:46 |
| Akina прав, нужно указывать какие точки соеденены ребрами для однозначности. Плоский случай предложенный jorka как бы однозначен потому что двухмерные точки соединятся в порядке следования в массиве. т.е. указывается их порядок. Для наглядности можно взять квадрат ABCD, его площадь = 1. А теперь из этих же точек составим фигуру ABDC (песочные часы) площадь которой будет в 2 раза меньше. |
| Автор: Pavia 16.12.2012, 22:05 |
| Точки должны быть связанные тогда объем можно вычислить. |
| Автор: Silent 17.12.2012, 07:38 |
| Ссылка http://www.gamedev.net/page/resources/_/technical/game-programming/area-and-volume-calculations-r2247 (но без дырки), ссылка http://blog.simmakers.ru/algoritm-vychisleniya-objema-v-3d-prostranstve/ (произвольное тело). Ищите в алгоритмах для нефтегазовой промышленности |
| Автор: mrgloom 17.12.2012, 08:58 |
| задача помоему называется построение минимальной выпуклой оболочки. http://habrahabr.ru/post/144921/ http://algolist.manual.ru/maths/geom/convhull/ |
