Polygonmethode/ Voronoi-Diagramm

salbei shared this question 10 years ago
Answered

Hallo,


Zunächst einmal: ich weiß gar nicht, ob ich hier mit meiner Frage richtig bin, oder ob ich in einem Mathe-Forum besser aufgehoben wäre. Heute habe ich nämlich kein reines GeoGebra-Problem, sondern komme mit der Umsetzung nicht so recht weiter.


Ich beschäftige mich immer noch mit dem Voronoi-Diagramm. Leider zeigt mir GeoGebra das Diagramm nur als Ortslinie an. Für die Polygonmethode, die ich eigentlich umsetzen möchte, brauche ich aber die einzelnen Flächen bzw. Polygone, die die einzelnen Punkte umschließen. Die Polygonmethode ist eine Methode zur Interpolation von Geodaten. Als einfaches Beispiel: Ich habe vier Messstationen in einem viereckigen Gebiet. Diese messen den Niederschlag. Nun möchte ich wissen, wie der mittlere Niederschlag über dem Gebiet ausgesehen hat. Da das einfache arithmetische Mittel zu ungenau ist, ordne ich den Messstationen Flächen zu und mittle dann anteilig. Dazu bilde ich das Voronoi-Diagramm und ordne den Flächen den Niederschlagswert des Punktes zu, der sich in der jeweiligen Fläche befindet. Nun habe ich also die einzelnen Flächen mit Niederschlagswert und kann so den Mittelwert bestimmen. (Ich hoffe, ihr versteht, was ich sagen will...)


Ich habe nun also versucht, das Voronoi-Diagramm selbst zu konstruieren. Mein Plan dazu sieht wie folgt aus:

- Delaunay-Triangulation durchführen (das "Gegenstück" zum Voronoi-Diagramm, die Mittelsenkrechten der Delaunay-Dreiecke sind das Voronoi-Diagramm)

- Voronoi-Diagramm zeichnen

- vielleicht noch die Flächen schön einfärben (je nach Wert des Polygons)

- Flächenanteile ausrechnen und Mittelwert bilden


Punkt 1 habe ich geschafft: die Delaunay-Dreiecke. Heißt hier ListeTriang. Ich habe dazu den Folgen-Befehl genutzt. Darin werden die vorhanden Punkte zu Dreiecken miteinander verbunden, wenn kein anderer Punkt sich im Umkreis dieses Dreiecks befindet. Ich weiß, der Befehl ist sehr lang und unübersichtlich. Ich bin aber froh, dass ich es überhaupt geschafft habe :flushed: Über Verbesserungsvorschläge würde ich mich aber auch freuen.

So, nun würde ich gerne das Voronoi-Diagramm zeichnen, aber ich bin damit gerade etwas überfordert. Wie kann ich Mittelsenkrechten der Dreiecksseiten zeichnen lassen, diese dann am Schnittpunkt mit der nächsten enden lassen und dann auch noch die Flächenanteile bestimmen? Ich habe schon heraus gefunden, dass die Schnittpunkte der Mittelsenkrechten der Mittelpunkt der Dreiecksumkreise ist, aber irgendwie hilft mir das nicht weiter.


Ich hoffe, hier kann mir jemand helfen. Vielleicht gibt es ja auch eine ganz einfache Lösung und ich stehe nur auf dem Schlauch? Oder man kann mit dem Voronoi-Befehl doch mehr machen, als ich glaube?

Anbei mein bisheriger Stand, mit den Buttons können zufällige Punkte hinzugefügt oder gelöscht werden. Die Fläche, um die es geht, wäre das graue Quadrat. Das GeoGebra-Voronoi-Diagramm habe ich zur Kontrolle schon eingezeichnet.


Vielen Dank schon einmal (schon alleine fürs Lesen meines Romans hier)

Silvia

https://ggbm.at/555801

Comments (21)

photo
1

Hallo,

mit dem Voroni-Diagramm kenne ich mich noch nicht aus.

Aber zwei deiner Fragen könnte ich beantworten (wenn du sowiso nicht schon weist wie es geht).

Wie kann ich Mittelsenkrechten der Dreiecksseiten zeichnen lassen, diese dann am Schnittpunkt mit der nächsten enden lassen und dann auch noch die Flächenanteile bestimmen?
Schnittpunkt der Mittelsenkrechten eines Dreiecks:

    Schneide[ Mittelsenkrechte[ DP_{1} , DP_{2} ] , Mittelsenkrechte[ DP_{2} , DP_{3} ] ]

Fläche ermitteln lassen (welche Flächenanteile?):

    Fläche[ Punkt_{1} , Punkt_{2} , Punkt_{3} ]

-vielleicht noch die Flächen schön einfärben (je nach Wert des Polygons)
Ich weis wie das außerhalb von Folgen funktioniert, bezweifle jedoch, dass das innerhalb einer Folge möglich ist ("Ein Königreich für diese Möglichkeit!").

