Anzahl der Dreiecke eines regelmäßigen n-Ecks

Softwarepraktikum I

Anzahl von Dreiecken eines regelmäßigen n-Ecks

Sascha Kurz 07.07.2001

1. Einleitung
2. Zweck des Programms
3. Funktionsweise des Programms
4. Aufruf der public-Methoden
5. Ähnliche Fragestellungen
6. Literatur
7. Mängelliste
Beispiele regelmäßiger n-Ecke
Tabellen der Anzahl der m-Ecke regelmäßiger n-Ecke

1. Einleitung

Diese HTML-Seite ist die Dokumentation zum C++ - Programm drawing.cpp, welches im Rahmen des Software Praktikums I an der Universität Bayreuth entstandt.
Der Sinn und Zweck dieses Programms wird unter 2. näher dargestellt.
Aktuelle Versionen sind unter der URL http://www.stud.uni-bayreuth.de/~a8581/ zu erhalten.
Kommentare zu dem Programme bitte an KurzTEF@web.de

2. Zweck des Programms

In drawing.cpp sind mehrere Routinen implementiert, mit denen man die Anzahl der Dreiecke eines regelmäßigen n-Ecks ausrechnen kann. Beispiel (regelmäßiges 9-Eck):

Dieses regelmäßige 9-Eck enthält 90 Dreiecke, 36 Vierecke, 18 Fünfecke, 9 Sechsecke und 1 Neuneck.

Definition eines m-Ecks (Dreiecks):

Die von den Kanten erzeugten Schnittpunkte werden ebenfalls wie die Knoten als, gleichberechtigte, Punkteb angesehen. m-Ecke, im Spezialfall Dreiecke, bestehen aus der entsprechenden Anzahl solcher Punkte, die mit Kantenstücken verbunden sind. Dabei darf ein solches m-Eck keine weiteren Punkte oder Kantenstücke enthalten.

Natürlich kann man den Begriff des m-Ecks auch anders definieren. Dies führt auf andere Fragestellungen die unter 5. näher dargestellt sind.

Weitere Beispielzeichnungen regelmäßiger n-Ecke.

3. Funktionsweise des Programms

Allgemeines Verfahren:

(i) In einem ersten Schritt werden die Koordinaten eines regelmäßigen n-Ecks berechnet

(ii) Die Schnittpunkte aus den Kanten werden berechnet, und den jeweiligen Kanten zugeordnet

(iii) Die Geraden werden sortiert, so daß benachbarte Schnittpunkte nebeneinander liegen.

(iv) Aus dieser Information wird eine Adjazensliste des Graphens der Knoten und Schnittpunkte erstellt

(v) Anhand dieser Adjazensliste wird die Anzahl der 3-Ecke bzw. m-Ecke berechnet

Spezielle Vereinfachungen

Wenn man nur an den m-Ecken regelmäßiger Polygone interessiert ist, kann man sich auch auf einen Sektor des Polygons beschränken, und die Ergebnisse mit n multiplizieren. Dies geht wegen der Roatationssymmetrie eines n-Ecks.

Weitere Informationen zu (v)

Berechnung der 3-Ecke aus einer Adjazensliste

Um sämtliche Dreiecke zu finden, werden einfach alle Zykel der Länge 3 in dem Kreuzungsgraphen gesucht, und sichergestellt, das es keinen Knoten im inneren eines solchen Dreiecks gibt. Dies geht mit Hilfe der Adjazensliste mit einem Aufwand in der Größenornung der Anzahl der Knoten des Graphen, hier also O(n^4), bzw. O(n^3) wenn man die Rotationssymmetrie ausnutzt. Zum Auffinden aller 3-Zykel, werden einfach alle Knoten durchlaufen. Zu einem solchen Knoten werden alle Paare von Nachbarn bestimmt. Bei jedem Paar von Nachbarn wird bestimmt, ob sie selbst benachbart sind. Bei einem regelmäßigen Polygon kann es keine inneren Punkte in einem solchen Dreieck geben. Eine nähere Darstellung und exakte Abschätzung der Komplexität findet sich in "Die maximale Anzahl von Dreiecken bei Zeichnungen von Graphen" [4]

