Calcolo del centroide e del volume di un poliedro quando i vertici sono dati

Question

Data la posizione dei vertici di un poliedro convesso (3D), ho bisogno di calcolare il centroide e il volume del poliedro. Il seguente codice è disponibile allo Mathworks site.

function C = centroid(P) 
k=convhulln(P); 
if length(unique(k(:)))<size(P,1) 
    error('Polyhedron is not convex.'); 
end 
T = delaunayn(P); 
n = size(T,1); 
W = zeros(n,1); 
C=0; 
for m = 1:n 
    sp = P(T(m,:),:); 
    [null,W(m)]=convhulln(sp); 
    C = C + W(m) * mean(sp); 
end 
C=C./sum(W); 
return 
end 

Il codice è elegante ma è terribilmente lento. Ho bisogno di calcolare il volume e il centroide di migliaia di poliedri centinaia di volte. L'uso di questo codice nel suo stato attuale non è fattibile. Qualcuno sa un approccio migliore o questo codice può essere reso più veloce? Ci sono alcuni piccoli cambiamenti che posso pensare ad esempio, sostituendo mean con espressione per media.

Answer 1

Quanto è possibile velocizzare il codice dipende molto da come si desidera calcolare il centroide. Vedi this answer about centroid calculation per le tue opzioni. Si scopre che se hai bisogno del centroide del poliedro solido, sei praticamente sfortunato. Se, tuttavia, solo i vertici del poliedro hanno un peso, allora si potrebbe scrivere semplicemente

[k,volume] = convhulln(P); 
centroid = mean(P(k,:)); 

Answer 2

Pensando l'unica opzione se quickhull non è abbastanza buono è cudahull se si desidera soluzioni esatte. Anche se, anche in questo caso, otterrai solo un aumento massimo di 40x (sembra).

Suppongo che gli scafi convessi di ognuno di essi abbiano almeno 10 vertici (se è molto inferiore, non c'è molto che si possa fare). Se non ti dispiace soluzioni "abbastanza vicine". Potresti creare una versione di quickhull che limiti il ​​numero di vertici per poligono. Il numero di vertici a cui si limita il calcolo consentirà anche il calcolo dell'errore massimo, se necessario.

Il fatto è che quando il numero di vertici sullo scafo convesso si avvicina all'infinito, si finisce con una sfera. Ciò significa che a causa del modo in cui lo scafo veloce funziona, ogni vertice aggiuntivo che aggiungi allo scafo convesso ha meno effetto * di quelli precedenti.

* A seconda di come quickhull è codificato, questo può essere vero solo in senso generale. Realizzare ciò in pratica richiederebbe la modifica dell'algoritmo di ricognizione di Quickhull, così mentre il "prossimo vertice" è sempre calcolato (eccetto che dopo l'ultimo vertice è stato aggiunto, o nessun punto rimane per quella sezione), i vertici vengono effettivamente aggiunti allo scafo convesso in l'ordine che massimizza l'aumento del volume dei poliedri (probabilmente per ordine di distanza maggiore o minore). Avrai dei costi di performance per tenere traccia dell'ordine per aggiungere i vertici, ma finché il rapporto tra punti scafo convessi in sospeso e punti in sospeso è abbastanza alto, dovrebbe valerne la pena. Per quanto riguarda l'errore, l'opzione migliore è probabilmente quella di arrestare l'algoritmo quando viene raggiunto lo scafo convesso effettivo, oppure l'aumento massimo del volume diventa minore di una certa frazione del volume totale corrente. Se le prestazioni sono più importanti, limita semplicemente il numero di punti scafo convessi per poligono.

Si potrebbe anche osservare i vari algoritmi approssimativi di scafo convesso, ma il metodo descritto sopra dovrebbe funzionare bene per l'approssimazione volume/centroide con la capacità di determinare l'errore.

Answer 3

C'è un approccio molto più semplice per calcolare il volume con il minimo sforzo. Il primo aroma utilizza 3 insiemi di informazioni topologiche locali del poliedro, il vettore di unità tangente dei bordi, i vettori unitari del piano piano normale su questa tangente e il vettore unitario della faccetta stessa (che sono molto semplici da estrarre dal vertici). Si prega di fare riferimento a Volume of a Polyhedron per ulteriori dettagli.

Il secondo aroma utilizza le aree del viso, i vettori normali e i barilotti del viso per calcolare il volume del poliedro in base a questo Wikipedia Article. Entrambi gli algoritmi sono piuttosto semplici e molto facili da implementare e attraverso la semplice struttura di sommatoria facile da vectorizzare. Suppongo che entrambi gli approcci saranno molto più veloci di una vera e propria tesselation del poliedro.

Il centroide del poliedro può quindi essere calcolato applicando il teorema di divergenza che trasferisce l'integrazione sul volume del poliedro completo in un'integrazione sulla superficie del poliedro. Una descrizione dettagliata può essere trovata in Calculating the volume and centroid of a polyhedron in 3d. Non ho verificato se la tassellatura del poliedro in triangoli sia realmente necessaria o si possa lavorare anche con le superfici poligonali più complesse del poliedro, ma in ogni caso la tassellatura dell'area delle facce è molto più semplice della tassellazione del volume. In totale, un simile approccio combinato dovrebbe essere molto più rapido dell'approccio basato sul volume.