多面体体積を計算する一般式

Question

頂点のリスト（v）と、頂点を接続する辺のリスト（e）と、辺を接続するサーフェスのリスト（s）が与えられている場合、多面体？

Answer 1

1. ポリゴンを取り、三角形に分割します。
2. 各三角形と任意の点（原点）とによって形成される四面体を考える。
3. これらの四面体の符号付きボリュームを合計します。

注：

1. あなたが外から見て三角形に一貫CCまたはCCWの順序を保つことができる場合にのみ動作します。
2. 面体の署名された体積は、以下の行列の行列1/6に等しい：

[×1×2×3×4]
[Y1、Y2、Y3、Y4]
[Z1 Z2 Z3 Z4]

ここで、列は、頂点（x、y、z、1）の同次座標である。

シェイプが原点を囲んでいないにもかかわらず、そのボリュームを削除して追加しても、一貫した並べ替えが必要な場合でも機能します。

あなたが順序を保持できない場合は、それを四面体に分解し、それぞれの行列式の1/6絶対値を合計する何らかの方法を見つけることができます。

Answer 2

ポリゴンと同様に、三角形に分割して領域を合計することができます。
多面体をピラミッドに分割してボリュームを合計することができます。しかし、そのアルゴリズムを実装するのがどれほど難しいかはわかりません。

（私はベクトルや行列を使用してのように、数学的な方法/公式があると考えています。
私はhttp://mathoverflow.netにも質問を投稿することをお勧め）

Answer 3

まず、新しいエッジに描画することによって三角形にすべての顔を破ります。

は今1つの三角形を見て、それが（これらの詳細のいくつかは、後に重要でないことが判明するだろう）「上」表面上にあると仮定します。三角形の下の容積を見て、ポーロヘドロンの下の水平面にします。 {h1、h2、h3}が3点の高さであり、Aが底辺の面積である場合、ソリッドの体積はA（h1 + h2 + h3）/ 3になります。今、私たちは上位顔のためにこれらの固体のボリュームを追加し、poyhedronのボリュームを取得するために下顔のためにそれらを減算する必要があります。

は代数と遊ぶ、あなたは、水平面上の多面体の高さは関係ないことがわかります。平面は多面体の上にあるか、またはそれを通過することができ、その結果は正しいでしょう。

だから我々は必要なもののベースの面積を計算するために、（1）の方法である、と（2）の方法「下」1から「上位」の顔を伝えるために。最初の点は点のデカルト座標があれば簡単で、2番目の点は点が順序付けされていれば簡単ですし、それらを組み合わせて1つの石で2羽の鳥を殺すことができます。それぞれのdaceに対して、反時計回りの順序でそのコーナーのリストがあるとします。次に、これらの点のx-y平面上での投影は、上面に対しては反時計回りであり、下面に対しては時計回りである。 this methodを使って基底の面積を計算すると、上の方が正、下の方が負となるので、それらをすべて一緒に追加して答えます。

どのようにコーナーの注文リストを取得しますか？ 1つの三角形で始まり、順序を選択し、各エッジに対して、そのエッジを共有するネイバーは、その2つのポイントを逆の順序でリストする必要があります。あなたはすべての三角形のリストがあるまで、隣人から隣人に移動します。多面体の体積が負になる場合は、-1を掛けます（最初の三角形の順序が正しくないことを意味し、多面体は内側にあります）。

編集： 私は最高の部分を忘れました！これらのボリュームを積算する代数をチェックすると、特に三角形を元の面に戻したときに、多くの用語が相殺されることがわかります。私はこれを詳細には研究していませんが、最終結果が驚くほど単純な機能であるかのように見えます。

Answer 4

私は以前これを行っていましたが、私が使ったサーフェスメッシュには常に三角形の面がありました。メッシュに非三角形のファセットがある場合は、最初にそれらを三角形のファセットに簡単に分割できます。それから私はTetGenにそれを供給して、内部の四面体化を得た。最後に、私は四面体のすべてのボリュームを追加しました。 TetGenは、使用するのがかなり簡単で、CGAL以外の唯一のライブラリであり、複雑なメッシュを扱うことができます。 CGALは、巨大なライブラリをインストールするのを気にせず、狂ったようなテンプレートを使用しても大丈夫です。

Answer 5

これは、Pythonの潜在的な実装です。 誰でも正しいことを確認できますか？ 2番目のテスト（立方体）が0.666で、1でないので、ポイントの順列が欠けていると思います。

乾杯 EL

class Simplex(object): 
    ''' 
    Simplex 
    ''' 


    def __init__(self,coordinates): 
     ''' 
     Constructor 
     ''' 

     if not len(coordinates) == 4: 
      raise RuntimeError('You must provide only 4 coordinates!') 

     self.coordinates = coordinates 



    def volume(self): 
     ''' 
     volume: Return volume of simplex. Formula from http://de.wikipedia.org/wiki/Tetraeder 
     ''' 
     import numpy 

     vA = numpy.array(self.coordinates[1]) - numpy.array(self.coordinates[0]) 
     vB = numpy.array(self.coordinates[2]) - numpy.array(self.coordinates[0]) 
     vC = numpy.array(self.coordinates[3]) - numpy.array(self.coordinates[0]) 

     return numpy.abs(numpy.dot(numpy.cross(vA,vB),vC))/6.0 


class Polyeder(object): 

    def __init__(self,coordinates): 
     ''' 
     Constructor 
     ''' 

     if len(coordinates) < 4: 
      raise RuntimeError('You must provide at least 4 coordinates!') 

     self.coordinates = coordinates 


    def volume(self): 

     pivotCoordinate = self.coordinates[0] 

     volumeSum = 0 

     for i in xrange(1,len(self.coordinates)-3): 

      newCoordinates = [pivotCoordinate] 

      for j in xrange(i,i+3): 
       newCoordinates.append(self.coordinates[j]) 

      simplex = Simplex(newCoordinates) 
      volumeSum += simplex.volume() 

     return volumeSum 


coords = [] 

coords.append([0,0,0]) 
coords.append([1,0,0]) 
coords.append([0,1,0]) 
coords.append([0,0,1]) 

s = Simplex(coords) 
print s.volume() 

coords.append([0,1,1]) 
coords.append([1,0,1]) 
coords.append([1,1,0]) 
coords.append([1,1,1]) 

p = Polyeder(coords) 
print p.volume()