Dringend Hilfe gesucht! - Punkte im Raum - Euklidischer Abstand

dancer

Hallo Leute,

ich habe mich schon länger anmelden wollen, habe ich doch schon einige sehr nutzvolle Beiträge hier lesen dürfen. Leider kann ich selbst noch nicht viel dazusteuern. Bin ertes Semester und eig. bisher mit den Aufgaben gut Zurecht gekommen. Seit einer Woche nun eine neue Freundin und ich BEKOMME MEINEN KOPF NICHT FREI!
Ich wäre für jede Hilfe sehr dankbar, denn ich muss bis Mitternacht mein Quellcode hochgeladen haben.

Die Aufgabe habe ich verstanden: Eingabe: -ein Referenzpunkt und N Punkte im Raum. Den Punkt, mit dem geringsten Abstand zum Ref-punkt ermitteln.
Probleme habe ich nun mit den Strukturen in Verbindung mit dem Array usw. Ich weiß nicht mal wo ich ansetzen soll. Bin fast am Verzweifeln und heute ist Freitag!

Hier die Aufgabenstellung:

11. Aufgabe: Eine Menge von N Punkten, die Raumkoordinaten darstellen, sollen in einem Array gespeichert werden. Jeder Punkt soll durch eine Struktur mit den x-,y- und z- Koordinaten als Komponenten dargestellt. Entwickeln Sie ein Programm, dass zu manuell eingegebenen Punktkoordinaten den als nächster Nachbar vorhandenen punkt ermittelt. Zur Strukturierung des Programmes entwickeln Sie zwei Funktionen:

* Berechnung des euklidischen Abstandes zwischen zwei Punkten: Parameter sind zwei Punktstrukturen. Der Rückgabewert ist der Abstand zwischen den Punkten.

* Bestimmung des nächsten Nachbarn zu eingegeben Koordinaten: Parameter sind die Koordinaten eines Punktes. Der Rückgabewert sind die Koordinaten des nächsten Nachbarn.

Wie gesagt, bin für jegliche Hilfe dankbar.

MfG

CStoll

Den Euklidischen Abstand zu berechnen sollte nicht so schwierig sein - Stichwort "Pythagoras".

Um den nächsten Nachbarn zu einem deiner Punkte zu finden, mußt du im Zweifelsfall dein komplettes Array durchlaufen und für alle anderen Punkte den Abstand zum Ziel berechnen - derjenige mit dem zweitkürzesten Abstand (der kürzeste Abstand ist 0 und gehört zum Zielpunkt selber) ist der gesuchte Nachbar.

dancer

Danke, das ist mir eig. auch bewusst (denke ich jedenfalls *g*). Wird dann wohl ein dreidimensionales Array sein, oder? Aber wie handhabe ich das mit der Struktur, ich habe hier dicke Wälzer aber bekomme keinen Durchblick.
Vielleicht wäre ein Beispiel ganz nett, wie ich die Struktur(array) für die Koordinaten aufstelle und mit einer anderen Struktur die berechnung...
Auf jeden fall hilft es, mit euch darüber zu diskutieren. Finde langsam einen Faden.

CStoll

Eigentlich reicht ein eindimensionales Array, in dem du alle deine Punkte sammelst:

typedef struct
{
  double x,y,z;
} point3d;

point3d all_points[MAX_SIZE];

double dist(point3d p1, point3d p2)
{
  ...
}

point3d nearest_neighbour(point3d pt)
{
  for(int i=0;i<point-count;++i)
  {
    double d = dist(pt,all_points[i];
    ...
  }
}

dancer

Bist du so nett und könntest noch etwas kommentieren? Ich verstehe nur die Hälfte.

mcr

Das solltest du eigentlich schon verstehen, was er da macht.

-- Im ersten Teil definiert er sich einen Typen, in dem die Koordinaten
eines Punktes im drei dimensionalen Raum abgespeichert werden.

-- Dann definiert er sich ein ein-dimensionales Array zum Speichern
aller Punkte. Hier solltest du vielleicht noch abfragen, ob mehr Punkte
eingegeben werden, als beabsichtigt MAX_SIZE ist, oder verwende malloc(),
solltest du mehr Punkte speichern müssen.

-- Dann hat er dir die Definition einer Funktion gegeben, die du noch
ausfüllen mußt: Ziel der Funktion: Berechnung des Abstandes zweier Punkte.

-- Und zum Schluß hat er dir noch eine Funktionsdefinition gegeben,
die den nächst-gelegen Punkt finden soll. Auch hier, mußt du die Hauptarbeit
noch machen. Ok, einen Tip: "point-count" gibt die Anzahl der gespeicherten
Punkte an.

-- ok, noch einen Tip: du berechnest den Abstand jedes Punktes zu dem
einen ausgewählten und speicherst dir in jedem Schritt den zum Zeitpunkt
kleinsten Abstand und Punkt ab. Wenn alle Punkte verglichen sind, gibst
du den aktuell nächsten Punkt aus.

Ich hoffe, das hat dir geholfen.

Gruß mcr

PS: dies ist kein C89 Code, er ist eher als Denkansatz zu verstehen.

dancer

Wollte mich noch für die Hilfe bedanken! Habe zwar den ganzen Tag daran gesessen, war am Ende jedoch zufrieden.