Hier der Link zu der Hilfeseite (ganz unten Dynamische Farben), von der ich das nötige Wissen habe.

Gruß

Loco

photo
1

Hallo Loco,


danke für deine Antwort! Wie man Mittelsenkrechten zeichnet, weiß ich ja. Nur wie kann ich die in einer Folge zeichnen lassen, zu einem Polygon verbinden und dieser Fläche dann einen Wert zuordnen? Das ich den Befehl für die Mittelsenkrechte in eine Folge packen kann, denke ich eigentlich schon. Nur wie ich dann die einzelnen Strecken zu einer Fläche verbinde und diese dann ansprechen kann, ist mir unklar. Das Ganze soll halt möglichst für beliebig viele Punkte funktionieren. Aber auch bei gleicher Anzahl von Punkten verändert sich die Anzahl der Dreiecke je nach Lage der Punkte.


Viele Grüße

Silvia

photo
1

Hallo salbei,

ja ich dachte mir schon, dass du die Befehle kennst.

Wie bereits erwähnt, kenne ich mich damit noch nicht so aus, aber ich hätte da einen Denkanstoß (wenn ich alles richtig verstehe):

Zuerst ermittelst du ja die Dreiecke (ListeTriang), hier wäre es sinnvoll die Punkte jedes Dreiecks zusammen irgendwo abzuspeichern ( LD={ {D1P1,D1P2,D1P3},{D2P1,D2P2,D2P3}, ... } ).

Dann vergleichst du ja welche Dreiecke aneinander liegen. Hier gehst du her und schaust ja nach einer Übereinstimmung mit einem anderem Dreieck in der Liste.

Wenn zum Beispiel ein Punkt in einem anderem Dreieck vorkommt, dann ermittelst du den Umkreismittelpunkt des Dreiecks und fügst diesen in eine Polygonliste ein ( LP={ {MP1,MP2, ...} , {MP2,MP4, ...} } ).

So bekommst du Polygone, wenn diese zwei gleiche Punkte haben sind sie geschlossen und du kannst den Flächenbefehl darauf anwenden.

Die Strecken die nach außen verlaufen, scheinen mir Mittelsenkrechte der äußeren Strecken zu sein. Wie die in mein Denkbild passen weis ich noch nicht.

Dummerweise scheitere ich schon daran die passenden Dreiecke zu ermitteln, sonst könnte ich dir mehr als nur meine Gedanken dazu mitteilen.

Gruß

Loco


Edit:


Nach Stunden voller Zweifel habe ich es doch geschafft.

Ich habe den von mir angedachten Weg eingeschlagen und die angehängte Datei erstellt.

Jedoch ist diese fehlerhaft, der Schneide-Flächen-Befehl scheint noch ein wenig buggy zu sein.

Zudem ist mir immer noch schleierhaft welche logische Regel ich anwenden könnte um die Punkte, für die bildverlassenden Strahlen, den jeweiligen Messpunkten zuzuweisen.

Daher kann ich leider nicht das ganze Quadrat tapezieren.

Das Zuweisen der an die Messpunkte gekoppelten Messwerte und das wertebezogene Färben funktioniert.

Jedoch nicht innerhalb einer Folge ("Ein Königreich für diese Möglichkeit!"), das müsste man evtl. über ein Script lösen.

Die Flächen werden netterweise von GGB gleich mitberechnet und ich musste sie nur noch in die Beschriftungen aufnehmen.


So das war meine gute Tat für diese Woche.

Ich hoffe die Beispiel-Datei hilft dir weiter, wenn nicht werden dir sicherlich die klügeren Forumteilnehmer helfen, ich bin leider in nächster Zeit (1 Woche) verhindert.


Edit-2:

Meine Flächenzuweisung spinnt, die Winkel der einzelnen Punkte werden manchmal falsch berechnet.

https://ggbm.at/557669

photo
1

Hallo Loco,


ich habe erst heute deine Antwort gesehen, vielen Dank für die Mühe, die du dir gemacht hast. Ich muss mich da erst mal rein fitzen, was du da genau machst. Sieht aber auf jeden Fall schon mal gut aus.

Die Strecken nach außen (so wie alle anderen Strecken auch) sind tatsächlich die Mittelsenkrechten der Dreiecksseiten (daher auch dualer Graph zu den Dreiecken). Ich habe in der Zwischenzeit eine andere Idee gehabt, die umliegenden Polygon-Eckpunkte für die einzelnen Punkte zu bestimmen. Hier mal für den Punkt A2:

    EntferneUndefiniert[Folge[Wenn[Abstand[A2, Element[ListeKreise, i]] ≟ 0, Mittelpunkt[Element[ListeKreise, i]]], i, 1, Länge[ListeKreise]]]

Bedeutet, die Kreise der anliegenden Dreiecke schneiden sich alle in dem Punkt, um den das Polygon gezeichnet werden soll. Liegt der Punkt also auf einem Kreis, so wird der Mittelpunkt dieses Kreises zur Liste hinzugefügt.


