Punkte verbinden

Tiny-Toon

Hallo,

ich habe folgendes Problem.

Ich generiere mir ein "Punktewolke", um an einem 3D-Objekt eine Epotentiallinie anzuzeigen.
Dazu lese ich alle Werte aus, die einer bestimmten Höhe entsprechen.

Diese sieht in etwa so aus:

http://www.imgbox.de/users/public/thumbnails/r39336c127_t.gif

Nun möchte ich diese Punkte so verbinden, dass sich zwei Formen ergeben(also im Prinzip so, als würde man die Punkte von Hand verbinden).

Nur habe ich leider keine Ahnung, wie ich das angehen könnte, zumal die einzelnen Abstände nicht wie beispielsweise in einem Gitternetz feste Werte haben, sondern durchaus Lücken enstehen, oder zwei Punkte dichter aneinander liegen könnten.

mfg

volkard

Einfach bei einem beliebigen Punkt anfangen und immer mit dem nächsten (am dichtesten dranliegenden anderen) Punkt verbinden? Solange es noch freie Punkte gibt, neuen Kreis anfangen.

rapso

jeden punkt mit jedem verbinden
der laenge nach absteigend sortieren
liste durchgehen und jede verbindung entfernen falls die endpunkt noch >2 verbindungen haben

man kann das einfach um andere kostenfunktionen und entfernungsbedingungen ergaenzen.

Tiny-Toon

Moin,

vielen Dank für die Antworten.
Ich kam heute erst dazu, an dem Projekt weiter zu arbeiten.

jeden punkt mit jedem verbinden
der laenge nach absteigend sortieren
liste durchgehen und jede verbindung entfernen falls die endpunkt noch >2 verbindungen haben

Den dritten Punkt verstehe ich nicht. Könntest du das bitte näher erläutern?

Vielen Dank.

rapso

Tiny-Toon schrieb:

jeden punkt mit jedem verbinden
der laenge nach absteigend sortieren
liste durchgehen und jede verbindung entfernen falls die endpunkt noch >2 verbindungen haben

Den dritten Punkt verstehe ich nicht. Könntest du das bitte näher erläutern?

wenn du n punkte jeden mit jedem verbindest, gibt es fuer jeden punkt n-1 verbindungen.
diese hast du in der sortierten liste die du von der laengsten bis zur kuerzesten durchgehst. beim durchgehen pruefst du nun fuer beide eckpunkte der verbindung, ob sie noch mindestens 2 verbindungen uebrig haben, falls du die momentane entfernst (jeder punkt sollte am ende 2 verbindungen haben um geschlossene koerper zu erhalten).
ich hoffe das ist jetzt ein wenig besser erklaert

TGGC

Das sind allerdings Naeherungsverfahren, die sich irren koennen. Ohne nochnmal auf die Ausgangsdaten zurueckzugreifen kann man keine korrekte Loesung garantieren. Wenn man die Verbindungen direkt erkennt, duerfte das auch effizienter sein. f'`8k

Autocogito

Gruß, TGGC (Was Gamestar sagt...)

Wie generierst du die Punktewolke?

Gast25250

Hallo, eine Lösung für ein Problem sind alphashapes

http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html

http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

d.h.

1.) Du Delaunay-Triangulierst deine Punktewolke
2.) Du löscht alle Dreieck die eine Seite > alpha haben

Gruss, Jochen

Tiny-Toon

Hi,

@TravisG: Ich lese mein Objekt als Graustufen-Bitmap ein. Aufgrund der Grauwerte jedes Pixels kann ich dann die Höhe in der z-Achse bestimmen.
(schwarz= 0 ...... weiß=255)
Alle Pixel, die nun eine bestimmte Höhe kreuzen werden gesammelt, und danach nochmal gefiltert. So bekomme ich die auf Punktewolke, wie auf dem Bild im ersten Post.

@Gast25250: Danke für die Links, ich hoffe, dass ich damit weiter komme.

mfg

TGGC

Du kannst einen Pixelumriss von deinem "Plateau" erzeugen indem du alle Pixel suchst, die ueber der Hoehe x liegen und einen Nachbar (je nachdem wies sein soll - 4er/ 8er Nachbahrschaft) haben mit Hoehe unter x. f'`8k

Autocogito

Gruß, TGGC (Was Gamestar sagt...)

hellihjb

Wenn die Daten sowieso aus einem Bild (Grid) stammen, bietet es sich vielleicht an den Umriss per Marching Squares zu erzeugen.
Der Vorteil ist, dass Du so nicht einzelne Punkte sondern Kanten erzeugst.
Zusammenhaengende Kanten bilden dann ein Polygon das ggf noch in konvexe Teilpolygone zerlegt werden muss.