Công thức chung để tính khối lượng đa diện

Question

Cho danh sách các đỉnh (v) và danh sách các cạnh nối các đỉnh (e) và danh sách các bề mặt kết nối các cạnh (s), cách tính thể tích của Polyhedron?

Answer 1

1. Chụp các đa giác và chia chúng thành hình tam giác.
2. Hãy xem xét tứ diện được hình thành bởi mỗi tam giác và một điểm tùy ý (nguồn gốc).
3. Tổng khối lượng đã ký của các tứ diện này.

Ghi chú:

1. này sẽ chỉ làm việc nếu bạn có thể giữ một CC phù hợp hoặc lệnh CCW để hình tam giác như nhìn từ bên ngoài.
2. Khối lượng ký của tứ diện bằng 1/6 yếu tố quyết định của ma trận sau:

[x1 x2 x3 x4]
[y1 y2 y3 y4]
[z1 z2 z3 z4]
[1 1 1 1]

trong đó các cột là tọa độ đồng nhất của các đỉnh (x, y, z, 1).

Nó hoạt động ngay cả khi hình dạng không kèm theo nguồn gốc bằng cách giảm bớt khối lượng đó cũng như thêm nó vào, nhưng điều đó phụ thuộc vào việc có thứ tự nhất quán.

Nếu bạn không thể giữ nguyên thứ tự, bạn vẫn có thể tìm thấy cách nào đó để chia nó thành tứ diện và tính tổng giá trị tuyệt đối của yếu tố quyết định của mỗi số.

Answer 2

Tương tự với đa giác nơi chúng tôi có thể chia thành hình tam giác và tổng hợp các khu vực,
bạn có thể chia đa hình thành các hình kim tự tháp và tổng khối lượng của chúng. Nhưng tôi không chắc làm thế nào khó để thực hiện một thuật toán cho điều đó.

(Tôi tin rằng có một cách toán học/công thức, như sử dụng vectơ và ma trận.
Tôi đề nghị để gửi câu hỏi của bạn cũng trên http://mathoverflow.net)

Answer 3

Đầu tiên, phá vỡ mọi khuôn mặt vào hình tam giác bằng cách vẽ ở cạnh mới.

Bây giờ hãy nhìn vào một hình tam giác và giả sử nó nằm trên bề mặt "phía trên" (một số chi tiết này sẽ trở thành không quan trọng sau). Nhìn vào âm lượng bên dưới hình tam giác, xuống một số mặt phẳng nằm ngang bên dưới giá treo. Nếu {h1, h2, h3} là chiều cao của ba điểm, và A là diện tích của đế, thì thể tích của chất rắn sẽ là A (h1 + h2 + h3)/3. Bây giờ chúng ta phải thêm khối lượng của các chất rắn này cho các mặt phía trên và trừ chúng cho các mặt thấp hơn để nhận âm lượng của giá treo.

Chơi với đại số và bạn sẽ thấy rằng chiều cao của đa diện trên mặt phẳng ngang không quan trọng. Mặt phẳng có thể nằm phía trên đa giác, hoặc đi qua nó, và kết quả sẽ vẫn chính xác. Vì vậy, những gì chúng tôi cần là (1) một cách để tính toán diện tích của cơ sở, và (2) một cách để nói một khuôn mặt "trên" từ một "thấp hơn" một trong những. Việc đầu tiên là dễ dàng nếu bạn có tọa độ Descartes của các điểm, thứ hai là dễ dàng nếu các điểm được đặt hàng, và bạn có thể kết hợp chúng và giết hai con chim với một viên đá. Giả sử cho mỗi dace bạn có một danh sách các góc của nó, theo thứ tự ngược chiều kim đồng hồ. Sau đó, phép chiếu của các điểm trên mặt phẳng x-y sẽ ngược chiều kim đồng hồ đối với mặt trên và chiều kim đồng hồ cho điểm thấp hơn. Nếu bạn sử dụng this method để tính diện tích cơ sở, nó sẽ xuất hiện tích cực cho mặt trên và âm cho mặt dưới, vì vậy bạn có thể thêm tất cả lại với nhau và có câu trả lời.

Vậy làm cách nào để bạn có được danh sách các góc được sắp xếp? Bắt đầu với một hình tam giác, chọn một thứ tự, và đối với mỗi cạnh mà hàng xóm chia sẻ cạnh đó sẽ liệt kê hai điểm đó theo thứ tự ngược lại. Di chuyển từ hàng xóm đến hàng xóm cho đến khi bạn có một danh sách cho mỗi tam giác. Nếu âm lượng của đa diện đi lên âm, chỉ nhân với -1 (có nghĩa là bạn đã chọn sai thứ tự cho tam giác đầu tiên đó, và đa diện nằm trong-ngoài).

EDIT: Tôi quên phần tốt nhất! Nếu bạn kiểm tra đại số để thêm các tập này, bạn sẽ thấy rằng rất nhiều thuật ngữ hủy bỏ, đặc biệt là khi kết hợp các hình tam giác trở lại các khuôn mặt ban đầu. Tôi đã không làm việc này một cách chi tiết, nhưng có vẻ như kết quả cuối cùng có thể là một chức năng đơn giản đáng kinh ngạc.

Answer 4

Tôi đã làm điều này trước đây, nhưng lưới bề mặt tôi đã sử dụng luôn có các mặt hình tam giác. Nếu lưới của bạn có các khía cạnh không hình tam giác, bạn có thể dễ dàng chia chúng thành các cạnh hình tam giác trước tiên. Sau đó, tôi cho nó ăn TetGen để có được một tứ diện của nội thất. Cuối cùng, tôi cộng tất cả các khối tứ diện. TetGen là hợp lý dễ sử dụng, và là thư viện duy nhất khác hơn CGAL Tôi biết rằng có thể xử lý các mắt lưới phức tạp. CGAL là khá dễ sử dụng nếu bạn không nhớ cài đặt một thư viện khổng lồ và sử dụng các mẫu như điên.

Answer 5

Đây là triển khai tiềm năng cho điều đó trong Python. Có ai vui lòng kiểm tra xem nó có chính xác không? Tôi tin rằng tôi thiếu hoán vị của các điểm vì thử nghiệm thứ hai của tôi (khối lập phương) cho 0.666 và không 1. Ý tưởng bất cứ ai?

Cheers 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()