Berechnung nächst gelegener Punkte

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo
für die Erzeugung eines Gitters aus Dreiecken habe ich folgendes Problem: Ich habe verschiedene Punkte mit Koordinaten X,Y (und Z)

Wenn ich ein Bsp. aus 5 Punkten annehme mit verschiedenen Koordinaten, wie kann man über die nächstgelegenen Punkte ein sauberes Dreiecksnetz legen. Gibt es dafür einen logischen Zusammenhang bzw. ein Berechnungsverfahren?

Ich hätte den Ansatz so gewählt, das man zunächst eine allgemeine Lösung aufstellen würde, wo diese Punkte ein Dreiecksnetz erzeugen
nach dem Kriterium Suche nächster Punkte.

Später würde ich das Kriterium erweitern wollen, nämlich dahingehend, das die Höhe der Punkte einbezogen werden soll.
Wenn man eine Mauer mit UK und OK annimmt, sind an jeder Ecke 2 Punkte seh nahe beieinander. Die Bruchkante bilden aber die Einzelpunkte der UK und OK. Zwischen diesen Punkten dürfen ja keine falschen Verbindungen erzeugt werden.

Man könnte auch zunächst Vierecke erzeugen und diese dann später teilen. Je nachdem wie es am besten ist, die Punkte logisch zu verknüpfen.

Kann mir jmd helfen, hat einen Lösungsansatz oder ein Programmfragment.
Am besten in VB6.

Als Bsp. kann man sich ja mal 5 Punkte hernehmen:

X Y Z
0 0 0
10 10 10
4 6 3
1 1 5
-2 4 8

Kann mir dazu jmd was sagen???

Mfg Werner

#2

nächste® Nachbar(n)-Pixel
hallo,
habe dieselbe Aufgabe - in Java, allerdings und lange her und wahrscheinlich ziemlich umständlich (vielöleicht ist es auch prinzipiell umständlich?) - so gelöst:

o zunächst braucht man von den vorhandenen Punkten (zB aus einem zweidimensionalen array mit den Koordinaten der Punkte) einen (ersten) Ausgangspunkt
o dieser wird nun mit allen anderen Punkten daraufhin verglichen (alle anderen Punkte daraufhin ‚gescannt‘), wie ‚weit‘ sie vom Ausgangspunkt ‚entfernt‘ sind
o ‚wie weit entfernt‘ ist die Länge der Diagonalen, die mit Phythagoras Wurzel aus a²-b² bzw Wurzel aus (xa-xb)²-(ya-yb)² ermittelt werden kann
o man sortiert einfach nach diesem (zweit~) geringsten (diagonalen) Abstand die Punkte aus.
o man kann diese nächstgelegenen Punktepaare nun mit einer Linie verbinden oder sonstwie bearbeiten, merken, was auch immer.

idealerweise - wenn man versierter ist als ich - kann man, anstatt alle anderen Punkte, die mit dem Ausgangspunkt verglichen werden sollen (bzw deren Abstand ‚gemessen‘ werden soll) von oben links bis unten rechts, … einen Algorithmus bauen, der kreisförmig vom Ausgangspunkt aus die Nachbarn scannt, was schneller geht, da die nächstgelegenen als erstes gefunden werden.

bestimmt kommt noch eine präzisere Antwort ;o)

#3

Moien

Kann mir dazu jmd was sagen???

Das ist ein Standardproblem, in deinem Fall mit zusätzlichen Einschränkungen. Google nach „Delaunay triangulation“ und kuck dir das als ersten Ansatz an. Wenn man das Prinzip drin hat geht der Rest recht simpel.

cu

#4

Ausnahmen, Sonderfälle gleich entfernt!
… jedoch muß schon beim abscannen infrage kommender Nachbarn, der Algorithmus gleich weit entfernte Punkte berücksichtigen und behandeln (und nicht beim erstbesten gefundenen nächsten Nachbarn mit dem scan abbrechen), sowie eine Routine für solche Sonderfälle (bzw Behandlung solcher) eingebaut werden.
… weiterhin könnte ich mir vorstellen, daß manche Punktepaare zu einem ‚gewünschten‘ dritten (bzw sechsten) Punkt gar keine dreiecks-Verbindung bekommen, weil sie gemeinsame … (einen ‚fünften‘) ‚nächstgelegene Nachbarn‘ haben … (?!)

#5

Hi
als ersten Ansatz habe ich folgende Adressen gefunden:

http://www.ikg.uni-hannover.de/lehre/katalog/gis/gis…
und
http://www.unigis.ac.at/fernstudien/UNIGIS_professio…

Klingt recht hilfeversprechend vor allem beim Erzeugen des Logarhythmus. Nachdem es aber auch sehr viele Programme gibt,
könnte es ja sein, das schon mal jmd einen Ansatz dazu programmiert hat!

Mfg Werner

#6

Wichtigen Link zu Delauney gefunden
Hi,
na also dem Netz sei dankbar.
Und sogar in vielen Programmiersprachen.

Damit sollte sich doch was anfangen lassen.

http://local.wasp.uwa.edu.au/~pbourke/papers/triangu…

Mfg Werner