Objętość 3D wypukłego kadłuba małych zestawów punktów na kadłubie

Mam pytanie podobne do tego zadanego wcześniej, z wyjątkiem 3D, i potrzebuję tylko objętości, a nie faktycznego kształtu kadłuba.

Mówiąc dokładniej, otrzymałem mały zestaw punktów (powiedzmy 10-15) w 3D, z których wszystkie leżą na wypukłym kadłubie zestawu punktów (więc wszystkie one „mają znaczenie” i definiują kadłub). Chcę tylko obliczyć objętość kadłuba, nie dbam o obliczenie rzeczywistego wielościanu. Czy istnieje skuteczny algorytm do tego celu?

Byłbym zaskoczony, jeśli potrafisz pokonać sugestię Shuhao Cao: obliczyć kadłub, a następnie głośność, gdy tylko triangulacja kadłuba. Można obliczyć kadłub za pomocą algorytmu przyrostowego lub algorytmu pakowania prezentów. Jeśli naprawdę chcesz łatwego kodu, możesz po prostu napisać pętlę n 4 nad wszystkimi możliwymi trójkątami, aby sprawdzić, czy są na kadłubie. Dla n = 15 jest to wciąż dość szybkie i można łatwo wdrożyć skróty. Po uzyskaniu wszystkich powierzchni trójkąta wybierz jeden wierzchołek v i utwórz czworościan z każdym trójkątem T i v . Jego objętość to 4 $O(n^2)$$n^4$$n=15$$v$$T$$v$ wyznacznik we współrzędnych wierzchołka.$4 \times 4$

Mały test w MATLAB, dla liczby wierzchołków , każdy składnik jest jednolitą liczbą losową w [ 0 , 1 ] :$N = 100$$[0,1]$

N = 100;
p=rand(N,3);
tic;
T = delaunayTri(p(:,1),p(:,2),p(:,3));
t = T.Triangulation;
e1 = p(t(:,2),:)-p(t(:,1),:);
e2 = p(t(:,3),:)-p(t(:,1),:);
e3 = p(t(:,4),:)-p(t(:,1),:);
V = abs(dot(cross(e1,e2,2),e3,2))/6;
Vol = sum(V);
time_elapse = toc;

Wynik:

time_elapse =
              0.014807
Vol =
      0.67880219135839

Powiedziałbym, że jest dość szybki, jeśli chcesz uruchomić go razy, zajmuje to mniej niż 3 godziny. Oto jak to jest:$10^6$

$4\times 4$$N=10^5$

time_elapse =
              3.244278
Vol =
     0.998068316875714

$\approx 7\times 10^5$$1$$[0,1]^3$

Z FAQ obliczeń wielościennych obliczeń Komei Fukudy :

$R^d$

Wiadomo, że obliczenie objętości V-politopu (lub H-politopu) jest twardością # P, patrz [DF88] i [Kha93]. Istnieją teoretycznie wydajne algorytmy randomizowane do przybliżania objętości ciała wypukłego [LS93], ale wydaje się, że żadna implementacja nie jest dostępna. Istnieje badanie porównawcze [BEF00] różnych algorytmów obliczania objętości wypukłych polytopów. Wskazuje to, że nie ma jednego algorytmu, który działałby dobrze dla wielu różnych rodzajów polytopów.

[DF88] ME Dyer i AM Frieze. Złożoność obliczania objętości wielościanu. SIAM J. Comput. , 17: 967-974, 1988.

[Kha93] LG Khachiyan. Złożoność obliczania objętości polytopów. W J. Pach, redaktor, New Trends in Discrete and Computational Geometry , strony 91-101. Springer Verlag, Berlin, 1993.

[LS93] L. Lovasz i M. Simonovits. Losowe spacery w wypukłym ciele i ulepszony algorytm głośności. Losowe struktury i algorytmy , 4: 359-412, 1993.

[BEF00] B. Bueler, A. Enge i K. Fukuda. Dokładne obliczanie objętości wypukłych polytopów: praktyczne badanie. W G. Kalai i GM Ziegler, redaktorzy, Polytopes - Combinatorics and Computation , DMV-Seminar 29, strony 131-154. Birkhauser, 2000.

Może to wydawać się zakrywać specyfikę problemu 3D wśród trudności wyższych wymiarów, pomimo tytułu papieru Dyer and Frieze. Z ich streszczenia: „Pokazujemy, że obliczenie objętości wielościanu podanego albo jako listę aspektów, albo jako listę wierzchołków jest tak trudne, jak obliczenie stałej macierzy”.

$P$$P$$N_v$$v$$P$$P$$P$$P = \{x \in \mathbb{R}^3 : Ax \le b \}$

$P$