Alle nach außen verlaufende Strecken gehören zu den äußersten Punkten, die die konvexe Hülle bilden. Für die Punkte innerhalb der konvexen Hülle funktioniert also deine Version oder mein Ansatz oben. "Nur" die Punkte der konvexen Hülle müssten also anders behandelt werden. Ich hatte auch schon ein paar Geistesblitze, für die ich jedoch die Punkte der konvexen Hülle benötige. Leider erzeugt auch der Befehl KonvexeHülle nur eine Ortslinie. Ich habe es mit dem Abstand versucht: also den Abstand der einzelnen Punkte zur konvexen Hülle berechnen, ist dieser gleich Null, dann gehört der Punkt zur konv. Hülle. Leider spinnt die Berechnung bei mir und der Abstand ist mal Null, mal größer Null. Meinst du, es lohnt, diese Idee weiter zu verfolgen und die konvexe Hülle selbst zu bestimmen (wie auch immer...)?


Viele Grüße

Silvia


Nachtrag: in der angehängten Datei sieht man, was ich mit dem Abstand von Punkt A zur konvexen Hülle meine.

https://ggbm.at/557735

photo
1

Hallo salbei,

deine Lösung ist evtl. besser als meine, da bei meiner Lösung der Bezug zu den Messpunkten verloren geht und ich ihn im späteren Verlauf wieder herstellen muss.

Hier nochmal stichpunktartig mein Vorgehen in der Beispieldatei:

  • zusammenstellen aller Punkte zu einer Liste (LP)
  • ermitteln der Dreiecke (auf Grundlage dieser Definition) und speichern der Dreiecke (BDL - BDVL) (dein Vorgehen leicht modifiziert)
  • vergleichen jedes Punktes (LP) mit der Dreiecksliste (BDVL) und Übernahme der Umkreismittelpunkte bei Übereinstimmung, speichern dieser in einer Polygonliste (PL)
  • jeweils Wahl des ersten Punktes aus der Polygonliste (PL) ermitteln der Winkel zu jedem Weiterem Punkt und der Horizontalen und sortieren der Punkte nach dem Winkel (PLS) (hier spinnt GGB oder meine Regel manchmal)
  • anwenden des Vieleckbefehls auf die sortierten Polygonlisten (PLS) und gleichzeitiges schneiden mit der Begrenzungsfläche (FFlächen) (der Schneide-Befehl scheint noch ziemlich buggy zu sein)
  • ermitteln der zusammengehörenden Datenpakete (L) und Flächen (FFlächen) über den Liegt-im-Bereich-Befehl (Zuteilung)
  • erstellen der Punktbeschriftungen und erzeugen der Farbflächen per Hand (wie gesagt Farben in Folgen scheinen nicht möglich zu sein)


Nun bezüglich der konvexen Hülle (um die wirst du wohl nicht umhin kommen), hier gibt es denke ich mehrere Möglichkeiten.

Entweder du trickst und erstellst einfach ein paar äußere Punkte, so umgehst du das Problem verfälscht aber unter Umständen das Ergebnis,

oder du ermittelst die Liste der Punkte der Konvexen Hülle. Dies dürfte meiner Einschätzung nach nicht ganz einfach werden, da hier aufeinander aufbauende Folgen angewandt werden müssten(Graham Scan) (evtl. Skripting prüfen).

Eine dritte Möglichkeit wäre die Ermittlung der Punkte durch reine Logik.

Hier ein Hinweis: Alle Eckpunkte der Dreiecke (BDVL) sind durch Strecken verbunden. Die Besonderheit der äußeren Punktpaare und Strecken sind, dass sie einzigartig in der Menge der Dreiecksseiten sind.


Dass Problem mit dem Schneide-Flächen-Befehl müsste dann auch noch gelöst werden (evtl. muss das auch per Hand gemacht werden).


Wenn ich ein wenig Zeit frei machen kann, werde ich mal eine neue Datei zusammenzimmern.


Gruß

Loco


Anhang:

Nun die konvexe Hülle zu erzeugen ist nicht schwer (einfach nur Punktpaare vergleichen), das schwierige kommt erst danach.

Die Datei ist deshalb leider immer noch nicht ganz ausgereift (Flächenschnittproblem, Polygonproblem, äußere Grenzen Problem), aber ich denke du möchtest auch noch ein wenig tun.

https://ggbm.at/557803

photo
1

Hallo


Hier noch eine weitere Möglichkeit die Elemente einer Konvexen-Hülle aus gegebenen Punkten zu ermitteln.

Dieser Lösungsansatz untersucht die Abstände der Punkte aus der PunkteListe zur Ortslinie von KonvexeHülle[PunkteListe].

Die Erläuterungen sind als Text im Arbeitsblatt hinterlegt.


