Rätsel: wie viele Quadrate von 25 x 36 = 900 werden von der Diagonalen geschnitten

[Vorn N. (eprofi)]

Wieder mal ein kleines Rätsel:
Gegeben sei ein Rechteck aus 25 x 36 = 900 kleine Quadraten.
Z.B. ein kariertes Blatt Papier mit 5mm-Quadraten.
Frage: wie viele Quadrate werden von der Diagonalen zerschnitten?
Antwort: 60?         Tipp: 25 + 36 = 61
Graphische Lösung mit PostScript steht im Anhang
Gesucht: Berechnung
Hilft da der Bresenham?

[Axel S. (a-za-z0-9)]

Vorn N. schrieb:
> Wieder mal ein kleines Rätsel:

Das ist kein "Rätsel", sondern eine stinknormale Matheaufgabe.

> Gegeben sei ein Rechteck aus 25 x 36 = 900 kleine Quadraten.
> Z.B. ein kariertes Blatt Papier mit 5mm-Quadraten.
> Frage: wie viele Quadrate werden von der Diagonalen zerschnitten?
> Antwort: 60?         Tipp: 25 + 36 = 61
> Gesucht: Berechnung

Der Weg wird unterteilt in Schritte zwischen je zwei Schnittpunkten mit 
dem Koordinatengitter. Da dX=25 (=5*5) und dY=36 (=2²*3²) teilerfremd 
sind, liegt außer den Endpunkten kein weiterer 
Koordinaten-Kreuzungspunkt auf dem Weg. Jeder Schritt schneidet darum 
ein weiteres Quadrat entweder in x- oder in y-Richtung. Insgesamt sind 
24 (dX-1) Schritte in x- und 35 (dY-1) Schritte in y-Richtung zu 
bewältigen. Dazu das Quadrat das man im ersten Schritt durchschneidet. 
Ergibt die Weglänge als (dX-1)+(dY-1)+1. Oder einfacher dX + dY - 1.

Für den Fall, daß dX und dY nicht teilerfremd sind, kann man den 
Gesamtweg in Teilwege unterteilen, für die das dann jeweils wieder gilt. 
Sei z = ggT(dX, dY). Dann sind es z Einzelwege von (dX/z, dY/z) Länge. 
Die Gesamtlänge ist dann z*(dX/z + dY/z -1) = dX + dY - z.

Das war ja einfach. Komm ich jetzt ins Fernsehen?

[Vorn N. (eprofi)]

Ich danke Dir für Deine ausführliche Antwort!
Vor allem für die (nicht explizit gefragte) allgemeine Form.
War recht überrascht, dass zeitweise die Zahl der Downloads des PS-Codes 
höher war als die des PDF (14:13).

[Johann L. (gjlayde)]

Axel S. schrieb:
> Vorn N. schrieb:
>> Wieder mal ein kleines Rätsel:
>
> Das ist kein "Rätsel", sondern eine stinknormale Matheaufgabe.
>
> [...]
> Sei z = ggT(dX, dY). Dann sind es z Einzelwege von (dX/z, dY/z) Länge.
> Die Gesamtlänge ist dann z*(dX/z + dY/z -1) = dX + dY - z.

Nett :-)

> Das war ja einfach. Komm ich jetzt ins Fernsehen?

