Многогранники

С изучения аналитической геометрии.

Например на питоне. Как сделать, можешь почитать у Марка Лутца...

какой инструмент использовать для данной задачи?

И да, для начала - gnuplot. Потом хотите сами рендеринг через z-буфер пишите, хотите какой нить openGL постигайте... все от целей зависит.

афинное преобразование, проекция на плоскость.

Быть может VPython? Я когда-то хотел его посмотреть, но потом остыл.

На чём угодно. Я в своё время сделал это на си и opengl. Для каждой фигуры я задавал её вершины, затем эти вершины группировал в грани. Бесконечные сущности - плоскости и линии - я хранил в виде коэффициентов уравнения. Естественно, завёл функции линия_по_двум_точкам(), в_какой_точке_плоскость_пересекается_с_линией(), лежит_ли_точка_между_двух_других() и т.д. Точки хранил в формате opengl, для фигур своя структура (универальная, но, для простоты, с жёстко заданными лимитами на число рёбер и проч.). Короче, свелось всё к элементарной геометрии.

что почитать по данной теме

погорелов, стереометрия.

какой инструмент использовать для данной задачи

мозг.

нарисовать многогранник по заданным параметрам

Каким параметрам?

Попробую подсказать более-менее универсально:

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

производить манипуляции над данным многогранником - поворачивать, отмечать точки, строить сечения

уможать на матрицу поворота. Проще некуда.

имеетя в виду, что многогранник просто задан координатами вершин.

Посмотреть простенькие примеры интегрирования openGL-ных виджетов в GTK-интерфейс (это если помимо окна нужны еще всякие менюшки-настройки). Рисовать и поворачивать - элементарно; отмечать точки - тоже (selection buffer), строить сечения тоже просто (при отображении картины задавать нужную глубину переднего и заднего отсечения).

имеетя в виду, что многогранник просто задан координатами вершин.

В общем случае многогранник невозможно задать просто координатами вершин. Многогранник это совокупность граней, каждая грань это совокупность ребер, каждое ребро это две вершины, но грань уже можно задать в виде последовательности (списка) вершин. Для построения многогранника просто по координатам вершин требуется сначала сгруппировать вершины по граням, а это вообще то некорректная задача (имеющая не единственное решение).

С чего начать, что почитать по данной теме

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

какой инструмент использовать для данной задачи?

Должна быть куча готовых библиотек...

В VTK всё из списка вроде есть.

что почитать по данной теме

Ласло М. Вычислительная геометрия и компьютерная графика на C++.

имеетя в виду, что многогранник просто задан координатами вершин.

В общем случае многогранник невозможно задать просто координатами вершин. Многогранник это совокупность граней, каждая грань это совокупность ребер, каждое ребро это две вершины, но грань уже можно задать в виде последовательности (списка) вершин. Для построения многогранника просто по координатам вершин требуется сначала сгруппировать вершины по граням, а это вообще то некорректная задача (имеющая не единственное решение).

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

А во-вторых, я бы не был так уверен, что многогранник не определен исключительно его вершинами (при условии, что каждое ребро граничит лишь с двумя гранями)

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

И вот контр-пример для невыпуклого случая: http://www.image-share.com/upload/1363/11.png (слева - усеченная пирамида, справа - другой многогранник на тех же веришинах)

это не контрпример. Так как усеченная пирамида - выпуклый многоугольник. А то, что справа - вообще не многоугольник по ходу.

А контрпример можно сделать так:

берем таки усеченную пирамиду, потом берем точку внутри нее. Строим многоугольник так: убираем «грань-меньшее основание» и включаем в многоугольник внутреннюю точку.

Второй многоунольник с теми же вершинами строим аналогично, только убирем грань-большее основание.

очевидно, что эти два многоугольника неидентичны, причем используют теже вершины.

(при условии, что каждое ребро граничит лишь с двумя гранями)

Приведите ка мне пример, когда ребро граничит не с двумя гранями;-)

корректная, если считать многогранник выпуклым

Для выпуклого да, корректная. Но во первых про выпуклость ТС не говорил, во вторых даже для выпуклого многогранника требуются некоторые танцы с бубном для определения граней содержащих более трех вершин.

да берем любой выпуклый многогранник и добавляем одну вершину внутрь - получаем число вариантов по числу граней исходной фигуры.

(при условии, что каждое ребро граничит лишь с двумя гранями)

Приведите ка мне пример, когда ребро граничит не с двумя гранями;-)

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

корректная, если считать многогранник выпуклым

Для выпуклого да, корректная. Но во первых про выпуклость ТС не говорил,

он вообще мало про что говорил :)

во вторых даже для выпуклого многогранника требуются некоторые танцы с бубном для определения граней содержащих более трех вершин.

это лишь дело техники. да и часто достаточно иметь триянгуляцию.

две пирамиды, срощенные на ребре.

ЗачОт. Мне не хватило фантазии, каюсь...

достаточно иметь триянгуляцию.

А что вы понимаете под триянгуляцией в данном случае?

да берем любой выпуклый многогранник и добавляем одну вершину внутрь - получаем число вариантов по числу граней исходной фигуры.

больше получаем вариантов. Навскидку >=BinCoeff(n,2)

достаточно иметь триянгуляцию.

А что вы понимаете под триянгуляцией в данном случае?

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

больше получаем вариантов.

Да, согласен.

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

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

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

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

согласен. Таки да.

Ого, как обильно :) Ну, буду читать аналитическую геометрию. Всем спасибо.

А то, что справа - вообще не многоугольник по ходу.

Почему же? Грани 1, 2 и невидимое днище пирамиды оставляем на месте. А грани 3 и 4 выкидываем - вместо них добавляем грани 5, 6 и 7. http://www.image-share.com/upload/1363/99.png

А то, что справа - вообще не многоугольник по ходу.

Почему же? Грани 1, 2 и невидимое днище пирамиды оставляем на месте. А грани 3 и 4 выкидываем - вместо них добавляем грани 5, 6 и 7. http://www.image-share.com/upload/1363/99.png

даже сказать нечего, молодец. Записал в закрома.