Leider spinnt die Berechnung bei mir und der Abstand ist mal Null, mal größer Null.

Mit Umgehungslösung, Besserung ist vermutlich erst in GGB 4.2 zu erwarten (Bug gemeldet)


Raymond

https://ggbm.at/557867

photo
1

Hallo salbei,

meine Sortierlogik der Polygonpunkte ist suboptimal, benutze die Methode von rami, diese ist effizienter und umgeht einige Fehlerquellen.

Gruß

Loco

photo
1

Hallo Raymond und Loco,


vielen Dank für die viele Mühe, die ihr euch gemacht habt.


Loco, deine Lösung sieht echt toll aus, ich brauchte erst einmal einen anderen PC um mir das alles anschauen zu können, mein Netbook fand die ganze Sache nicht so prickelnd :D Deshalb antworte ich auch erst jetzt. Ich versuche mich da jetzt durchzuarbeiten. Die Listen-Befehle muss ich erst mal verstehen... Ansonsten aber vielen Dank, ich werde mir da sicher einige Anregungen holen können.


Raymond, deine Lösung für die konvexe Hülle habe ich schon schneller verstanden :D Ich habe sie in meine Lösung eingebaut, leider scheint GeoGebra die große Anzahl von Listen nicht mehr bewältigen zu können. Wenn ich einen Punkt der konvexen Hülle nach Innen ziehe, und er so nicht mehr zur konvexen Hülle gehört, dauert die Berechnung sehr lange und die Punkte lassen sich danach auch nicht mehr "live" verschieben: ich ziehe an einem Punkt und dieser verändert seine Position erst, nachdem ich ihn wieder los lasse.


Ich habe in der Zwischenzeit eine weitere Lösung zur Bestimmung der konvexen Hülle umgesetzt: zuerst werden die beiden Punkte mit dem kleinsten und größten x-Wert ermittelt. Diese gehören ja auf jeden Fall zur konvexen Hülle. Dann werden mit den restlichen Punkten und diesen beiden Punkten Dreiecke gebildet. Befinden sich Punkte in einem Dreiecke, so gehören diese nicht zur konvexen Hülle. Das Ganze nennt sich QuickHull-Algorithmus.

    EntferneUndefiniert[Verbinde[Folge[Folge[Wenn[LiegtImBereich[Element[PktListeMitte, i], Vieleck[Element[PktListeSort, 1], Element[PktListeSort, Länge[PktListeSort]], Element[PktListeMitte \ {Element[PktListeMitte, i]}, j]]] ≟ true, Element[PktListeMitte, i]], j, 1, Länge[PktListeMitte] - 1], i, 1, Länge[PktListeMitte]]]]

PktListeMitte sind dabei die Punkte ohne größten und kleinsten Punkt. Wahrscheinlich ziehmlich umständlich, funktioniert aber. Leider tritt dabei bei mir das gleiche oben beschriebene Problem auf, wie mit der Lösung von Raymond. Ich denke, irgendwas bei meinen Listen stimmt nicht.


Da das Ganze nur zur Erklärung des Prinzips dienen und möglichst schnell laufen soll, habe ich mich jetzt dafür entschieden, die äußersten vier Ecken einfach vorzugeben und die restlichen Punkte auf die Fläche dazwischen zu beschränken. So kenne ich die konvexe Hülle und kann die Flächen leichter bestimmen. Trotzdem wurmt mich das Ganze und wenn ich demnächst etwas mehr Zeit habe, versuche ich es noch einmal mit deiner Lösung, Loco. Wie gesagt, ich muss mich da nur erst einmal hinein finden.


Vielen Dank noch einmal für die tolle Hilfe!

Silvia

photo
1

Hallo salbei,

wenn du eine Step-by-Step-Erklärung für meine Datei wünscht könnte ich eine noch nachträglich posten (ich löse gerne die Probleme bin aber meist zu faul eine Erklärung zu schreiben).


Was die Laufzeit betrifft, ich ärgere mich selbst gerade durch eine meiner Dateien welche extremste Laufzeitprobleme hat und versuche sie zu "tunen".

Ich frage ich welche die größten Laufzeitkiller sind und wie man sie wohl umgehen kann, aber das ist ein Thema für sich.


Bezüglich deines Problems, ich habe deinen neuen Code noch nicht nachvollzogen aber ich denke die Lösung von rami oder die Lösung (nur konv. Hülle) von mir dürfte günstiger sein, da du keine "neuen Objekte" erzeugst (nur eine Vermutung).

Gruß

Loco

photo
1

Hallo Loco,


eine Erklärung wäre toll, natürlich nur, wenn dir das nicht zu viel Arbeit macht!

Wegen meines neuen Codes: ich sage ja, umständlich und Raymonds Lösung ist wesentlich eleganter. Ich hatte mich nur erst einmal damit beholfen, da das für mich der am einfachsten nachvollziehbare Algorithmus war :) .

photo
1