Wenn du das analoge Problem für Kreise löst stehen die Chancen garnicht 
schlecht (-:

o  Einheitspixel mit einer Pixel-Ecke in (0,0).

o  Kreis mit Radius r (gerne auch ganzzahlig) um (0,0).

Wieviele Pixel schneidet der Kreis?

[Michael B. (alter_mann)]

Johann L. schrieb:
> Wieviele Pixel schneidet der Kreis?

Wie groß sind die Pixel?

[Axel S. (a-za-z0-9)]

Johann L. schrieb:
> Axel S. schrieb:

>> Das war ja einfach. Komm ich jetzt ins Fernsehen?
>
> Wenn du das analoge Problem für Kreise löst stehen die Chancen garnicht
> schlecht (-:
>
> o  Einheitspixel mit einer Pixel-Ecke in (0,0).
> o  Kreis mit Radius r (gerne auch ganzzahlig) um (0,0).
>
> Wieviele Pixel schneidet der Kreis?

Das ist jetzt nicht wahnsinnig viel komplizierter. Zunächst muß man ja 
nur einen Quadranten betrachten. Sagen wir einfach Quadrant I (x>=0 und 
y>= 0). Der Kreisbogen beginnt in dem Pixel bei (1,r) und endet in dem 
Pixel bei (r,1). Bei jedem Übergang von einem Pixel zu einem anderen muß 
der Bogen entweder das x- oder das y-Gitter schneiden (genauso wie bei 
der Geraden). Das sind auch hier wieder r-1 Gitterlinien in x- und r-1 
Gitterlinien in y-Richtung.

Bleibt die Frage nach Gitterpunkten, die exakt auf dem Kreisbogen 
liegen. Hier überqueren wir 2 Gitterlinien gleichzeitig, was die Anzahl 
der Pixel jeweils um eins reduziert. Aus elementaren geometrischen 
Überlegungen (-: folgt, daß ein solcher Punkt die diophantische 
Gleichung x² + y² = r² [1] erfüllen muß. Damit reduziert sich unser 
Problem auf die Frage, wieviele Lösungen x>0, y>0 diese Gleichung für 
das gegebene r hat. Für praktikable Werte von r würde man das einfach 
ausprobieren: teste ob sqrt(r² - x²) ganzzahlig ist für alle x von 1 bis 
sqrt(y).


[1] auch bekannt als "pythogoräische Tripel". Das bekannteste ist 
(3,4,5) => 3² + 4² = 5²

[Johann L. (gjlayde)]

Michael B. schrieb:
> Johann L. schrieb:
>> Wieviele Pixel schneidet der Kreis?
>
> Wie groß sind die Pixel?

Wie groß mag ein Einheitspuxel wohl sein?

[Heinz V. (heinz_v)]

Vorn N. schrieb:
> Hilft da der Bresenham?

Nein, der original Bresenham macht jeweils einen Schritt in die X 
Richtung nach rechts und setzt dann ein Pixel das in Y Richtung, das 
möglichst nahe der Linie liegt, daher kommt Bresenham nur auf 36 
gesetzte Pixel.

Mit Antialiasing müsste es aber zum richtigen Ergebniss führen, wenn man 
alle gefärbten Pixel zusammenzählt.

[Johann L. (gjlayde)]

Axel S. schrieb:
> Johann L. schrieb:
>> Axel S. schrieb:
>
>>> Das war ja einfach. Komm ich jetzt ins Fernsehen?
>>
>> Wenn du das analoge Problem für Kreise löst stehen die Chancen garnicht
>> schlecht (-:
>
> Das ist jetzt nicht wahnsinnig viel komplizierter.
>
> Bleibt die Frage nach Gitterpunkten, die exakt auf dem Kreisbogen
> liegen. Hier überqueren wir 2 Gitterlinien gleichzeitig, was die Anzahl

DAS ist die Stelle, wo du ins Fernsehen kommen kannst ;-)

> der Pixel jeweils um eins reduziert. Aus elementaren geometrischen
> Überlegungen (-: folgt, daß ein solcher Punkt die diophantische
> Gleichung x² + y² = r² [1] erfüllen muß. Damit reduziert sich unser
> Problem auf die Frage, wieviele Lösungen x>0, y>0 diese Gleichung für
> das gegebene r hat. Für praktikable Werte von r würde man das einfach
> ausprobieren: teste ob sqrt(r² - x²) ganzzahlig ist für alle x von 1 bis
> sqrt(y).

Das ist aber mindestens so kompliziert wie r zu faktorisieren...

[Gustl B. (-gb-)]

So, hier die Bruteforce Lösung für Pixel und Voxel.

[Johann L. (gjlayde)]

Gustl B. schrieb:
> corner = math.sqrt(abs(math.pow(i,2)+math.pow(j,2)))

corner = math.hypot (i,j)

[Gustl B. (-gb-)]

Ui, cool, Danke!