Есть какое-то количество точек в пространстве. Необходимо найти объем объекта, который был бы ограничен этими точками. Все боковые поверхности объекта плоские, а заданные точки являются вершинами объекта.
Объект может быть вогнутым кое-где.

Вот такая задачка.

Здравствуйте, neslon, Вы писали:

N>Есть какое-то количество точек в пространстве. Необходимо найти объем объекта, который был бы ограничен этими точками. Все боковые поверхности объекта плоские, а заданные точки являются вершинами объекта.
N>Объект может быть вогнутым кое-где.

N>Вот такая задачка.

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

Здравствуйте, xp_alp, Вы писали:

_>Необходимо еще условие, позволяющее определить, какой из возможных объектов будет искомым.

Ага, например, куб с точкой внутри. Яму можно устроить на каждой из граней.

Здравствуйте, neslon, Вы писали:

N>Есть какое-то количество точек в пространстве. Необходимо найти объем объекта, который был бы ограничен этими точками. Все боковые поверхности объекта плоские, а заданные точки являются вершинами объекта.
N>Объект может быть вогнутым кое-где.

Задача неоднозначна.
Простейший пример: куб и точка где-то внутри. Итак, нам дано 9 точек. Что это за объект?
Похоже, что из куба вычли пирамиду, основание которой — одна из граней куба, а вершина — та самая внутренняя точка.
6 разных ответов получаются.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, neslon, Вы писали:

N>>Есть какое-то количество точек в пространстве. Необходимо найти объем объекта, который был бы ограничен этими точками. Все боковые поверхности объекта плоские, а заданные точки являются вершинами объекта.
N>>Объект может быть вогнутым кое-где.

К>Задача неоднозначна.
К>Простейший пример: куб и точка где-то внутри. Итак, нам дано 9 точек. Что это за объект?
К>Похоже, что из куба вычли пирамиду, основание которой — одна из граней куба, а вершина — та самая внутренняя точка.
К>6 разных ответов получаются.

Гораздо больше шести. Можно выгрызать больше одной пирамиды, а если вершина изолируется — добивать тетраэдром.

Добавляю условие.
Каждая точка соединена с тремя ближайшие к ней точками ребрами. Надо посчитать объем тела, образорванным этими ребрами.
Так лучше?

Здравствуйте, deniok, Вы писали:

D>Гораздо больше шести. Можно выгрызать больше одной пирамиды, а если вершина изолируется — добивать тетраэдром.

Ну, это получается, что несколько вершин сливаются.

Этак и с обычным кубом можно чудеса сотворить: трактовать 8 вершин как
— 1 монолитный куб
— 4 прямоугольных тетраэдра (куб с вырезанным внутри правильным тетраэдром), соприкасающиеся по диагоналям граней куба
— 2 пирамиды с квадратными основаниями (верхняя и нижняя грани), соприкасающиеся по главной диагонали куба
— 2 прямоугольных тетраэдра (вообще несвязное тело)

Добавляю условие.
Каждая точка соединена с тремя ближайшие к ней точками ребрами. Надо посчитать объем тела, образорванным этими ребрами.
Так лучше?



neslon

Здравствуйте, Аноним, Вы писали:

А>Добавляю условие.
А>Каждая точка соединена с тремя ближайшие к ней точками ребрами. Надо посчитать объем тела, образорванным этими ребрами.

Я так понимаю, фактически даны грани объекта?
Первое что приходит в голову:
1)Поместить тело в минимально покрывающий куб
2)Взять одну из граней куба, и пропускать с каким то шагом через нее лучи.
3)Искать точки пересечения луча с гранями объекта.
4)Суммировать части луча, проходящие через внутренность объекта.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, deniok, Вы писали:

D>>Гораздо больше шести. Можно выгрызать больше одной пирамиды, а если вершина изолируется — добивать тетраэдром.

К>Ну, это получается, что несколько вершин сливаются.

Что значит сливаются? Если доп. внутри, то куб можно разложить на 6 правильных пирамид, соединив эту точку со всеми вершинами. Выгрызаем пирамиды на соседних гранях — получаем что во внутренней точке сходятся 6 рёбер.

Выгрызаем три пирамиды вокруг какой-то вершины куба — получаем полкуба зигзагообразно погрызанного, но вершина при этом отваливается. Чтобы вернуть её — достраиваем тетраэдр на одной из граней




К>Этак и с обычным кубом можно чудеса сотворить: трактовать 8 вершин как
К>- 1 монолитный куб
К>- 4 прямоугольных тетраэдра (куб с вырезанным внутри правильным тетраэдром), соприкасающиеся по диагоналям граней куба
К>- 2 пирамиды с квадратными основаниями (верхняя и нижняя грани), соприкасающиеся по главной диагонали куба
К>- 2 прямоугольных тетраэдра (вообще несвязное тело)
К>

Здравствуйте, Аноним, Вы писали:

А>Добавляю условие.
А>Каждая точка соединена с тремя ближайшие к ней точками ребрами. Надо посчитать объем тела, образорванным этими ребрами.
А>Так лучше?

Всё равно неоднозначно.



Пусть далеко от этой конструкции есть точка E.
EA = EC = x
EB = ED = y
y > x

Какой тетраэдр надстраивать — EADC или EABC?

Здравствуйте, deniok, Вы писали:

Спасибо за иллюстрацию. Не хватило воображения, понимаешь.

