Kreise im Raum ermitteln
-
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?
-
Kann man denn jetzt was damit anfangen?
-
Nein.
Es geht darum was bedeuten deine Normalen, die du bekommst?
Sie stehen ja auf irgendwas senkrecht. Auf was?
-
Mehr kann ich auch nicht darüber aussagen. Mehr liefert die Bibliothek auch nicht an Informationen. In PMI Daten steht sowas auch nicht drin oder?!
Die Normalen stehen auf jedem Punkt auf.*nu bin ich völlibg verwirrt*
-
Ich brauch doch aber auch die Funktionsgleichungen der Normalen in den Punkten. Nur die hab ich nicht. Es stehe wie gesagt nur die Normelenwerte zu jedem Punkt da. Um diese zu ermitteln brauch man ja auch nur den Punkt in die Funktionsgleichung einzusetzen. Und diese Funktionsgleichung ist mir nicht bekannt. Oder hab ich jetzt ein Denkfehler?
-
Im 3D Raum ist Ein Kreis Eindeutig bestimmt Durch 8 Kontrollpunkte. Mit dreien Geht es Einfach Nicht, Da eine Dimension Fehlt.
Ein Kreis Kann um Seine eigene Achse Gedreht Sein im 3D-Raum, wobei Dies im 2D-Raum Nicht Möglich ist. Um Dies zu Kompensieren Braucht man Mindestens n+2 Andere Punkte. Im 3D-Raum Ist n=3, Also Braucht man Mindestens 5 Weitere Punkte.
Um Es Klarer zu Formulieren. Im 2D-Raum Ist ein Kreis Bestimmt Durch 3 Punkte. Jedoch Nicht im 3D-Raum. Denn ein Kreis Ist Eigentlich ein 2D-Objekt. Wenn Dieses in den 3D-Raum eintaucht, Muss Die Ebene, in Der es Liegt, Mit Angegeben sein. Eine Ebene Braucht 4 Angaben. Die 8. Angabe Steckt In der Rotation Des Kreises um Seine eigene Achse.
Wenn Du Dies in C++ Umsetzt, Sehe Ich Keine Probleme bei der Umsetzung.
-
Wenn ich drei Punkte im 3D-Raum habe, dann liegen die in einer Ebene, ein Kreis, der diese drei Punkte enthalten soll muß also auch in dieser Ebene liegen. Ich bekomme also eine Ebene und drei Punkte, damit also einen eindeutigen Kreis. Mehr Punkte braucht's nicht.
Zu 4 Punkten findest Du im allgemeinen keinen Kreis mehr... wenn sie nicht koplanar sind.
Aber unabhängig davon sehe ich auch nicht, wie das bei der Umsetzung helfen sollte.
@Mister Wing: was für eine Funktionsgleichung?