Ergebnis 1 bis 7 von 7

Thema: [DugJC] - 07 - Algorithmische Geometrie

  1. #1
    Moderator
    Nothing is unbreakable!

    Registriert seit
    Jul 2003
    Beiträge
    622
    Renommee
    819

    [DugJC] - 07 - Algorithmische Geometrie

    Hallo,
    meine Challenge startet dann in 2 Wochen, damit Chb seine noch feritg machen kann. Am Montag den 15.08 werd ich dann meine Aufgaben posten.
    Es geht wie der Titel schon sagt in Richtung Algorithmische Geometrie. Viel zu Programmieren wird es nicht geben, damit man es auch in 2 Wochen schafft.

    Bis dann.

  2. #2
    Moderator
    Nothing is unbreakable!

    Registriert seit
    Jul 2003
    Beiträge
    622
    Renommee
    819

    Re: [DugJC] - 07 - Algorithmische Geometrie

    Hallo und guten Morgen,
    aus Zeitgründen werd ich meine Challenge jetzt schon starten. Besser ein Tag zu früh als ein Tag zu spät. Wenn ihr Fragen habt, dann fragt. Alles weitere steht in der Aufgabenbeschreibung, die leider 4 Seiten lang geworden ist
    Aber keine Angst. Das meiste davon sind nur nebensächliche Informationen und Bilder

    Also, haut rein und lasst es mich wissen, wenn ihr wo nicht weiter kommt.
    Angehängte Dateien Angehängte Dateien

  3. #3
    Registered User
    Registriert seit
    Jul 2003
    Beiträge
    249
    Renommee
    520

    Re: [DugJC] - 07 - Algorithmische Geometrie

    Gude,

    ich habe eine Rückfrage zu Aufgabe 1: Heißt "über eine Kante verbunden", dass die Dreiecke eine gemeinsame Kante haben müssen? Oder sind auch Dreiecke, die nur einen gemeinsamen Punkt haben Nachbarn?

    Und eine Anmerkung zu Aufgabe 2: Nicht jeder Graph ist so, wie die Aufgabe es vorsieht, nummerierbar:
    Wenn Dreiecke nur Nachbarn sind, wenn sie eine gemeinsame Kante haben, ist z.B. der Graph der aus den Dreiecken 0,1,2,7 besteht nicht so nummerierbar, dass man durch hochzählen von Nachbar zu Nachbar springen kann.

    Wenn auch gemeinsame Punkte aus Dreiecken Nachbarn machen, wäre es der Graph, der aus den Dreiecken 4,10,14,17 besteht. (Ich beziehe mich dabei immer auf die Abbildung aus Aufgabe 2)
    thx 4 reading

  4. #4
    Moderator
    Nothing is unbreakable!

    Registriert seit
    Jul 2003
    Beiträge
    622
    Renommee
    819

    Re: [DugJC] - 07 - Algorithmische Geometrie

    Hallo,

    Ja. Nachbar ist nur, wer über eine gemeinsame Kante verbunden ist. Dreiecke mit nur einem gemeinsamen Punkt wird es nicht geben.

    Das führt, wie du richtig erkannt hast, dazu, dass der Graph nicht durchgängig nummerierbar ist. Man landet sozusagen in einer Sackgasse. Aber das ist gewollt und nicht weiter schlimm.
    DIe Fragt ist, wie man die Nummerierung sinnvollerweise fortsetzt und wie man das implementieren könnte.

  5. #5
    Administrator
    Registriert seit
    Apr 2004
    Beiträge
    754
    Renommee
    1274

    Re: [DugJC] - 07 - Algorithmische Geometrie

    *bump*?

  6. #6
    Moderator
    Nothing is unbreakable!

    Registriert seit
    Jul 2003
    Beiträge
    622
    Renommee
    819

    Re: [DugJC] - 07 - Algorithmische Geometrie

    Ja ich wollt noch bissel warten ob sich doch noch jemand meldet. Aber naja, werd mal die Lösung heute mittag runter tippen.

  7. #7
    Moderator
    Nothing is unbreakable!

    Registriert seit
    Jul 2003
    Beiträge
    622
    Renommee
    819

    Re: [DugJC] - 07 - Algorithmische Geometrie

    So, hier mal die Auflösung.

    Aufgabe1
    =======

    In der ersten Aufgabe war gefragt, wie man die Nachbar Elemente eines Elements bekommt.
    Die Elemente sind über Kanten miteinander verbunden. Und eine Kante besteht aus zwei Knoten.
    Die Brutefoce Lösung wäre folgende:
    Man nehme ein Element und zwei seiner Knotennummern. Nun durchsuche man alle anderen Elemente ob sie auch diese zwei Knotennummern haben. Das müsste eine Quadratische Laufzeit haben, da man jedes Element mit jedem Element vergleicht.

    Aber besser ist es zu Wissen, statt zu Suchen. Beim Einlesen der Elemente hat man die Assoziation Element - Knoten. Also jeder Knoten weiß nun, an welchen Element er angeschlossen ist. Und jedes Element kennt seine Knoten.
    Man nehme also ein Element und davon seine Knoten. Nun durchsuche man alle an den Knoten angeschlossene Elemente, ob sie zwei identische Knotennummern haben.

    Die Laufzeit ist jetzt deutlich besser als n^2. Praktisch spürt man das auch deutlich.
    In einem Test von mir war dieser Algo. 7000mal schneller.

    Man kann das natürlich noch weiter treiben und beim einlesen der Daten Kanoten-Objekte erstellen. So kennt dann jedes Element seine Kanten, und die Kante seine zwei Elemente und schon hat man die Nachbarschaft.

    Aufgabe 2
    ========

    In der 2. Aufgabe sollten die Elementnummern neu angeortnet werden. Da ja nun jedes Element seine Nachbarn kennt, kann man sich so durch das Netz navigieren.
    Eine Sortierung wäre z.b. die Folgende:
    Man sucht den Knoten mit den niedrigsten x und y Werten und fängt bei dem Element an, welches mit diesem Knoten verbunden ist.
    Da das Element seine Nachbar kennt, soll es auch entscheiden welches als nächstes genommen wird. Es ermittelt also nun den Schwerpunkt der Nachbarelemente und nimmt das, mit dem niedrigsten Y Wert und dem größten X Wert.
    Gibt es kein Nachbar auf der rechten Seite, wird eben der auf der linken Seite genommen.
    Hat man sich für ein Nachbar entschieden, bekommt er eine fortlaufende neue Nummer.
    So durchwandert man das Netz immer hin und her.

    Probleme gibt es, wenn es keine Nachbarn gibt, die man noch nicht besucht hat. In meinen Beispieldatein ist so ein Fall vorgesehen. Wenn man das Netz als Labyrinth betrachtet, ist das einfach eine Sackgasse. Man geht also zur nächsten Kreuzung zurück.
    Man erstellt sich also eine Liste der Elemente die man besucht hat. Sozusagen der rote Faden den man nur wieder aufwickeln muss.

    Aufgabe 3
    ========

    Hier sollen Randknoten des Netzes gefunden werden. Ein Rand kann man durch eine Kante definieren, an der nur ein Element hängt. Erinnert euch an Aufgabe 1.

    Eine andere Möglichkeit besteht darin, einen Knoten Informationen über seine Nachbarknoten zu geben. Dann kann man den Winkel bestimmen zwischen 2 Knoten. Ist die Summe kleiner als 360Grad, ist es ein Randknoten.

    Oder man nimmt die Anzahl der angeschlossenen Knoten und Elemente. Und vergleicht sie.

    Aufgabe 4
    ========

    In der 4. Aufgabe soll der Rand des Netzes gefunden werden. Der Rand besteht aus zusammengesetzte Kanten bzw. Knoten. Da ja nun jeder Knoten seine angeschlossenen Knoten, Kanten und Elemente kennt. Und die Knoten wissen, ob sie zum Rand gehören, sollte es ein leichtes sein, diese Aufgabe zu lösen.

    Bei Fragen, einfach fragen.

Aktive Benutzer

Aktive Benutzer

Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)

Ähnliche Themen

  1. [DugJC] - 04 - SecQuiz
    Von Rodnox im Forum Contest Forum
    Antworten: 13
    Letzter Beitrag: 09.06.2011, 12:58
  2. Einführung Algorithmische Mathematik
    Von accessd im Forum Naturwissenschaften & Elektronik
    Antworten: 9
    Letzter Beitrag: 05.10.2009, 18:12
  3. Geometrie --> Mathe...
    Von bysnake im Forum Technisches Off-Topic
    Antworten: 5
    Letzter Beitrag: 27.05.2004, 19:16
  4. Festplatten-Geometrie, anzahl der addr. Sektoren
    Von Format C: im Forum Algorithmen und sonstige Programmiersprachen
    Antworten: 0
    Letzter Beitrag: 09.12.2003, 00:54
  5. [Mathe/Geometrie]Polarkoordinaten
    Von Emergency_ROM im Forum Naturwissenschaften & Elektronik
    Antworten: 16
    Letzter Beitrag: 08.11.2002, 10:35

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •