Kreise im Raum ermitteln
-
Mit einer Hough-Transformation lässt sich sowas schon machen. Du brauchst halt recht viele Parameter: Kreisebene: 3 Parameter, den Kreismittelpunkt: 2 Parameter und den Radius: 1 Parameter. Macht also insgesamt eine 6-dimensionale Lookup-Tabelle. Nicht gerade super attraktiv.
Dein Sweep-Line Verfahren ist mir völlig unklar. In welcher Richtung sweepst Du und was machst Du dabei genau? Eine Ebene durch den Raum schieben? Was machst Du wenn die Kreise senkrecht auf dieser Ebene stehen?
Mal davon abgesehen, ist Sweep-Line eine Beschleunigungstechnik. Das benutzt man gerne, um einen einfachen, aber funktionierenden Algorithmus zu verbessern. Ich würde Dir empfehlen erstmal einen einfachen polynomiellen Algorithmus zu finden und den anschließend möglicherweise dann mit Sweeping zu beschleunigen.
-
hm. ich hatte mal nen ähnliches problem.
gegeben war ein bild mit (vielen!)punkten darauf deren 3dimensionale entsprechung auf einen kreis lag.
lösungsansatz war methode der kleinsten quadrate mit dem ansatz für kegelschnitte.. (die zugehörige matrix wurde mit der svd bestimmt)mehr details weiß ich nich mehr. k.a. ob das hier was hilft..
-
@Jester Mir sind doch Kreisebene, Radius und Mittelpunkt nicht bekannt. Bei meinem SweepVerfahren würde ein Quader durch den Raum entlang der x-Achse gleiten. Ich betrachte doch nur Punkte in diesem Quader, ganz egal in welcher Lage diese sind, das finde ich dann durch Berechnung der linearen Abhängigkeit raus.
@xroads42 Schnittebenen sind mir ja auch nicht bekannt, ich wüsste nicht wo ich schneiden sollte mit dem Kegelschnitt.
-
Könntest du ein Bild von der Punktwolke irgendwo online stellen?
-
Mister Wing schrieb:
@Jester Mir sind doch Kreisebene, Radius und Mittelpunkt nicht bekannt.
Deswegen hast Du ja auch 6 Parameter, die eben durchsucht werden. Funktionieren würde das schon, aber schnell ist das Verfahren sicher nicht.
Und das Sweep-Verfahren funktioniert doch auch nicht richtig, oder? Stell Dir vor, Du nimmst erstmal aus Deinem Quader 4 Punkte, die gerade nicht auf dem Kreis liegen. Danach fütterst Du ein ums andere Mal die Punkte aus dem Kreis rein. Dein Abhängigkeitstest sagt Dir, dass die nicht in einer Ebene liegen, also wirfst Du ein um's andere Mal den Punkt vom Kreis wieder raus und findest am Schluß nichts.
Ich denke, wenn das ganze so allgemein bleibt sind die Chancen was effizientes zu finden nicht allzu hoch. Hast Du vielleicht stärkere Annahmen, die Du benutzten könntest?
-
Hallo,
hier ein Bild.
http://www.flickr.com/photos/29723497@N06/2777111879/
Ich bekomme die Punkte ohne topologische Informationen. Rein nur die Punkte. Nun möchte ich zum Beispiel Kreise ausfindig machen und darstellen. Anschliessend schmeisse ich dann diese Punkte raus und kann meine Menge reduzieren.
-
Ein Kreis ist doch durch 3 Punkte eindeutig bestimmt, oder?
Ab wie vielen Punkten geht denn bei deinem Problem ein Kreis
los?Ich würde versuchen den Raum entsprechend aufzuteilen in überschaubare
Teilräume (10 Punkte oder ähnliches).
In diesen Teilräumen durch den polynomialen Ansatz die Kreise bestimmen (also
jede Dreierkombination von Punkten, die in 1 Ebene liegen -> Kreis mit
Mittelpunkt + Radius [zum Quadrat]).
Danach verschmilzt eine Merge-Funktion immer wieder 2 Teilräume und auch deren
Kreise.Kreise, die nicht deinen Anforderungen entsprechen (bestehend aus zu wenig
Punkten, zu klein oder ähnliches), rauskicken aus deiner Datenstruktur.Als solche würde ich vielleicht eine Hash-Tabelle nehmen, wegen konstanten
Zugriff.
-
Das Problem ist doch, das ich keinen Kreis aus 3 Punkten konstruieren möchte, sondern schauen muss (meinetwegen bei 10 Punkten), welche in einer Ebene liegen, dann aus jeweils zwei von denen einen Mittelpunkt berechnen, und schauen welche Punkte noch auf dem Kreisbogen liegen. Diese Punkte schmeisse ich dann aus meiner zu untersuchenden Punktmenge raus. Die müssen ja nicht noch ein weiteres Mal geprüft werden.
Das hatte ich ja weiter oben bereits als Ansatz beschrieben.
-
Mister Wing schrieb:
Das Problem ist doch, das ich keinen Kreis aus 3 Punkten konstruieren möchte, sondern schauen muss (meinetwegen bei 10 Punkten), welche in einer Ebene liegen, dann aus jeweils zwei von denen einen Mittelpunkt berechnen, und schauen welche Punkte noch auf dem Kreisbogen liegen. Diese Punkte schmeisse ich dann aus meiner zu untersuchenden Punktmenge raus. Die müssen ja nicht noch ein weiteres Mal geprüft werden.
Mit anderen Worten: eine wesentliche Randbedingung ist, dass sich die gesuchten Kreise nicht schneiden können?
-
Ja, genau. Das ist eine Randbedingung. Diese dürfen sich nicht schneiden.
Sprich zwei Kreise bestehen aus disjunkten Mengen.
Hier noch mal mein Gebilde.
-
Dein obiger Ansatz funktioniert nicht auf beliebigen Punktmengen (oder ich habe ihn völlig falsch verstanden). Das hatte ich doch vorher auch beschrieben. Du mußt mehr Informationen über Deine Punktmenge verraten/ausnutzen.
-
Ich habe keine weiteren Informationen. Ich weiss zwar wie das Modell aussieht, die Daten die mir geliefert werden, bestehen jedoch nur aus Kanten und deren Normalen. Ich habe keinerlei Infos über die Toplogie. Mit den Normalen kann ich doch nix anfangen, da mir die Tangentenlängen fehlen. Oder liege ich da falsch?! Die Normalen geben mir doch keine Information wie ich die Punkte mit einander verbinden kann?!
geom set #0:
vertices = ( 1150.57, -152.249, -32.5767, 1150.42, -151.893, -32.6272, 1150.57, -151.901, -32.5872 )
normals = ( 0.246937, -0.0322172, -0.968496, 0.327183, 0.00511223, -0.944947, 0.23095, -0.0321239, -0.972435 )
geom set #1:
vertices = ( 1194.49, -644.385, -30.1644, 1194.46, -644.36, -30.1512, 1194.44, -644.432, -30.1582 )
normals = ( 0.309198, -0.150901, 0.938949, 0.308835, -0.151265, 0.93901, 0.286149, -0.174616, 0.94214 )So sehen meine Daten aus die ich bekomme. Wobei vertices(x,y,z,x,y,z,...) bedeutet. Ich möchte ein Drahtmodell erstellen. Dabei muss ich mir die Punkte holen und sie bearbeiten.
-
Mister Wing schrieb:
Die Normalen geben mir doch keine Information wie ich die Punkte mit einander verbinden kann?!
Das kommt auf Deine Modelle an. Wenn die zum Beispiel konvex sind, dann kannst Du mit Hilfe der Normalen immerhin ganze Halbräume ausschließen. Außerdem sind für einen Punkt x mit Normale n als Kandidaten Punkte, die nahe x sind und nahe der Ebene durch mit senkrecht auf n besonders interessant, wenn das modell nicht gerade scharfe Kanten hat.
Das könnte hier evtl schon ganz gut funktionieren.
edit: btw. scheinst du eine ganze menge mehr informationen zu haben... versuch mal genau rauszufinden, was du weißt.
-
Mit der Normale eines Punktes hast du doch schon 1 Bedingung wie die Kreisebene E auszusehen hat.
Desweiteren können nur noch Punkte zum Kreis gehören, deren Normale selbst auch
senkrecht zur Normale von E stehen.
-
Ich hab das jetzt so verstanden, dass das die Normale des Punktes im 3d-modell ist und nicht unbedingt die normale der Ebene, in der der Kreis liegt.
-
Dann gibts aber mehrere verschiedene Lösungen, bei ein und dem selben
Punktebild, wenn verschiedene Algorithmen daran arbeiten.Ich dachte diese Normale ist die Normale der Tangetialebene an diesem Punkt.
-
Chuck schrieb:
Ich dachte diese Normale ist die Normale der Tangetialebene an diesem Punkt.
Ja, und warum sollte dann der komplette Kreis dadrin liegen?
-
Was sind denn hier nun die Normalen des Punktes?
Sind das u und v? Aber was ist dann der dritte Parameter?
Diese Werte sind doch auch sicher normiert.geom set #0:
vertices = ( 1150.57, -152.249, -32.5767, 1150.42, -151.893, -32.6272, 1150.57, -151.901, -32.5872 )
normals = ( 0.246937, -0.0322172, -0.968496, 0.327183, 0.00511223, -0.944947, 0.23095, -0.0321239, -0.972435 )
geom set #1:
vertices = ( 1194.49, -644.385, -30.1644, 1194.46, -644.36, -30.1512, 1194.44, -644.432, -30.1582 )
normals = ( 0.309198, -0.150901, 0.938949, 0.308835, -0.151265, 0.93901, 0.286149, -0.174616, 0.94214 )Wie muss ich mir die Normalen an einem Punkt grafisch vorstellen?
-
Hier noch mal die genauen Daten die ich bekomme!
Description: Get a facetted geometry primitive definition from the shape, specified by index.
Outputs:
coord3vecs - An array of consecutive (x,y,z) vertice values. Memory is internally allocation, and should be deallocated by the user via "delete[]".numcoords - The number of vertices in the returned vertice array.
normal3vecs - An array of consecutive (x,y,z) normal values. Memory is internally allocation, and should be deallocated by the user via "delete[]".
numnorms - The number of normals in the returned normal array.
color3vecs - An array of consecutive (R,G,B) color values. Each value is in the range [0.0, 1.0]. Memory is internally allocation, and should be deallocated by the user via "delete[]".
numcolors - The number of colors in the returned color array.
texture2vecs - An array of consecutive (x,y) texture values. Memory is internally allocation, and should be deallocated by the user via "delete[]".
numTextCoords - The number of texture coordinates in the returned texture array
-
Das mußt schon Du uns sagen, was die bedeuten. Woran sollen denn wir das erkennen?