Hallo salbei,

dann fange ich mal an. Ich gehe davon aus, dass du schon vertrauter mit GGB bist und werde deshalb nicht alles haarklein erklären.

Die Kosmetik (Texte und Farben) lasse ich mal ausen vor.


Nun zu Beginn hast du ja die Begrenzungsfläche (area) und deine Flächenpunkte (MP1 - MP6) in einer Liste zusammengefasst (Lpoints).

    area = Vieleck[(0,0),(10,0),4]

    Lpoints = {MP1, MP2, MP3, MP4, MP5, MP6}

Und deine zugehörigen Daten in der Tabelle welche ich im nächsten Befehl schon mal in einer Liste den Punkten zuweise (Ldata) (nicht essentiell).

    Ldata = Folge[{Element[ Lpoints ,k] , Element[B2:B7,k] , Element[C2:C7,k] },k,1,Länge[ Lpoints ]]

Danach beginnst du mit der Delaunay-Triangulation. Ich arbeite hier nach der Wikipediadefinition, nach der kein weiterer Punkt im jeweiligen Dreiecksumkreis liegen soll, und nach deiner Vorlage.

Ich wende hier eine vierfach verschachtelte Folge an (bestimmt geht das hier geschickter)

    Ltrian =

    EntferneUndefiniert[ Verbinde[Verbinde[

    Folge[Folge[Folge[


    Wenn[

    Summe[

    Folge[LiegtImBereich[Element[Lpoints \ {Element[Lpoints, i], Element[Lpoints \ {Element[Lpoints, i]}, j], Element[Lpoints \ {Element[Lpoints, i], Element[Lpoints \ {Element[Lpoints, i]}, j]}, k]}, t], Kreis[Element[Lpoints, i], Element[Lpoints \ {Element[Lpoints, i]}, j], Element[Lpoints \ {Element[Lpoints, i], Element[Lpoints \ {Element[Lpoints, i]}, j]}, k]]], t, 1, Länge[Lpoints]-3]

    ] ≟ 0,

    Sortiere[{Element[Lpoints, i], Element[Lpoints \ {Element[Lpoints, i]}, j], Element[Lpoints \ {Element[Lpoints, i], Element[Lpoints \ {Element[Lpoints, i]}, j]}, k]}]

    ]


    , k, 1, Länge[Lpoints] - 2], j, 1, Länge[Lpoints] - 1], i, 1, Länge[Lpoints]]

    ]] ]

Ich habe die Befehlszeile etwas auseinandergerissen, damit ein klein bisschen mehr Übersicht gewährleistet ist.

Die äußeren drei Folgen nutze ich um das Testdreieck durchzuschalten (Folgen i , j , k), sie sind um jeweils eine Einheit kürzer als die äußere Folge.

Da ich ja den Punkt welchen ich in der äußersten Folge wähle in der Folge darunter nicht mehr wählen können möchte entferne ich diesen aus der Folgenliste.

  • Punkt A = Element[Lpoints, i] (äußerste Folge i)
  • Punkt B = Element[Lpoints \ {Element[Lpoints, i]}, j] (mittlere Folge j)
  • Punkt C = Element[Lpoints \ {Element[Lpoints, i], Element[Lpoints \ {Element[Lpoints, i]}, j]}, k] ("innerste" Folge k)

Danach prüfe ich ob die übrigen Punkte der Liste in dem Kreis liegen welcher durch die Punkte A bis C bestimmt wird (Folge t).

  • Folge[ LiegtImBereich[ Element[ Lpoints \ { Punkt A, Punkt B, Punkt C}, t], Kreis[Punkt A,Punkt B, Punkt C] ], t, 1, Länge[Lpoints]-3]

Ist das nicht der Fall und die Summe der im Kreis liegenden Objekte ist Null übernehme ich die Punkte A bis C in eine Liste.

Da die Kombinationen mehrfach vorkommen entferne ich die "Duplikate" aus der Gesamtliste.

    Ltrian_{clear} = Vereinigungsmenge[Ltrian, Ltrian]

Danach vergleiche ich die Dreiecksseiten auf Einzigartigkeit um die konvexe Hülle zu erhalten.

Hierzu erzeuge ich eine Liste in der ich die drei Seiten jedes Dreiecks (Ltrian_{clear}) als Punktpaare abspeichere (Ltrian_{pairs})

    Ltrian_{pairs} = Verbinde[Folge[{Sortiere[{Element[Ltrian_{clear}, i, 1], Element[Ltrian_{clear}, i, 2]}], Sortiere[{Element[Ltrian_{clear}, i, 1], Element[Ltrian_{clear}, i, 3]}], Sortiere[{Element[Ltrian_{clear}, i, 3], Element[Ltrian_{clear}, i, 2]}]}, i, 1, Länge[Ltrian_{clear}]]]

