Geraden (P1(x,y),P2(x,y)

Berni123

Hi,

hab folgendes Problem:

ich habe eine unbestimmte Anzahl von Geraden, die in einem dyn. Feld gespeichert sind.
Die Geraden sollen zusammenghängt ein Polygon(können auch mehrere sein)
ergeben.
Das Problem ist jetzt, daß die Geraden in meinem Feld wild durcheinander
gewürfelt sind.

Kennt jemand von euch vielleicht einen Algorithmus der dieses Problem lösen kann?
Wenn ich die Geraden am Bildschirm ausgebe, habe ich keine Probleme, jedoch wenn ich Sie plotten will.

Hoffe ihr versteht mein Problem

Winn

Öööh nein... verstehe ich nicht.

Wenn Du sie schon auf dem Bildschirm hast, warum ist dann das Drucken ein Problem ?
Es handelt sich wohl um Geraden im zweidimensionalen Raum, oder ?
Wenn es Polygone sein sollen, warum wandelst Du Dein Geradengestrüpp nicht in ein Polygon Feld um... also quasi eine zweidimensionale Liste die die entsprechenden Punkte enthalten, die ein Polygon bilden, dabei darf ein Punkt (Stichwort: Geradenschnittpunkt) auch in anderen Polygonen auftauchen...

Berni123

Es geht um Geraden im 2 Dimensionalen Raum.
Das Drucken stellt auch kein Problem dar.

Meine Garaden sind folgendermaßen gespeichert:

struct gerade
{
int p1x;
int p1y;
int p2x;
int p2y;
};
vector<gerade> geradenmenge;  // Hier werden alle Geraden gespeichert, jedoch unsortiert

Wenn ich meine Geraden auf dem Bildschirm darstelle habe ich auch keine Probleme, denn der Bildaufbau geht ja so schnell von statten daß keiner was von den nicht sortierten Geraden merkt.
d.h. die erste Gerade wird z.B. links oben gezeichnet, dir nächste in der mitte, die nächste unten rechts, usw...
Zusammengesetzt ergeben sie mehrere Polygone.

Ich möchte die Geraden sozusagen aneinanderhängen damit eine Schrittmotorsteuerung das ganze so schnell wie möglich fahren kann, also die Fahrbewegung optimiert.

Mit einem Polygon ist alles wunderbar.
Jedoch komme ich mit steigender Zahl der Polygone nicht mehr klar, das ganze wird zu komplex, denn dann gehört ja ein Punkt zu einem anderen Polygon,
beim sortieren bekomme ich dann Probleme.

Bin anscheinend zu blöd dazu, das ganze mathematisch so zu formulieren dass ich mir selbst den passenden Algorithmus zusammenbauen kann.

Plotter benutzen doch intern auch einen Algorithmus zum optimieren der Fahrbewegung, dachte ich zumindest.

Jester

Sehe ich das richtig, daß Deine Geraden keine Geraden sondern Strecken sind? Also mit Anfangs und Endpunkt?
Sind in der Liste nur die Strecken eines Polygonzuges oder von mehreren? Sind die Polygonzüge geschlossen?
Gib mal ein paar mehr Infos, dann kriegen wir das vielleicht auch hin.
MfG Jester

Berni123

Sorry, hab mich mit Geraden falsch ausgedrückt, es sind Strecken.

Ich habe in der Liste alle Strecken von allen Polygonen.

Manche Polygone sind auch nicht geschlossen.

Die Strecken bekomme ich folgendermaßen:

Ich habe einen beliebigen 3D Körper dessen Oberfläche aus Dreiecken aufgebaut ist.

Nun lege ich eine Ebene durch den Körper.

Die Schnittpunkte zwischen dem Körper und der Ebene speichere ich in der Liste.

Die Strecken in der Liste ergeben sich durch die 2 Schnittpunkte von einem Dreieck, daß die Ebene schneidet.

Jester

Naja, dann würd ich sagen: Du fängst mit einer beliebigen Strecke an. Dann suchst Du in Deinem Array nach einer Strecke, die einen der Startpunkte berührt. Die hängst Du hintendran. Und das immer weiter. Wenn Du keine passenden Strecken mehr findest, dann hast Du entweder das Polygon geschlossen, oder Du mußt von der Anfangsstrecke auch noch in der anderen Richtung laufen. Damit das suchen der Strecken mit passenden Anfangspunkten halbwegs effizient muß man vielleicht ein bissel was reinstecken:

Erstmal würde ich für jeden Punkt an dem eine Strecke beginnt oder endet einen Array-Eintrag mit Referenz auf die passende Strecke anlegen. Dieses Punkte-Array kannst Du dann nach x und y Koordinate sortieren (nach x sortieren und falls x gleich nach y). Dann kannst Du effizient (mit O(log n)) nach einem passenden Punkt suchen. Bei n Strecken gibt das einen Aufwand von O(n*log n), das ist eigentlich ganz vertretbar.

Das ganze ziehst Du durch, bis alle Strecken vergeben sind.

Achtung, das Verfahren ist nicht 100% sicher. Polygone, die sich an Eckpunkten berühren werden möglicherweise falsch konstruiert, da gibts nämlich ne Wahlmöglichkeit...

MfG Jester

Berni123

Dachte mir erst, wenn ich meine kartesischen Koordinaten in Polarkoordinaten umwandle könnte ich das lösen, geht aber nur wenn ich den Mittelpunkt eines Polygons kenne, wär so schön gewesen.

Vielen DANK erst mal