Delaunay triangularization of Polyhedron (Python)

Question

Я пытаюсь получить Delaunay Triangulation многогранника в python, чтобы вычислить центроид. Я вижу, что есть функция Delaunay в scipy.spatial и что она работает в n-измерениях. Беда в том, что документация показывает 2D-использование и не дает мне никаких указаний на то, что делать с более высокими измерениями. Возможность разложить этот объект в массив, вероятно, решит эту проблему для меня, но я не знаю, как это сделать.

Проблема, с которой я столкнулся, заключается в том, что я не знаю, как проверить правильность работы, поскольку она выводит объект. Я ничего не могу найти в Google о том, как графовать многогранник или как использовать этот объект, который scipy плюет назад.

Если я

import numpy as np 
from scipy.spatial import Delaunay 

points = np.array([[0,0,0],[1,0,0],[1,1,0],[1,0,1],[1,1,1],[0,1,0],[0,1,1],[0,0,1]]) 
Delaunay(points) 

Я действительно просто хотел бы быть в состоянии получить обратно координаты этих тетраэдров, так что я могу вычислить центроиды многогранников. Было бы также очень приятно, если бы мне удалось графически изобразить и тесселированный многогранник. Я видел в MATLAB, что я могу сделать это с помощью fuction, называемого trimesn, и я нашел его от matplotlib, но, похоже, он действительно отличается, и его документация невелика.

from matplotlib.collections import TriMesh TriMesh.__doc__ 

u'\n  Class for the efficient drawing of a triangular mesh using\n 
Gouraud shading.\n\n A triangular mesh is a 
:class:`~matplotlib.tri.Triangulation`\n object.\n ' 

Answer 1

Что возвращает tess = Delaunay(pts) является объектом класса Delanauy. Вы можете проверить тетраэдры как tess.simplices. Он имеет разные атрибуты и методы. Например, в 2D он может отображать триангуляцию, выпуклый корпус и конструкцию Вороного.

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

from __future__ import division 
import numpy as np 
from scipy.spatial import Delaunay 
import matplotlib.pyplot as plt 
from mpl_toolkits.mplot3d import Axes3D 
from mpl_toolkits.mplot3d.art3d import Poly3DCollection, Line3DCollection 
from itertools import combinations 


def plot_tetra(tetra, pts, color="green", alpha=0.1, lc="k", lw=1): 
    combs = combinations(tetra, 3) 
    for comb in combs: 
     X = pts[comb, 0] 
     Y = pts[comb, 1] 
     Z = pts[comb, 2] 
     verts = [zip(X, Y, Z)] 
     triangle = Poly3DCollection(verts, facecolors=color, alpha=0.1) 
     lines = Line3DCollection(verts, colors=lc, linewidths=lw) 
     ax.add_collection3d(triangle) 
     ax.add_collection3d(lines) 

pts = np.array([ 
      [0,0,0], 
      [1,0,0], 
      [1,1,0], 
      [1,0,1], 
      [1,1,1], 
      [0,1,0], 
      [0,1,1], 
      [0,0,1]]) 
tess = Delaunay(pts) 

fig = plt.figure() 
ax = fig.add_subplot(111, projection='3d') 
for k, tetra in enumerate(tess.simplices): 
    color = plt.cm.Accent(k/(tess.nsimplex - 1)) 
    plot_tetra(tetra, pts, color=color, alpha=0.1, lw=0.5, lc="k") 
ax.scatter(pts[:, 0], pts[:, 1], pts[:, 2], c='k') 
plt.savefig("Delaunay.png", dpi=600) 
plt.show() 

Полученное изображение

Answer 2

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

Вам не нужно разбивать многогранник на тетраэдры. Во-первых, триангулируйте грани многогранника, т. Е. Квадратики разбивают на два копланарных треугольника и т. Д. Затем выберите произвольную точку p в пространстве, скажем, начало координат. Теперь для каждой грани треугольника (a, b, c) вычислите подписанный объем тетраэдра (p, a, b, c). Это работает, если все треугольники ориентированы против часовой стрелки. Подписанный том заботится обо всем через отмену. Используйте громкость подписи как вес , чтобы умножить центроиды тетраэдров.

тетраэдров подписал объем объясняется в главе 1 моей книги, "Computational Geometry in C."