Berechnung der m-Ecke aus einer Adjazenzliste und en Koordinaten der Punkte

Auch bei diesem Verfahren werden werden in einer ersten Schleifen alle Knoten durchlaufen, und ein Nachbar dazu bestimmt. Von dieser Startkante, aus den zwei Punkten, ausgehend bestimmt man zwei weitere Kanten, die den maximalen, bzw. minimalen Winkel zu dieser Kante bilden. Nun durchläuft man ein m-Eck, indem man iteriert die Kanten mit dem maximalen, bzw. minimalen Winkel wählt. Dies geschieht solange, bis man wieder am Ausgangsknoten angekommen ist.

4. Aufruf der public-Methoden

4.1 set-Methoden
4.2 get-Methoden
4.3 Informations-Methoden
4.4 Berechnungen
4.5 Bauskasten zum Programmieren eigener Berechnungsroutinen

4.1 set-Methoden

int setMatrix(int a,int b,int w)

Belegt den Wert an Position (a,b) der Verbindungsmatrix mit dem Wert w. Hierbei darf w nur die Werte 0 und 1 annehmen.

Rückgabewert: -1 bei Fehlern, 0 sonst

Diese Funktion wird nur benötigt, wenn man die Anzahl der m-Ecke von anderen als den regelmäßigen Polygonen berechnet will, weil die Verbindungsmatrix eines regelmäßigen n-Ecks automatisch von CreateRegularNGon() erzeugt wird.

int setMatrix(int a, int* b)

Belegt die a-te Spalte der Verbindungsmatrix mit den Werten im int-Vektor b. Die Werte dürfen nur 0 und 1 annehmen.

Rückgabewert: -1 bei Fehlern, 0 sonst

int setMatrix(int** a)

Belegt die Verbindungsmatrix mit den Werten aus der int-Matrix a. Die Werte dürfen nur 0 und 1 annehmen.

Rückgabewert: -1 bei Fehlern, 0 sonst

int setKnotenX(T i,S x)

Belegt die X-Koordinaten des i-ten Knotens mit dem Wert x. Hierbei ist T ein Ganzzahldatentyp, normalerweise int oder long, und S ein Fließkommadatentyp, normalerweise double oder long double.

Rückgabewert: -1 bei Fehlern, 0 sonst

Diese Funktion wird nur benötigt, wenn man die Anzahl der m-Ecke von anderen als den regelmäßigen Polygonen berechnet will, weil die Koordinaten eines regelmäßigen n-Ecks automatisch von CreateRegularNGon() berechnet werden.

int setKnotenY(T i,S y)

Belegt die Y-Koordinaten des i-ten Knotens mit dem Wert y. Hierbei ist T ein Ganzzahldatentyp, normalerweise int oder long, und S ein Fließkommadatentyp, normalerweise double oder long double.

Rückgabewert: -1 bei Fehlern, 0 sonst

int CreateCompleteGraph()

Erzeugt die Matrix eines vollständigen Graphen, und belegt die Verbindungsmatrix.

Rückgabewert: -1 bei Fehlern, 0 sonst

int CreateRegularPoints()

Erzeugt die Koordinaten eines regelmäßigen n-Ecks, und belegt die entsprechenden Werte KnotenX und KnotenY.

Rückgabewert: -1 bei Fehlern, 0 sonst

int CreateRegularNGon()

Erzeugt ein regelmäßiges n-Eck, mitsamt Verbindungsmatrix und Koordinaten der Knoten.

Rückgabewert: -1 bei Fehlern, 0 sonst

4.2 get-Methoden

int getAnzahlDerKnoten()

Gibt die Anzahl der Knoten zurück.

Rückgabewert: -1 bei Fehlern

T getAnzahlDerKanten()

Gibt die Anzahl der Kanten zurück.

Rückgabewert: -1 bei Fehlern

T getAnzahlDerKreuzungspunkte()

