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

11

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?

algorithms reference-request computational-geometry

— Victor Liu
źródło

Wiesz, że punkty są wierzchołkami wielościanu. Czy znasz twarze (wielokąty na kadłubie)? Jeśli tak, możesz dość łatwo obliczyć objętość (jako sumę objętości „stożkowych”).

— hardmath

1

Leniwym sposobem byłoby najpierw triangulacja, a następnie zsumowanie objętości czworościanów (bardzo łatwe do obliczenia).

— Shuhao Cao,

@hardmath: Nie. Wiem, że gdybym znał kształty faset, byłoby to łatwe.

— Victor Liu

@Shuhao Cao: Czy istnieje prosty algorytm triangulacji dla tego specjalnego przypadku? Generalnie algorytmy czworościanu 3D są dość skomplikowane i spodziewam się, że będę musiał rozwiązać ten problem tysiące lub miliony razy.

— Victor Liu

5

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ę nad wszystkimi możliwymi trójkątami, aby sprawdzić, czy są na kadłubie. Dla jest to wciąż dość szybkie i można łatwo wdrożyć skróty. Po uzyskaniu wszystkich powierzchni trójkąta wybierz jeden wierzchołek i utwórz czworościan z każdym trójkątem i . Jego objętość to $O(n^2)$ $n^4$ $n=15$ $v$ $T$ $v$ wyznacznik we współrzędnych wierzchołka. $4 \times 4$

— Joseph O'Rourke
źródło

2

Mały test w MATLAB, dla liczby wierzchołków , każdy składnik jest jednolitą liczbą losową w : $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$

konwulsja

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

time_elapse =
              3.244278
Vol =
     0.998068316875714

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

— Shuhao Cao
źródło

BTW test został przeprowadzony na moim starym Core 2 T61p 2007.

— Shuhao Cao,

2

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$

— matematyka
źródło