Здравствуйте, Аноним, Вы писали:

А>Добавляю условие.
А>Каждая точка соединена с тремя ближайшие к ней точками ребрами. Надо посчитать объем тела, образорванным этими ребрами.
А>Так лучше?

Так — легко потерять односвязность. Представь: 8 точек — две далеко разнесённые группы по 4 точки. Получишь 2 изолированных тетраэдра.

ЗЫ. А откуда эта задачка возникла? Она — часть какой-то бОльшей проблемы?

Здравствуйте, neslon, Вы писали:

N>Есть какое-то количество точек в пространстве. Необходимо найти объем объекта, который был бы ограничен этими точками. Все боковые поверхности объекта плоские, а заданные точки являются вершинами объекта.
N>Объект может быть вогнутым кое-где.

N>Вот такая задачка.

Эта "простенькая" задачка делится на три серьезные подзадачи. Ну хорошо, по крайней мере две серьезные и одну вычислительную. Где-то на форуме обсуждали вопрос, как, например, по точкам на поверхности лица восстановить его изображение -- трехмерную модель. Главная проблема в возможном "склеивании горбов у верблюда".

1. Определение фигуры по точкам. Это может оказаться очень простой или очень сложной задачей. Все зависит от того, какая у Вас есть еще информация. Очень простой, если, например, фигура заведомо выпуклая. Или для любой четверки точек известно, включается ли данная пирамида или нет. Сложной -- если ничего неизвестно. Здесь целое направление развито. По-моему, это активно используется в 3d-сканировании. В целом поиск по '"mesh reconstruction" 3d' может помочь. Либо просто упрощайте постановку.

2. Трехмерная триангуляция. Делите фигуру на треугольные пирамиды. Опять-таки, если на первом шаге что-то известно про включение пирамид, то здесь все просто. Иначе поиск по "3D triangulation" или "3D Delaunay triangulation".

3. Объем пирамиды считается по координатам 4 точек без проблем.

Кстати, с некоторым допущением можно попробовать опустить первый шаг и делать триангуляцию сразу по точкам. И посмотреть, что из этого выйдет. Загляните сюда, здесь java-апплет показывает 4 различных способа триангуляции по точкам. Там же есть ссылки на описание всех четырех алгоритмов.

Здравствуйте, Аноним, Вы писали:

А>Добавляю условие.
А>Каждая точка соединена с тремя ближайшие к ней точками ребрами. Надо посчитать объем тела, образорванным этими ребрами.
А>Так лучше?

Так хуже...
При таком подходе часть точек, находящихся далеко от поверхности, вообще не будет задействована,
они будут находится либо внутри объекта, либо снаружи.
Чтобы этого не допустить, возможен вариант, когда ребрами соединены не ближайщие точки, а точки, находящиеся на ближайщем угловом расстоянии относительно центра масс например.

А вообще ты бы лучше сказал что решает эта задача, а то так долго гадать можно.

N>Есть какое-то количество точек в пространстве. Необходимо найти объем объекта, который был бы ограничен этими точками.
...

Можно потренироваться на 2D (для начала — попробовать эту задачу строго сформулировать)

Всем спасибо за ответы.

Я и сам понимаю, что условия задачи не корректны.
Итак суть проблемы: есть объект (пусть будет самолет), контуры которого описаны точками в пространстве. Точки ложатся более-менее регулярно. Объект впуклый. Характер распределения точек неизвестен.
По идее, надо сначала соеденить ребрами ближайшие несколько точек. Видится по три ребра на одну точку. Косяки при этом весьма и весьма вероятны.
Вообще можно было бы построить сглаженный кубический сплайн, взять двойной интегральчик и посчитать объем.
Можнои (???) разбить объект на несколько сечений плоскостями через одинаковые промежутки, посчитать среднюю площадь сечений и помножить на длину отрезка перпендикуляра к сечениям.
Сечение искать перебирая точки, составляя пары точек справа-слева с минимальным расстоянием. По ним найти точки пересечения объекта с сечением, по тем уже "окружность" сечения.
В общем такие мысли...
___________________
neslon, забыл пароль

Здравствуйте, Аноним, Вы писали:

А>Я и сам понимаю, что условия задачи не корректны.
А>Итак суть проблемы: есть объект (пусть будет самолет), контуры которого описаны точками в пространстве. Точки ложатся более-менее регулярно. Объект впуклый. Характер распределения точек неизвестен.
А>По идее, надо сначала соеденить ребрами ближайшие несколько точек. Видится по три ребра на одну точку.

Как и предполагалось, задача не имеет решения в общем случае. Фактически, сводится к восстановлению связности по неким вторичным половым признакам и является "сложнейшей задачей научной магии". Вычисление объема после этого — тривиально.

А>Косяки при этом весьма и весьма вероятны.

Вот именно.

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

Здравствуйте, neslon, Вы писали:

N>Есть какое-то количество точек в пространстве. Необходимо найти объем объекта, который был бы ограничен этими точками. Все боковые поверхности объекта плоские, а заданные точки являются вершинами объекта.
N>Объект может быть вогнутым кое-где.

N>Вот такая задачка.

Вообще-то условия задачки недостаточно четкие.

Если речь о полигоне с вершинами в этих точках, то общего решения конечно нет, но можно порыться в Point cloud(s). Там по массиву 3д-точек строится поверхность. Даже иногда с дырками .