On Fri, 10 Mar 2006 11:47:48 +0200, Аноним <0@users.rsdn.ru> wrote:
> Есть задача. Определить площадь поверхности выпуклого многогранника, > зная только координаты точек в 3D системе координат (x, y, z). > > Помогите пожалуйста ее сделать. Дайте ссылки по описанию алгоритма. > Заранее спасибо...
1. Перебираешь все тройки точек.
2. Если все остальнык точки лежат по одну сторону от плоскости
образованной данными, то прибавляешь ее площадью
есть ньюансы, но все решимо
Здравствуйте, Аноним, Вы писали:
А>Есть задача. Определить площадь поверхности выпуклого многогранника, А>зная только координаты точек в 3D системе координат (x, y, z).
А>Помогите пожалуйста ее сделать. Дайте ссылки по описанию алгоритма. А>Заранее спасибо...
Через одну из вершин разбиваете многоугольник на треугольник и считаете сумму площадей треугольников. А вообще, если готовая формула для выпуклого многоугольника, которая позволяет вычислять площадь по точкам! Гугль Вам в помощь!
Здравствуйте, Venn, Вы писали:
V>On Fri, 10 Mar 2006 11:47:48 +0200, Аноним <0@users.rsdn.ru> wrote:
>> Есть задача. Определить площадь поверхности выпуклого многогранника, >> зная только координаты точек в 3D системе координат (x, y, z). >> >> Помогите пожалуйста ее сделать. Дайте ссылки по описанию алгоритма. >> Заранее спасибо...
V>1. Перебираешь все тройки точек. V>2. Если все остальнык точки лежат по одну сторону от плоскости V> образованной данными, то прибавляешь ее площадью V>есть ньюансы, но все решимо
Это будет работать, только если каждая грань многогранника является треугольником. Достаточно существенный нюанс для этого и так достаточно неэффективного способа.
Здравствуйте, Azst, Вы писали:
A>Через одну из вершин разбиваете многоугольник на треугольник и считаете сумму площадей треугольников. А вообще, если готовая формула для выпуклого многоугольника, которая позволяет вычислять площадь по точкам! Гугль Вам в помощь!
Надо не для многоугольника, а для многогранника. А площадь любого простого многоугольника, хоть выпуклого, хоть невыпуклого считается элементарно: sum(x[i]*y[i+1] — x[i+1]*y[i])/2. Заодно получим направление обхода (знак площади).
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, Аноним, Вы писали:
А>Есть задача. Определить площадь поверхности выпуклого многогранника, А>зная только координаты точек в 3D системе координат (x, y, z).
Что-то мне подсказывает, что надо копать в сторону выпуклых оболочек (convex hull). Ведь точки могут быть никак не упорядочены, значит у нас нет информации о связности (гранях). Следовательно, необходимо как минимум упорядочить точки, например, по широте-долготе относительно центра масс. А потом уже — попытаться вычислить сами грани. То есть, задача сводится к построению многогранника как такового по набору точек.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, _DAle_, Вы писали:
_DA>Это будет работать, только если каждая грань многогранника является треугольником.
Не обязательно. Просто точки лежащие в той же плоскости, не надо вообще учитывать при определении, лежат ли все остальные точки с одной стороны от плоскости образованной тремя выбранными точками.
Здравствуйте, Рома Мик, Вы писали:
РМ>Здравствуйте, _DAle_, Вы писали:
_DA>>Это будет работать, только если каждая грань многогранника является треугольником. РМ>Не обязательно. Просто точки лежащие в той же плоскости, не надо вообще учитывать при определении, лежат ли все остальные точки с одной стороны от плоскости образованной тремя выбранными точками.
Неправда, нельзя их просто не рассматривать, надо будет построить в этой плоскости выпуклую оболочку и найти площадь получившегося многоугольника.
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, Аноним, Вы писали:
А>>Есть задача. Определить площадь поверхности выпуклого многогранника, А>>зная только координаты точек в 3D системе координат (x, y, z).
MS>Что-то мне подсказывает, что надо копать в сторону выпуклых оболочек (convex hull). Ведь точки могут быть никак не упорядочены, значит у нас нет информации о связности (гранях). Следовательно, необходимо как минимум упорядочить точки, например, по широте-долготе относительно центра масс. А потом уже — попытаться вычислить сами грани. То есть, задача сводится к построению многогранника как такового по набору точек.
Так и есть, надо построить выпуклую оболочку на этом множестве точек, а потом уже просуммировать площади граней. Эффективные методы построения выпуклых оболочек размерности больше двух можно найти, например, в книге Препарата-Шеймос "Вычислительная геометрия: введение". Например, метод заворачивания подарка (он же обход Джарвиса). Если же эффективность большой роли не играет, можно воспользоваться алгоритмом, упомянутым выше, со сложностью O(n^4).
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, Azst, Вы писали:
A>>Через одну из вершин разбиваете многоугольник на треугольник и считаете сумму площадей треугольников. А вообще, если готовая формула для выпуклого многоугольника, которая позволяет вычислять площадь по точкам! Гугль Вам в помощь!
MS>Надо не для многоугольника, а для многогранника. А площадь любого простого многоугольника, хоть выпуклого, хоть невыпуклого считается элементарно: sum(x[i]*y[i+1] — x[i+1]*y[i])/2. Заодно получим направление обхода (знак площади).
Здравствуйте, Аноним, Вы писали:
А>Есть задача. Определить площадь поверхности выпуклого многогранника, А>зная только координаты точек в 3D системе координат (x, y, z).
А>Помогите пожалуйста ее сделать. Дайте ссылки по описанию алгоритма. А>Заранее спасибо...
Если у тебя есть многогранник, то значит ты имеешь все его грани, которые есть
многоугольниками. Ну а тогда считаешь площадь кодого моногоугоьника и т.п.
Если у тебя есть просто набор точек(в пространстве) и ты не знаешь
где-какая грань, то , в принципе, можно триангулировать было бы этот масив точек.