Gibt die Anzahl der Kreuzungspunkte zurück.

Rückgabewert: -1 bei Fehlern

S getKnotenX(int i)

Gibt die X-Koordinate des i-ten Knotens zurück.Hierbei ist T ein Ganzzahldatentyp, normalerweise int oder long, und S ein Fließkommadatentyp, normalerweise double oder long double.

S getKnotenY(int i)

Gibt die Y-Koordinaten des i-ten Knotens zurück. Hierbei ist T ein Ganzzahldatentyp, normalerweise int oder long, und S ein Fließkommadatentyp, normalerweise double oder long double.

S getKreuzungspunktX(T i)

Gibt die X-Koordinate des i-ten Kreuzungspunktes zurück. Hierbei ist T ein Ganzzahldatentyp, normalerweise int oder long, und S ein Fließkommadatentyp, normalerweise double oder long double.

S getKreuzungspunktY(T i)

Gibt die Y-Koordinate des i-ten Kreuzungspunktes zurück. Hierbei ist T ein Ganzzahldatentyp, normalerweise int oder long, und S ein Fließkommadatentyp, normalerweise double oder long double.

int getKnotengrad(int i)

Gibt den Knotengrad des i-ten Knotens zurück.

Rückgabewert: -1 bei Fehlern

int getAnzahlDerNachbarn(T i)

Gibt die Anzahl der Nachbarn des i-ten Kreuzungspunktes zurück. Hierbei ist T ein Ganzzahldatentyp, normalerweise int oder long.

Rückgabewert: -1 bei Fehlern

int getMatrix(int i,int j)

Gibt den Wert der Verbindungsmatrix an der Stelle (i,j) zurück.

Rückgabewert: 1 wenn die Knoten i und j durch eine Kante verbunden sind, und 0 sonst

T getPolygone(int m)

Gibt die Anzahl der m-Ecke zurück.

Rückgabewert: -1 bei Fehlern

4.3 Informations-Methoden

T AnzahlRegionsRegularPolygon(int n)

Berechnet die Anzahl der Regionen (Flächen) eines regulären Polygons nach einer Formel aus "The number of intersection points made by the diagonals of a regular polygon" [1]

T AnzahlIntersectionsRegularPolygon(int n)

Berechnet die Anzahl der Kreuzungspunkte (intersection points) eines regulaeren Polygons nach einer Formel aus "The number of intersection points made by the diagonals of a regular polygon" [1]

T NachschlagenDreiecke(int n)

Gibt die Anzahl der Dreiecke eines regelmäßigen n-Ecks zurück, ohne sie auszurechnen. Die Daten werden in einem Standardfile nachgeschlagen.

Rückgabewert: -1 bei Fehlern

T NachschlagenDreiecke(int n,char* file)

Durchsucht die Datei file nach der Anzahl der Dreiecke eines regelmäßigen n-Ecks, und gibt diese zurück.

Rückgabewert: -1 bei Fehlern

T NachschlagenPolygone(int n,int m)

Gibt die Anzahl der m-Ecke eines regelmäßigen n-Ecks zurück, ohne sie auszurechnen. Die Daten werden in einem Standardfile nachgeschlagen.

Rückgabewert: -1 bei Fehlern

T NachschlagenPolygone(int n,int m,char* file)

Durchsucht die Datei file nach der Anzahl der m-Ecke eines regelmäßigen n-Ecks, und gibt diese dann zurück.

4.4 Berechnungen

