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

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?

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).

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?

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

Wie groß sind die Pixel?

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²

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

Wie groß mag ein Einheitspuxel wohl sein?

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.

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...

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

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

corner = math.hypot (i,j)

Ui, cool, Danke!