Voronoi Zerlegung mit Volumenberechnung

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

toby997

Forum-Newbie


	Beiträge: 1

	Anmeldedatum: 04.09.17

	Wohnort: ---

	Version: ---

Verfasst am: 04.09.2017, 18:21 Titel: Voronoi Zerlegung mit Volumenberechnung

Hallo zusammen,

ich sitze seit längerer Zeit an einem Problem, für das ich leider bis heute keine Lösung finden kann und daher wäre ich um jeden Tipp/Hinweis dankbar.
Und zwar möchte ich für eine große Menge an 3D Datenpunkten, die innerhalb der Einheitskugel liegen eine Voronoi/Dirichlet Zerlegung vornehmen und anschließend das Volumen jeder Zelle berechnen. Hierfür habe ich in der Vergangenheit bereits ein paar Zeilen Code getippt, welcher auch tadellos funktioniert hat.
Der Ausgangspunkt ist eine Nx3 Matrix mit je 200k x,y und z Koordinaten. Diese Punkte werden dann auf Eindeutigkeit geprüft und ggf. gelöscht.
Anschließend wird die Voronoi-Zerlegung und danach das Volumen einer jeden Zelle berechnet.

Code:

% X is the set of 3d points with dimension Nx3
[C, ia, ic] = unique(X,'rows'); % All non unique points are removed
B = 1:size(X,1);
missingvalues = setdiff(B,ia);
[Y,PS] = removerows(X,'ind', missingvalues);
volume = zeros(1,size(Y,1));
tic
[V,C] = voronoin(Y, {'Qbb'}); % Calculate Tessellation
toc
V(~isfinite(V)) = 0;
tic
for j=1:length(C)
X2 = [V(C{j},1) V(C{j},2) V(C{j},3)];
[K, V2] = convhulln(X2);
volume(j) = V2;
end
toc
end

Funktion ohne Link?

Die 200k Koordinaten in X sind dabei zufällig aus einer größeren Menge Y mittels

Code:

US_Pts = 200000;
Sze = size(Y,1)
p = randperm(Sze);
for i = 1:US_Pts
US(i) = p(i);
end
X = Y(US,:);

Funktion ohne Link?

ausgewählt worden.
Lasse ich statt 200k nur 100k Koordinaten auswählen, dann läuft der Code in 90 % der Fälle durch. Bei 200k crashed es auf jeden Fall immer mit der Meldung:

Code:

Error using cgprechecks (line 40)
Not enough unique points specified.
Error in convhulln (line 41)
cgprechecks(x, nargin, cg_opt);

Funktion ohne Link?

Der Code crashed dabei IMMER beim LETZTEN Schleifendurchgang, egal wie die Koordinaten in X sortiert werden. Das Programm lief bisher für deutlich größere quasi-zufällige Koordinatensätze problemlos durch und lieferte korrekte Volumina. Der aktuell verwendete Datensatz hat keinen quasi-random Seed mehr, allerdings sind die Punkte nach wie vor unique. Ein Beispiel für X, bei welchem es crashed habe ich unten angehängt.
Ein Test mit mehreren Matlab Versionen auf mehreren Rechnern hat bereits keinen Erfolg erzielt. Ein Beispiel für X habe ich angehängt.

Über jeden Hinweis wäre ich wahnsinnig dankbar!

X.mat

Beschreibung:

Download

Dateiname:

X.mat

Dateigröße:

4.39 MB

Heruntergeladen:

431 mal

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 16.09.2017, 18:19 Titel: Re: Voronoi Zerlegung mit Volumenberechnung

Hallo toby997,

Ich habe ein wenig herum gebastelt, verstehe aber nicht genau, was Du machst.
Du hast eine Matrix X mit 200000 Zeilen gepostet.
Welche Rolle spielt dann Y?

Nebenbei kannst Du den Code zum Auswählen von X deutlich vereinachen:

Code:

Index = randperm(size(Y, 1), 200000);
X = Y(Index, :);

Funktion ohne Link?

Die Zeilen

Code:

Funktion ohne Link?

wären so deutlich einfacher:

Code:

Y = unique(X, 'rows', 'stable');

Funktion ohne Link?

Oder?

Wenn ich den Rest des Codes mit aktiviertem dbstop if error laufen lasse, ist zu sehen, dass die letzten beiden Elemente von C leer sind. Dann ist:

Code:

X2 = [V(C{j},1) V(C{j},2) V(C{j},3)];

Funktion ohne Link?

ebenfalls die leer Matrix und convhull scheitert mit der zu erwartenden Fehlermeldung.

Zitat:

Der Code crashed dabei IMMER beim LETZTEN Schleifendurchgang, egal wie die Koordinaten in X sortiert werden.

Mit den von Dir geposteten Werten läuft er bis zur VORLETZTEN Iteration. Die letzte würde aber auch scheitern.

Wie wäre dies:

Code:

Y = unique(X, 'rows', 'stable');
volume = nan(1,size(Y,1));
[V, C] = voronoin(Y, {'Qbb'}); % Calculate Tessellation
V(~isfinite(V)) = 0;
for j = 1:numel(C)
if ~isempty(C{j})
[K, volume(j)] = convhulln(V(C{j}, :));
end
end

Funktion ohne Link?

Dann sind die Volumina mit leerem C auf NaN gesetzt.

Gruß, Jan


Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.