Rechtwinklige Dreiecke

Wissenschaft Physik
1

Hallo!
Hier was für alle Knobler…

Gegeben sei eine Matrix. Jedes Feld dieser Matrix kann den Wert 0 oder 1 annehmen.
1 bedeutet „Punkt“
0 bedeutet „kein Punkt“

Bsp: 2x2 Matrix

1 1
1 1

Aufgabe soll es sein, alle rechtwinkligen Dreiecke, die sich durch Kombination verschiedener Punkte ergeben können, zu finden.

In unserem Beispiel sind das 4 Stück.

Anderes Beispiel:

3 x 3 Matrix

1 0 1
0 0 1
1 1 1

Nur „1“ können miteinander verbunden werden!

Meine Frage:

Gibt es eine mathematische Lösung, um die Anzahl der möglichen Dreiecke zu berechnen.

  • für eine beliebig große Matrix mit wahllos verteilten Punkten

mfg Tobi

2

Hallo,

In unserem Beispiel sind das 4 Stück.

Anderes Beispiel:

3 x 3 Matrix

1 0 1
0 0 1
1 1 1

wenn ich alle möglichen rechtwinkligen Dreiecke für dieses Beispiel suche, dann finde ich mehr als 4. Ich gehe davon aus, dass die horizotale gleich der vertikalen „Auflösung“ ist. Verbinde ich die Eins in der 3. Spalte, 1. Zeile [3,1] mit [3,2] und [1,1] habe ich das erste Dreieck.
[3,1],[3,3],[1,1]
[3,3],[3,1],[1,3]
[3,3],[3,1],[2,3]
[1,1],[3,1],[1,3]
sind schon vier weitere. Es lassen sich noch mehr finden.

Ein Lösungsansatz für Dein Problem Voraussetzung orthogonale Lage der Dreiecke( Katheten in Zeilen- und Spaltenrichtung:

Erste Schleife…
Der rechte Winkel ist immer eine 1! Zeilen und Spalten nach einer Eins durchsuchen.
zweite Schleife…
drehen der Dreiecksrichtung in alle vier Möglichkeiten
Anz_1=anzahl der Einsen auf der ersten Kathete
Anz_2=anzahl der Einsen auf der zweiten Kathete
Anzahl der Dreiecke für diese Richtung ist Anz_R1…4=Anz1*Anz2

AnzDreiecke dieses rechten Winkels: Anz_W=Anz_R1+Anz_R2+Anz_R3+Anz_R4

Gesamtanzahl ist die Summe aller Anz_W

DAs funktioniert aber nicht, wenn die Dreiecke auch z.B. so in der Matrix liegen können (nicht orthogonal):

0 0 0
1 0 1
0 1 0

Je nach Größe der Matrix ist aber auch dieser Fall ist ggf. in obige Lösung integrierbar. Die Anzahl der möglichen Richtungen steigt mit der Größe der Matrix…

Jan

3

Hallo,
es lassen sich insgesamt neun Dreiecke in dem Bsp. finden.

(1)0(1) (1) 0 1 1 0 (1) 1 0 1 (1)0(1)
 0 0 1 0 0 1 0 0 1 0 0(1) 0 0(1)
 1 1(1) (1) 1(1) 1(1)(1) (1)1(1) 1 1 1

(1) 0 1 1 0 1 1 0(1) (1)0(1)
 0 0 1 0 0 (1) 0 0 1 0 0 1
(1)(1)1 1(1)(1) (1)1(1) (1)1 1

Der Brute-Force Ansatz testet für je drei gesetzte Punkte, ob es sich um ein rechtwinkliges Dreieck handelt.

Gruss
Enno