000
07.07.2005, 16:21 Uhr
~TerryB
Gast
|
Hi,
ich habe mir selbst eine Aufgabe überlegt, um Algorithmik üben zu können. Stellt euch vor, ihr habt ein kariertes Blatt Papier vor euch liegen. Irgendwo auf diesem karierten Blatt Papier ist der Nullpunkt (0,0). Ein Kästchen ist z.B. 10x12 Einheiten groß.
Nun zieht eine beliebige Linie auf dieses Blatt.
Bemerkung: normalerweise sind Kästchen auf einem karierten Blatt ja quadratisch. Diese Kästchen dieses Algorithmus sollen aber theoretisch auch rechteckig sein können.
Die Kästchen möchte ich durch einen x,y-Index angeben, der bezogen ist auf den Nullpunkt. Der Nullpunkt ist das Kästchen (0,0). Das Kästchen z.B. direkt unter dem Nullpunkt ist (0,1).
Je weiter es auf dem Blatt Papier nach unten geht, desto grösser wird der y-Wert. Je weiter es nach rechts geht, desto größer wird der x-Wert.
Wie würdet ihr nun in C ermitteln, welche Kästchen durch diese Linie geschnitten werden?
Ich habe schon einen eigenen Ansatz. Er erscheint mir aber sehr ineffizient und ich bin mir nicht sicher, ob alles abgedeckt wird. Außerdem gilt er nur unter folgender Annahme:
Hier gehe ich davon aus, dass die Linie von links oben nach rechts unten verläuft und dass die Linie immer ein Kästchen durchläuft das darunter liegt. Und das klappt ja nicht. Denn die Linie könnte ja auch ein Kästchen durchlaufen, dass daneben liegt.
Mein Ansatz ist deshalb nur teilweise richtig.
1.) Steigung der Linie berechnen.
m = abs(Anfangspunkt_y-Endpunkt_y)/(Anfangspunkt_x-Endpunkt_x);
2.) Kästchenindex des gegebenen Anfangs- und Endpunktes berechnen.
Kaestchenindex_x = Anfangspunkt_x/Kaestchenbreite;
Kaestchenindex_y = Anfangspunkt_y/Kaestchenhoehe;
/* bei beiden Berechnungen Nachkommastelle abschneiden, da von 0 an gezählt wird */
/* dasselbe für den Endpunkt */
3.) Linie in Richtung Anfangspunkt verlängern, bis sie eine Kästchengrenze berührt.
offset_kaestchengrenze_oben = Anfangspunkt_y mod Kaestchenbreite;
Schnittpunkt_y = Anfangspunkt_y - offset_kaestchengrenze_oben;
/* m = abs(Schnittpunkt_y-Anfangspunkt_y)/Schnittpunkt_x-Anfangspunkt_x) nach Schnittpunkt_x auflösen */
Schnittpunkt_x = abs(Schnittpunkt_y-Anfangspunkt_y)/m + Anfangspunkt_x;
4.) Vom Schnittpunkt aus nun immer über die Kaestchenhöhe weiter gehen und über Steigung und den neuen y-Wert den passenden x-Wert ausrechnen.
Danach wie in 2.) den Kaestchenindex davon berechnen.
5.) Dies tun bis Endpunkt erreicht ist.
Ich bin wirklich schon auf Tipps von euch gespannt, wie man diesen Algorithmus schön lösen kann, so dass er wirklich für alle Linien gilt, egal wie sie liegen.
Vielen Dank schonmal im Voraus für eure Tipps
TerryB |
(wenn eine von beiden 69er wäre käme vermutlich immer ne Sauerei raus)