und anschließend durch zählen die doppelten Paare entferne (Lconvex).

    Lconvex = Verbinde[EntferneUndefiniert[Folge[Wenn[ZähleWenn[x ≟ Element[Ltrian_{pairs}, i], Ltrian_{pairs}] ≟ 1, Element[Ltrian_{pairs}, i]], i, 1, Länge[Ltrian_{pairs}]]]]

Hier werden die doppelten Punkte auch wieder entfernt.

    Lconvex_{clear} = Vereinigungsmenge[Lconvex, Lconvex]

Nun erzeuge ich die einfachen Polygonlisten (umsortiert und ohne "konvexe Punkte"), wobei ich die Flächenpunkte mit der jeweiligen Punktliste "verknüpft lasse.

Hierzu prüfe ich ob ein Flächenpunkt (Lpoints)(MP) in einem der Dreiecke (Ltrian_{clear}) vorkommt, wenn dies der Fall ist füge ich den Umkreismittelpunkt des jeweiligen Dreiecks in seine "persönliche" Polygonliste ein.

    Lpoly_{inner} =

    Folge[ { Element[Lpoints, k] ,

    EntferneUndefiniert[

    Folge[Wenn[IndexVon[Element[Lpoints, k], Element[Ltrian_{clear}, i]] > 0,

    Schneide[Mittelsenkrechte[Element[Ltrian_{clear}, i, 1], Element[Ltrian_{clear}, i, 2]], Mittelsenkrechte[Element[Ltrian_{clear}, i, 2], Element[Ltrian_{clear}, i, 3]]]], i, 1, Länge[Ltrian_{clear}]]

    ] }

    , k, 1, Länge[Lpoints]]

Nun kommt der etwas unausgereifte Teil des Ganzen, und deshalb schreibe ich den hier auch nicht dazu (ich habe bemerkt, dass meine logische Zuweisung der Hüll-Punkte sehr Fehlerhaft ist)(wurmt mich).

Ich habe bisher die Mittelsenkrechte mit einem Streckenzug geschnitten und die Abstände der Punkte zu dem Mittelpunkt des Dreiecks verglichen. Dummerweise kann das Dreieck jedoch auch weiter außen liegen, sodass diese Regel hinfällig wird. Zudem könnte man die Eckpunkte der Grenzfläche mit aufnehmen, dies wird dann aber noch komplizierter (8 oder mehr Fallunterscheidungen)(und habe ich bisher auch nicht gemacht).


Wenn du nun alle Punkte eines Polygons ermittelt hast, dann wende erst auf diese die Sortierregel von rami an und dann auf die sortierten Punkte den Vieleck-Befehl.


Wenn mir eine passende Lösung zur Zuweisung der äußeren Punkte zu den jeweiligen Polygonen einfällt ergänze ich den Post (wurmt mich echt, dass ich keine Komplettlösung bieten kann).


Gruß

Loco


https://ggbm.at/557935


Edit:

Ach ja, ich bin hier auf etwas interessantes gestoßen: You-Tube-Link

Es hat scheinbar schon jemand ein Voronoi-Diagramm eingefärbt nur auf ganz andere Weise. Ich habe jedoch keine Ahnung wer und wo man die Datei findet.

photo
1

Hallo


Hier ein vollständig anderer Lösungsansatz für die Triangulation.

Er basiert auf der Ortslinie von DelaunayTrinangulation[] und extrahiert daraus die Kanten der Ortslinie und die dazugehörigen Dreiecke.Zusätzlich wird die Hüllkurve gebildet sowie die Kanten auf der Hüllkurve.

Das Ganze liegt auch als Makro (Benutzerwerkzeug) vor, auf der dann aufbauend die Voronoi-Elemente (nicht Ortslinie) extrahiert werden können.


Der Vorteil dieses Lösungsweges ist, dass er exakt dem Delaunay-Algorithmus folgt (Annahme kein Bug in DelaunayTrinangulation[]), was bei der 'händischen' aber genialen Variante von salbei nicht immer der Fall ist. Auch scheint mir, dass die Perfomance besser ist (weniger Listen-Elemente).


Die Erläuterungen findet man Im Arbeitsblatt.

Die Basis zur Makro und das Makro selbst ist im Anhang.


-------------------


Mit der darauf aufbauenden Voronoi-Funktion habe ich mich auch bereits befasst. Bugs in GGB haben die Weiterarbeit stark beeinträchtigt. Ich suche nun nach einem neuen Lösungsweg, der (ebenfalls) die Ortslinie Voronoi[] mit einbezieht.


Die Grundidee ist wie folgt:

Bilde die Vornoi-Knoten (Methode salbei)

Extrahiere aus diesen in Kombination mit der Ortslinie von Voronoi[] die Kanten (Methode rami in DelaunayAndHull). Bilde den Schnittpunkt jener Kanten, die die Hülle verlassen und kürze die entsprechende Kante bis zur Hülle.

