Площадь многогранника

← →
Van (2006-03-10 12:48) [0]

Есть задача. Определить площадь поверхности выпуклого многогранника,
зная только координаты точек в 3D системе координат (x, y, z).

Помогите пожалуйста ее сделать. Дайте ссылки по описанию алгоритма.
Заранее спасибо...

← →
Desdechado © (2006-03-10 12:54) [1]

> координаты точек
каких? вершин?

← →
Van (2006-03-10 12:56) [2]

да

← →
Ega23 © (2006-03-10 12:58) [3]

Хм... Прикольная задачка...
Ща подумаем...

← →
Desdechado © (2006-03-10 13:10) [4]

последовательность вершин есть или вычислять точки, образующие грани, предоставлено тебе?

← →
Desdechado © (2006-03-10 13:11) [5]

все ли точки являются вершинами? а то, может, какая-нибудь внутрь попадет?

← →
Fay © (2006-03-10 13:13) [6]

Есть n вершин. Нужно найти сумму площадей n-2 треугольников. Ужасно сложно.

← →
Ega23 © (2006-03-10 13:17) [7]

Уравнения рёбер известны, или нет? Если известны, то, в принцине найти можно. Если нет - то очень интересная задачка... :о)

← →
Sergey13 © (2006-03-10 13:18) [8]

2[6] Fay © (10.03.06 13:13)
>Есть n вершин. Нужно найти сумму площадей n-2 треугольников. Ужасно сложно.
N-2? У египетской пирамиды 5 вершин. Какими 3-мя треугольниками обойдемся?

← →
Alkid © (2006-03-10 13:19) [9]

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

← →
Сергей М. © (2006-03-10 13:24) [10]

> Van (10.03.06 12:48)

Начни с площади треугольника с заданными координатами вершин.
Все остальное базируется именно на этом и легко решается.

← →
Mikhail V © (2006-03-10 13:36) [11]

> Сергей М. © (10.03.06 13:24) [10]

Основное в этой задаче - перебор гране многогранника. А это не тривиально.

← →
Mikhail V © (2006-03-10 13:37) [12]

> Начни с площади треугольника с заданными координатами вершин.
>
> Все остальное базируется именно на этом и легко решается.
>

- а вот этим как раз и закончиш

← →
Alkid © (2006-03-10 13:47) [13]

Есть мысль, что если вычислить параметры эллипсоида, аппроксимируемого
данным многогранником, то по полярным координатам проекций точек на поверхность этого эллипсоида можно достаточно просто составить треугольники граней.

← →
Fay © (2006-03-10 13:47) [14]

2 Sergey13 © (10.03.06 13:18) [8]
Это меня колбасит - вопрос прочитал по диагонали.
Всё как обычно, короче 8(

← →
Сергей М. © (2006-03-10 13:50) [15]

> перебор гране многогранника. А это не тривиально

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

> Mikhail V © (10.03.06 13:37) [12]
> а вот этим как раз и закончиш

Аргументы ?

← →
Alkid © (2006-03-10 13:54) [16]

> Потому что задавать вершины граней нужно не от балды, а
> как положено - с единым направлением обхода.

Тогда не интересно. Фишка и менно в том, что бы восстановить порядок соединения граней только по заданному набору вершин, без задания их порядка.

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

> Аргументы ?

В конечном итоге будем рассчитывать площади треугольников, не иначе :)

← →
Van (2006-03-10 13:55) [17]

Грани не только треугольные, а N угольные. Нада каждую грань разбивать на треугольники а затем считать площади. Но вот как грани поделить? :)

← →
Mikhail V © (2006-03-10 13:55) [18]

> Потому что задавать вершины граней нужно не от балды, а
> как положено - с единым направлением обхода.

:))))))) Обойди тэтраэдр

← →
Alkid © (2006-03-10 13:56) [19]

> Грани не только треугольные, а N угольные. Нада каждую грань
> разбивать на треугольники а затем считать площади. Но вот
> как грани поделить? :)

Видишь ли, можно любой многогранник представить как имеющий треугольные грани, только некоторые из этих треугольников могут быть компланарны.
А как поделить - мысль работает...

> Van (10.03.06 13:55) [17]

Что мешает изначально задать многогранник "правильно" ?
Т.е. набором вершин именно треугольных фейсов, с заранее определенным направлением обхода вершин ?

> Mikhail V © (10.03.06 14:23) [21]

Значит первая задача - отсортировать и разбить/сгруппировать список вешин.

Все остальное при этом не составит трудностей.

>Van (10.03.06 13:55) [17]
>Грани не только треугольные, а N угольные. Нада каждую грань разбивать на треугольники а затем считать площади

Не нужно разбивать.
http://kladovka.net.ru/delphibase/?action=viewfunc&topic=mathcalc&id=10091

Alkid © (10.03.06 13:54) [16]
> один такой набор в общем случае может описывать более чем один многогранник
если он выпуклый, то вряд ли

Тут посовещались и родился следующий алгоритм:
1. Для каждых трёх точек составляем уравнение плоскости
2. Для каждой точки рассчитываем местонахождение относительно очередной плоскости ("выше", "ниже", "принадлежит плоскости").
3. Если все точки оказались ("выше" или "принадлежит плоскости") или ("ниже" или "принадлежит плоскости") - значит это грань. Считаем её площадь.
4. Goto 2 для следующей плоскости.

Можно оптимизировать.

> если он выпуклый, то вряд ли

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

> Надо сначала доказать.
Это в общем случае. А в условии выпуклость прозвучала явно, что значительно упрощает задачу.

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

Площадь многогранника Найти похожие ветки