Расчет центроида и объема многогранника при заданных вершинах

Учитывая расположение вершин выпуклого многогранника (3D), мне нужно вычислить центр тяжести и объем многогранника. Следующий код доступен на сайте Mathworks < / а>.

function C = centroid(P)
k=convhulln(P);
if length(unique(k(:)))<size(P,1)
    error('Polyhedron is not convex.');
end
T = delaunayn(P);
n = size(T,1);
W = zeros(n,1);
C=0;
for m = 1:n
    sp = P(T(m,:),:);
    [null,W(m)]=convhulln(sp);
    C = C + W(m) * mean(sp);
end
C=C./sum(W);
return
end

Код элегантный, но ужасно медленный. Мне нужно сотни раз вычислить объем и центроид тысяч многогранников. Использование этого кода в его текущем состоянии невозможно. Кто-нибудь знает лучший подход или этот код можно сделать быстрее? Есть некоторые незначительные изменения, о которых я могу подумать, например, замена mean выражением для среднего.


matlab performance volume centroid polyhedra
person John Smith    schedule 06.01.2013    source источник

Ответы (3)


arrow_upward
3
arrow_downward

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

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

Затем центр тяжести многогранника может быть вычислен путем применения теоремы о расходимости, переводящей интегрирование по всему объему многогранника в интегрирование по поверхности многогранника. Подробное описание можно найти в Расчет объема и центроида многогранника в 3D. Я не проверял, действительно ли тесселяция многогранника в треугольники необходима, или же можно работать и с более сложными многоугольными поверхностями многогранника, но в любом случае тесселяция поверхностей граней намного проще, чем тесселяция объема. В целом такой комбинированный подход должен быть намного быстрее, чем объемный подход.

person Rainer    schedule 12.11.2013

arrow_upward
1
arrow_downward

Единственный вариант, если Quickhull недостаточно хорош, - это cudahull, если вам нужны точные решения. Хотя даже тогда вы получите только 40-кратное увеличение (кажется).

Я предполагаю, что каждая выпуклая оболочка, которую вы создаете, имеет не менее 10 вершин (если их намного меньше, вы мало что можете сделать). Если вы не против "достаточно близких" решений. Вы можете создать версию quickhull, которая ограничивает количество вершин на многоугольник. Количество вершин, которым вы ограничиваете вычисление, также позволит при необходимости вычислить максимальную ошибку.

Дело в том, что по мере того, как число вершин выпуклой оболочки приближается к бесконечности, вы получаете сферу. Это означает, что из-за того, как работает быстрый корпус, каждая дополнительная вершина, которую вы добавляете к выпуклой оболочке, имеет меньший эффект *, чем предыдущие.

* В зависимости от того, как кодируется quickhull, это может быть правдой только в общем смысле. Чтобы реализовать это на практике, потребуется изменить алгоритм рекурсии Quickhull, поэтому, хотя «следующая вершина» всегда вычисляется (кроме случаев, когда добавляется последняя вершина или для этого участка не остается точек), вершины фактически добавляются к выпуклой оболочке в порядок, который максимизирует увеличение объема многогранников (вероятно, в порядке от наиболее удаленного до наименее удаленного). Вы понесете некоторую стоимость производительности для отслеживания порядка добавления вершин, но пока соотношение ожидающих выпуклых точек корпуса и ожидающих точек достаточно велико, оно того стоит. Что касается ошибки, то лучшим вариантом, вероятно, является остановка алгоритма либо когда будет достигнута фактическая выпуклая оболочка, либо когда максимальное увеличение объема станет меньше определенной части текущего общего объема. Если производительность важнее, просто ограничьте количество точек выпуклой оболочки на многоугольник.

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

person Nuclearman    schedule 07.01.2013

arrow_upward
0
arrow_downward

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

[k,volume] = convhulln(P);
centroid = mean(P(k,:));
person Jonas    schedule 06.01.2013