Zwischen den Punkten auf eine Hüll-Kante (inkl. Eck-Hüllpunkte) werden zusätzliche Voronoi-Kanten gebildet.

Allenfalls müssen noch weitere Kanten (für Punkte mit nur 1 oder 2 Kanten) konstruiert werden.

Falls ja: Es gilt die Senkrechte auf jene Hüll-Kante, deren Mittelsenkrechte diesen Punkt schneidet.


Nun müssen die Kanten noch einem der gegebenen Punkte (Messstationen) zugeordnet werden um daraus das Polygon zu bilden, dessen Fläche (für Gewichtung der Messresultate) interessiert:

Ich denke dass das Zuordnungskriterium wie folgt gegeben ist (erst gedanklich 'codiert'):

- Die Kante hat einen gemeinsamen Punkt mit einem Eckpunkt auf der Hülle

- Die Mittelsenkrechte einer (ungekürzten) Kante trifft auf einen der gegebenen Punkte.


-----------------------------


Kein Königreich aber ein kleines Fürstetum für das Einfärben der Polygone (nur als Idee, nicht erprobt).

In zwei Listen sind einerseits die Polygone und andereseits die Farbcodierungen hinterlegt

OnUpdat dieser Liste werden die Polygone in die Spalte A (Spalte Nr 1) der Tabelle übertragen.

Zusätzlich wird die Farbcodierung den Polygonen in der Tabelle zugeordnet. Dies geschieht (grob und ungeprüft) in folgendem Script-Befehl in OnUpdate PolygonListe:

Execute[Verbinde[Zip[{"SetzeWert[Zelle[1,"+n+"],"+P+"]","SetzeFarbe[Zelle[1,"+n+","+F+"]"}],P,PolygonListe,F,Farbliste,n,Folge[Länge[PolygonListe]]]]


-----------------------------


Weiterhin viel Spass beim knobeln um das Unmögliche mit GGB möglich zu machen.


Raymond

https://ggbm.at/557937

https://ggbm.at/1390957

photo
1

Hallo,


ihr wart ja fleißig hier :o Ich werde mir das alles in den nächsten Tagen mal in Ruhe anschauen, wie gesagt, dass lässt mir keine Ruhe :)


Der Youtube-Link: das sieht für mich aus wie der sweep-line- Algorithmus. Das bunte ist die Spur von den "Wellen". So etwas ähnliches, nur mit Kreisen die sich überschneiden, habe ich auch schon gefunden und umgesetzt. Ist recht einfach, aber mehr so eine nette Spielerei: beim Verschieben der Punkte bleibt die Spur, also die Farbe, an ihrem alten Platz. Sieht aber dennoch nett aus.

https://ggbm.at/557939

photo
1

Hallo


Der sweep-line- Algorithmus hat mich auf folgende Idee gebracht.


https://ggbm.at/557951


Uebrigens:

Ich vermute stark (auf Grund folgenden Beispiels), dass eine Voronoi-Kannte nicht immer auf

der Strecke zwischen den Umkreis-Mittelpunkten von zwei benachbarten

Triangulations-Dreiecken liegt. (Dann nicht, wenn sich so konstuierte Voronoi-Kanten

shneiden würden).