T AnzahlDreieckeRegularPolygon1(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Hierbei muß n ungerade sein. Zwischenergebnisse sind nicht mehr abrufbar.

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon2(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Hierbei muß n ungerade sein. Zwischenergebnisse sind abrufbar.

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlPolygoneRegularPolygon1(int n)

Berechnet die Anzahl der Polygone eines regelmäßigen n-Ecks. Hierbei muß n ungerade sein. Zwischenergebnisse sind nicht mehr abrufbar. Die Anzahl der m-Ecke werden ausgegeben.

Rückgabewert: -1 bei Fehlern, Anzahl der Polygone sonst

T AnzahlPolygoneRegularPolygon2(int n)

Berechnet die Anzahl der Polygone eines regelmäßigen n-Ecks. Hierbei muß n ungerade sein. Zwischenergebnisse sind abrufbar. Die Anzahl der m-Ecke werden ausgegeben.

Rückgabewert: -1 bei Fehlern, Anzahl der Polygone sonst

T AnzahlDreieckeRegularPolygon3(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Hierbei muß n ungerade sein. Zwischenergebnisse sind nicht mehr abrufbar. Gibt die Rechenzeiten aus.

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon4(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Hierbei muß n ungerade sein. Zwischenergebnisse sind abrufbar. Gibt die Rechenzeiten aus.

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlPolygoneRegularPolygon3(int n)

Berechnet die Anzahl der Polygone eines regelmäßigen n-Ecks. Hierbei muß n ungerade sein. Zwischenergebnisse sind nicht mehr abrufbar. Die Anzahl der m-Ecke werden ausgegeben. Gibt die Rechenzeiten aus.

Rückgabewert: -1 bei Fehlern, Anzahl der Polygone sonst

T AnzahlPolygoneRegularPolygon4(int n)

Berechnet die Anzahl der Polygone eines regelmäßigen n-Ecks. Hierbei muß n ungerade sein. Zwischenergebnisse sind abrufbar. Die Anzahl der m-Ecke werden ausgegeben.

Rückgabewert: -1 bei Fehlern, Anzahl der Polygone sonst

T AnzahlDreieckeRegularPolygon5(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Zwischenergebnisse sind nicht mehr abrufbar.

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon6(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Zwischenergebnisse sind abrufbar.

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlPolygoneRegularPolygon5(int n)

Berechnet die Anzahl der Polygone eines regelmäßigen n-Ecks. Zwischenergebnisse sind nicht mehr abrufbar. Die Anzahl der m-Ecke werden ausgegeben.

Rückgabewert: -1 bei Fehlern, Anzahl der Polygone sonst

T AnzahlPolygoneRegularPolygon6(int n)

Berechnet die Anzahl der Polygone eines regelmäßigen n-Ecks. Zwischenergebnisse sind abrufbar. Die Anzahl der m-Ecke werden ausgegeben.

Rückgabewert: -1 bei Fehlern, Anzahl der Polygone sonst

T AnzahlDreieckeRegularPolygon7(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Zwischenergebnisse sind nicht mehr abrufbar. Gibt die Rechenzeiten aus.

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon8(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Zwischenergebnisse sind abrufbar. Gibt die Rechenzeiten aus.

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlPolygoneRegularPolygon7(int n)

Berechnet die Anzahl der Polygone eines regelmäßigen n-Ecks. Zwischenergebnisse sind nicht mehr abrufbar. Die Anzahl der m-Ecke werden ausgegeben. Gibt die Rechenzeiten aus.

Rückgabewert: -1 bei Fehlern, Anzahl der Polygone sonst

T AnzahlPolygoneRegularPolygon8(int n)

Berechnet die Anzahl der Polygone eines regelmäßigen n-Ecks. Zwischenergebnisse sind abrufbar. Die Anzahl der m-Ecke werden ausgegeben.

Rückgabewert: -1 bei Fehlern, Anzahl der Polygone sonst

T AnzahlDreieckeRegularPolygon1_s(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Hierbei muß n ungerade sein. Zwischenergebnisse sind nicht mehr abrufbar. Nutzt die Rotationssymmetrie aus, und ist deswegen schneller als die AnzahlDreieckeRegularPolygon1(int n)

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon2_s(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Hierbei muß n ungerade sein. Zwischenergebnisse sind abrufbar. Nutzt die Rotationssymmetrie aus, und ist deswegen schneller als die AnzahlDreieckeRegularPolygon2(int n)

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon3_s(int n)

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon4_s(int n)

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon5_s(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Zwischenergebnisse sind nicht mehr abrufbar. Nutzt die Rotationssymmetrie aus, und ist deswegen schneller als die AnzahlDreieckeRegularPolygon5(int n)

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon6_s(int n)

Berechnet die Anzahl der Dreiecke eines regelmäßigen n-Ecks. Zwischenergebnisse sind abrufbar. Nutzt die Rotationssymmetrie aus, und ist deswegen schneller als die AnzahlDreieckeRegularPolygon6(int n)

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon7_s(int n)

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

T AnzahlDreieckeRegularPolygon8_s(int n)

Rückgabewert: -1 bei Fehlern, Anzahl der Dreiecke sonst

4.5 Bauskasten zum Programmieren eigener Berechnungsroutinen

Statt die vorgefertigten Routinen unter 4.4 zu benutzen kann man sich auch eigene Berechnungen mit einer Art Baukasten selber zusammenbasteln. So könnte man zum Beispiel die Anzahl der Dreiecke eines Graphen berechnen wollen, der kein regelmäßiges Polygon ist.

Die Berechnung läuft immer in 5 Schritten ab, dies sind die Punkte (i)-(v) bei 3. Für die einzelnen Schritte gibt es jeweils mehrere Methoden zur Auswahl, die nun näher erläutert werden.

1. Schritt: Setzen des Graphen

Hierfür muß man die set-Methoden benutzen, oder sich eigene Routinen schreiben.

2. Schritt: Berechnen der Kreuzungspunkte

int BerechneKreuzungspunkte()

Berechnet die Anzahl der Kreuzungspunkte eines allgemeinen Graphen.

Rückgabe: -1 bei Fehlern, 0 sonst

int BerechneKreuzungspunkte_symmetrisch()

Berechnet die Kreuzungspunkte eines Sektors eines regelmäßigen n-Ecks. Der Aufruf bei allgemeineren Graphen scheint nicht allzu sinnvoll zu sein.

Rückgabe: -1 bei Fehlern, 0 sonst

3. Schritt: Sortieren der Geraden

int sortiereGeradenQS()

Sortiert die Geraden mit Hilfe von Quicksort.

Rückgabe: -1 bei Fehlern, 0 sonst

int sortiereGeradenMS()

Sortiert die Geraden mit Hilfe von Mergesort.

Rückgabe: -1 bei Fehlern, 0 sonst

int sortiereGeradenHS(void)

Sortiert die Geraden mit Hilfe von Heapsort.

Rückgabe: -1 bei Fehlern, 0 sonst

3.5. Schritt: Verschmelzen von Mehrfachschnittpunkten

Dies ist nur sinnvoll, wenn man weiß, daß es Mehrfachschnittpunkte gibt.

int VerschmelzeMehrfachSchnittpunkte()

Verschmilzt Schnittpunkte, die dicht beieinander liegen zu einem einzigen Schnittpunkt.

Rückgabe: -1 bei Fehlern, 0 sonst

4. Schritt: Berechnen der Adjazensliste des Kreuzungsgraphen

BerechneNachbarArrays()

Berechnet die Adjazensliste des Kreuzungsgraphen. Es werden keine Zwischenergebnisse gelöscht.

Rückgabe: -1 bei Fehlern, 0 sonst

int BerechneNachbarArrays_o1()

Berechnet die Adjazensliste des Kreuzungsgraphen. Es wird ein Teil der Zwischenergebnisse gelöscht. Vor der Benutzung unbedingt die Bemerkung im Quellcode lesen.

Rückgabe: -1 bei Fehlern, 0 sonst

int BerechneNachbarArrays_o2()

Berechnet die Adjazensliste des Kreuzungsgraphen. Es wird ein Teil der Zwischenergebnisse gelöscht. Vor der Benutzung unbedingt die Bemerkung im Quellcode lesen.

Rückgabe: -1 bei Fehlern, 0 sonst

BerechneNachbarArrays_symmetrisch()

Berechnet die Adjazensliste des Kreuzungsgraphen. Es werden keine Zwischenergebnisse gelöscht. Ist nur bei Berechnung eines Sektors eines regelmäßigen n-Ecks anwendbar.

Rückgabe: -1 bei Fehlern, 0 sonst

int BerechneNachbarArrays_o1_symmetrisch()

Berechnet die Adjazensliste des Kreuzungsgraphen. Es wird ein Teil der Zwischenergebnisse gelöscht. Vor der Benutzung unbedingt die Bemerkung im Quellcode lesen. Ist nur bei Berechnung eines Sektors eines regelmäßigen n-Ecks anwendbar.

Rückgabe: -1 bei Fehlern, 0 sonst

int BerechneNachbarArrays_o2_symmetrisch()

Rückgabe: -1 bei Fehlern, 0 sonst

4. Schritt: Berechnung der Anzahl der m-Ecke

T BerechneAnzahlDreiecke(T a,T b)

Berechnet die Anzahl der Dreiecke. Hierbei muß beachtet werden, daß kein Test auf innere Punkte erfolgt,deswegen vor der Benutzung unbedingt Bemerkung im Quellcode durchlesen. Es werden die Knoten bzw. Kreuzungspunkte von a bis b-1 durchlaufen.

Rückgabe: -1 bei Fehlern, Anzahl der Dreiecke sonst

T BerechneAnzahlDreiecke_allgemein(T a,T b)

Berechnet die Anzahl der Dreiecke. Dies ist eine allgemein gültige Methode, d.h. es wird auf innere Punkte getestet. Es werden die Knoten bzw. Kreuzungspunkte von a bis b-1 durchlaufen.

Rückgabe: -1 bei Fehlern, Anzahl der Dreiecke sonst

T BerechneAnzahlVierecke(T a,T b)

Berechnet die Anzahl der Vierecke mit einer allgemeinen, aber langsamen, Methode. Es werden die Knoten bzw. Kreuzungspunkte von a bis b-1 durchlaufen.

Rückgabe: -1 bei Fehlern, Anzahl der Vierecke sonst

T BerechneAnzahlFuenfecke(T a,T b)

Berechnet die Anzahl der Fuenfecke mit einer allgemeinen, aber langsamen, Methode. Es werden die Knoten bzw. Kreuzungspunkte von a bis b-1 durchlaufen.

Rückgabe: -1 bei Fehlern, Anzahl der Fünfecke sonst

T BerechneAnzahlDreiecke_o()

Berechnet die Anzahl der Dreiecke. Dies ist keine allgemein gültige Methode, d.h. es wird nicht auf innere Punkte getestet. Zwischenergebnisse werden gelöscht.

Rückgabe: -1 bei Fehlern, Anzahl der Dreiecke sonst

T BerechneAnzahlDreiecke_o_allgemein()

Berechnet die Anzahl der Dreiecke. Dies ist eine allgemein gültige Methode, d.h. es wird auf innere Punkte getestet. Zwischenergebnisse werden gelöscht.

Rückgabe: -1 bei Fehlern, Anzahl der Dreiecke sonst

T BerechneAnzahlDreiecke_o_symmetrisch()

Berechnet die Anzahl der Dreiecke. Die Rotationssymmetrie wird ausgenutzt. Aufruf ist nur mit Sektoren eines regelmäßigen n-Ecks sinnvoll. Zwischenergebnisse werden gelöscht.

Rückgabe: -1 bei Fehlern, Anzahl der Dreiecke sonst

T BerechneAnzahlDreiecke_symmetrisch()

Berechnet die Anzahl der Dreiecke. Die Rotationssymmetrie wird ausgenutzt. Aufruf ist nur mit Sektoren eines regelmäßigen n-Ecks sinnvoll.

Rückgabe: -1 bei Fehlern, Anzahl der Dreiecke sonst

T BerechneAnzahlPolygone()

Berechnet die Anzahl der Polygone. Bei beliebigen Graphen kann es im jetzigen Zustand noch zu Fehlern kommen, die aber ausgegeben werden. Die Anzahl der m-Ecke wird ausgegeben.

Rückgabe: -1 bei Fehlern, Anzahl der Polygone sonst

5. Ähnliche Fragestellungen

An dieser Stelle werden drei Folgen aus der On-Line-Encyclopedia of Integer Sequences im Orginaltext wiedergeben.

ID Number: A006600
Sequence: 1,8,35,110,287,632,1302,2400,4257,...
Name: Triangles in regular n-gon
Comments: Place n equally-spaced points on a circle, join them i all possible ways, how many triangles can be seen.

ID Number: A005732
Sequence: 1,8,35,111,287,644,1302,2430,4257,...
Name: C(n+3,6)+C(n+1,5)+C(n,5)
Comments: Place n points in general position on a circle, join them in all possible ways; how many triangles can be seen?

ID Number: A007678
Sequence: 1,4,11,24,50,80,154,220,375,...
Name: Regions in regular n-gon with all diagonals drawn.

Die Folge 1,4,10,18,35,56,90,120,176,.. , welche diesem Softwareprojekt zugrunde liegt, also die Anzahl der Dreiecke regelmäßiger n-Ecke angibt, befindet sich dagegen nicht in dieser Sammlung.
Sie hat mit der ersten Sequenz gemeinsam, daß Dreiecke regelmäßiger Polygone gezählt werden. Die Definition eines Dreiecks ist hierbei aber anders gewählt, und entspricht dem Begriff der regions aus der dritten Sequenz.

Auch die zweite und die dritte Sequenz läßt sich auf diese Weise erweitern, und man bekommt die Frage nach der maximalen Anzahl an Dreiecken. siehe [4]: 1,4,10,35,? (56..68)

6. Literatur

[1] B. Poonen, M. Rubinstein, "The number of intersection points made by the diagonals of a regular polygon", SIAM Journal of Discrete Math. Vol. 11 No. 1, p. 135-156

[2] S.E. Sommars, T. Sommars, "The number of triangles formed by intersecting diagonals of a regular polygon", Journal of Integer Sequences Vol. 1, Article 98.1.5

[3] F. Klein, "Elementarmathematik vom höheren Standpunkt aus", Dritte Auflage, p. 3-10

[4] S. Kurz, "Die maximale Anzahl von Dreiecken bei Zeichnungen von Graphen", "Jugend forscht"-Arbeit 2000/01, erhältlich unter http://www.stud.uni-bayreuth.de/~a8581/j2000d2.zip

7. Mängelliste

Die Berechnung der Anzahl der m-Ecke nutzt die Rotationssymmetrie noch nicht aus, hängt mit dem zweiten Punkt zusammen.

Die Berechnung der Anzahl der m-Ecke funktioniert noch nicht zuverlässig bei allgemeinen Graphen, d.h. man bekommt richtige Ergebnisse oder Fehlermeldungen.

Routinen zum Abspeichern von Ergebnissen in Files sind noch nicht implementiert.

Bei größeren Polygonen wird viel Speicherplatz benötigt, und auch auf gut bestückten Maschinen kommt man relativ schnell in den Bereich, wo der Rechner fast nur noch mit swap-en beschäftigt ist. Durch eine eigene Datenorganisation könnte viel Rechenzeit gespart werden.

Die symmetrische Berechnung der Schnittpunkte hat noch die Komplexität O(n^4).

Das Verschmelzen von Mehrfachschnittpunkten ist bei vielen Verschmelzungen noch zu langsam, und kann optimiert werden.

Sämtliche Methoden können noch feinoptimiert werden.

Beispiele regelmäßiger n-Ecke

regelmäßiges 6-Eck:

regelmäßiges 9-Eck:

regelmäßiges 11-Eck:

Tabellen der Anzahl der m-Ecke regelmäßiger n-Ecke

Die Tabellen stehen jeweils in einzelnen HTML-Seiten

Ein regelmäßiges 2n+1 - Eck enthält weiterhin noch genau ein (2n+1)-Eck. Andere m-Ecke gibt es, für n<=105, nicht.

Last Update: by Sascha Kurz