Форум: "Начинающим";
Поиск по всему сайту: www.delphimaster.net;
Текущий архив: 2006.03.26;
Скачать: [xml.tar.bz2];




Вниз

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


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 угольные. Нада каждую грань
> разбивать на треугольники а затем считать площади. Но вот
> как грани поделить? :)

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



Сергей М. ©   (2006-03-10 14:20) [20]


> Van   (10.03.06 13:55) [17]


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



Mikhail V ©   (2006-03-10 14:23) [21]


> Сергей М. ©   (10.03.06 14:20) [20]

Астрономия преподавателя :)



Сергей М. ©   (2006-03-10 14:25) [22]


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


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

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



Mikhail V ©   (2006-03-10 14:33) [23]


> Сергей М. ©   (10.03.06 14:25) [22]

Именно



MBo ©   (2006-03-10 14:34) [24]

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

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



Desdechado ©   (2006-03-10 16:53) [25]

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



Ega23 ©   (2006-03-10 17:09) [26]

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

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



Ega23 ©   (2006-03-10 17:10) [27]


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


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



Desdechado ©   (2006-03-10 17:39) [28]

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

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




Форум: "Начинающим";
Поиск по всему сайту: www.delphimaster.net;
Текущий архив: 2006.03.26;
Скачать: [xml.tar.bz2];




Наверх





Память: 0.78 MB
Время: 0.043 c
1-1140422352      walkernet             2006-02-20 10:59  2006.03.26  
вопрос по WebBrowser


1-1140501734      Димон                 2006-02-21 09:02  2006.03.26  
Ошибки в проекте


2-1141906952      Barsky                2006-03-09 15:22  2006.03.26  
Форма поверх всех окон.


2-1141923333      Fenix                 2006-03-09 19:55  2006.03.26  
Преобразование TCaption в Pchar


15-1141233568     Piter                 2006-03-01 20:19  2006.03.26  
Радио-интернет и телефония