(rote Strecken=konstruiert, gestrichelt Schwarz=Voronoi[], hellblau=DelaunayTriangulation[]

23976bfa83c46547dc7345982f52cbad


Raymond

photo
1

Hallo rami,

ich habe die Punktekoordinaten oder die Datei nicht vorliegen, daher kann ich es nicht genau überprüfen,

aber mir scheint, dass das untere Dreieck (DCG?) nicht zulässig ist da F(?) mit im Umkreis des Dreiecks liegt.

Gruß

Loco

8e010a43e5e7a5e40532868bb83a874a

photo
1

Hallo Loco,


mir scheint, dass das untere Dreieck (DCG?) nicht zulässig ist

Dann hätte die Ortslinie von DelaunayTriangulation[] einen diesbezüglichen Bug (was ich nicht glaube)


Als Beilage das entsprechende Arbeitsblatt

Eigentlich ein fast fertiger Zwischenstand (es fehlt noch die Polygon-Bildung mit den Voronoi-Kanten) aber eben ein Zwischenstand, der genau im angesprochenen Fall leider falsch ist.


Zur Zeit bin ich dabei den eingeschlagenen Weg (zu Hilfe Nahme der Voronoi-Ortslinie) weiter zu verfolgen (nicht zuletzt auch aus Performance-Gründen).

Den hier (Voronoi03B) eingeschlagenen Weg will ich augenblicklich nicht weiter verfolgen (Aber vielleicht findest Du den Knackpunkt, denn ohne Ortslinie wäre es hübscher).


Raymond

https://ggbm.at/557961

photo
1

Hallo rami,

ich möchte meine Ansicht auch bezweifeln aber laut Definition ist das ein "Fehler-Dreieck".

Deshalb scheint es so, dass du einen der seltenen(?) GGB-Bugs gefunden hast.

Wikipedia - Delaunay-Triangulation[/url]"]In einer Delaunay-Triangulation erfüllen alle Dreiecke des Dreiecksnetzes die sogenannte Umkreisbedingung: Der Umkreis eines Dreiecks des Netzes darf keine weiteren Punkte der vorgegebenen Punktmenge enthalten. Dadurch weisen die Dreiecke des Netzes möglichst große Innenwinkel auf; mathematisch gesprochen wird „der kleinste Innenwinkel über alle Dreiecke maximiert“. Diese Eigenschaft ist in der Computergrafik sehr erwünscht, denn sie minimiert Rundungsfehler.

Die Delaunay-Triangulation ist nicht eindeutig, falls auf einem Umkreis mehr als drei Punkte liegen, d. h. der Anwender kann sich beliebig aussuchen, welche drei Punkte er zu einem Dreieck verbindet.

Wolfram Mathworld - Delaunay Triangulation[/url]"]The Delaunay triangulation is a triangulation which is equivalent to the nerve of the cells in a Voronoi diagram, i.e., that triangulation of the convex hull of the points in the diagram in which every circumcircle of a triangle is an empty circle (Okabe et al. 1992, p. 94).
Wenn ich salbeis oder meinen Algorithmus auf die Punktliste anwende bekomme ich andere Dreiecke und Mittelpunkte welche mit der Voronoi-Ortslinie übereinstimmen.

232fc0cabfdb6deb7b7e65755a8bdd8b(Rote Linie: Triangulation-GGB ; Schwarze Strichlinie: Eigenalgorithmus)


Gruß

Loco

photo
1

Hallo Loco


Ja das ist es, besten Dank.

Ich werde das jetzige Makro begraben und die salbei/Loco Methode für die Triangulation wieder hervorholen und sie tunen. Sodass ich mit Voronoi03 weiter darauf aufbauen kann.


Ich werde noch (bei Gelegenheit) eine Bug-Meldung absetzen.


Nun, das Fragezeichen bezüglich seltene GGB Bug's ist durchaus begründet. Es war schon schlimmer aber für meinen Geschmack auch heute noch knapp unter der Schmerzgrenze.


Raymond

photo
1

Hallo rami,

nur ein Denkanstoß, da ich mich für einige Zeit erstmal mit einer anderen Sache befassen muss.


Meine Eigenmethode probiert jedes erdenkliche Dreieck in der Punkmenge aus.

Das sind n^n (?) Möglichkeiten somit muss GGB für mehr Punkte mehr Möglichkeiten checken.

Zudem kann jedes Dreieck (ABC - BCA - CAB -....) auf mehrere Weisen gelesen/gespeichert werden,

das erklärt dann auch die hohe Zahl an "Klonen" vor der "Vereinigung".


Entweder man macht diesen Algorithmus effizienter oder man sucht sich einen anderen (wenn ich mich recht entsinne gibt es noch andere).


Over and Out (zumindest hier für eine Weile)

Loco

photo
1

Hier mein neuer Zwischenstand (zur Delaunay-Triangulation und Hülle)

Einigermassen effizient kann man das ganze programmieren, wenn

mit 'indirekten Indizies' gearbeitet wird (trotz der Brut-Force Methode).


Indirekte Indizies:

Ein Objekt verweist auf ein Objekt, das den Index zum eigentlichen

(physischen) Objekt beinhaltet.


Die Kommentare sind im Algebrafenster :exclamation:

Ich verwende praktisch ausschliesslich Zip[]

Die Namens-Konventionen bewirken, dass man den

Code von Oben nach Unten lesen kann.


Vom gewählten Programmierstil erhoffe ich mir, dass

ich meinen eigenen Code nach meinen Ferien immer

noch verstehe.


Nach meinen Ferien (ca. 2 Wochen) werde ich wieder

an dieser Problemstellung weiter arbeiten.


Raymond


PS:

Die Fehlermeldung zu 'DelaunayTriangulation[<list>]'

habe ich abgesetzt. Eine Korrektur ist erst mit 4.2 zu

erwarten.

http://www.geogebra.org/forum/viewtopic.php?f=8&t=28671

https://ggbm.at/557991

photo
1

Hi,


mit Execute kann man nur Englische Komandnamen nutzen.

Falsch: Execute[Verbinde[Zip[{"SetzeWert[Zelle[1,"+n+"],"+P+"]","SetzeFarbe[Zelle[1,"+n+","+F+"]"}],P,PolygonListe,F,Farbliste,n,Folge[Länge[PolygonListe]]]]


Richtig: Execute[Verbinde[Zip[{"SetValue[Cell[1,"+n+"],"+P+"]","SetColor[Cell[1,"+n+","+F+"]"}],P,PolygonListe,F,Farbliste,n,Folge[Länge[PolygonListe]]]]


Gruss,

Zbynek

© 2022 International GeoGebra Institute