Halbierende Diagonale
-
Wie kann ich in einem Polygion eine Diagonale finden, so dass die zwei Polygonhälften so gut es getht gleich viele Dreiecke bei einer Triangulierung besitzen?
-
Bitte mehr Kontext. Das klingt mir nicht so, als wolltest du dieses Problem ein für alle Mal ganz allgemein lösen, sondern eher danach, als hättest du eine konkrete Anwendung. Je mehr Annahmen wir machen können, desto besser können wir helfen.
Wichtige Angaben, die fehlen:
-Wozu wird das Ergebnis gebraucht?
-Muss es die beste Lösung sein oder reicht eine halbwegs gute Lösung?
-Willst du auch konkret die Triangulierung dazu wissen? Es könnte Methoden geben, bei denen diese nebenher abfällt, diese wären dann zu bevorzugen.
-Ist es ein einfaches Polygon, ohne Löcher?
-Kann man Abschätzungen über die Größenordnung der Anzahl der Ecken machen?
-Kann man irgendwelche Einschränkungen in der Geometrie erwarten?
-Ist es gar konvex? In dem Fall wäre die Lösung ja trivial und du bräuchtest nicht fragen. Aber habe schon zu oft erlebt, das Leute überhaupt nicht nachdenken, bevor sie hier fragen, daher lieber eine eventuell unnötige Gegenfrage.
-Was immer dir sonst noch einfällt.Ganz ganz allgemein ist eine Möglichkeit natürlich einfach Brute Force. Aber das ist vermutlich nicht die beste, weder für dein konkretes Problem (wie auch immer das genau lauten mag), noch für den allgemeinen Fall.
-
SeppJ schrieb:
-Muss es die beste Lösung sein oder reicht eine halbwegs gute Lösung?
-Ist es ein einfaches Polygon, ohne Löcher?Imo sind das die beiden wichtigen Fragen. Für den Fall, dass es keine Löcher gibt und das Polygon einfach ist, kannst du auf jeden Fall eine Z rlegung im Verhältnis 1/3 zu 2/3 finden; das geht sogar wenn die Triangulierung fest vorgegeben ist: einfach den nachbarschftsgraph der dreiecke betrachten. Das ist ein Baum mit maximalem knotengrad 3. es ist nicht schwer zu zeigen, dass es eine Kante geben muss unter der ein teilbaum mit gewicht zwischen 1/3 und 2/3 des gesamten Baums hängt. Den kann man dann auch leicht in linearer zeit finden.
Um die global optimale Lösung zu finden führt vermutlich nix dran vorbei halt alle diagonalen durchzuprobieren. Dabei hilft es natürlich zu wissen, dass ein polygon mit n Knoten mit n-2 dreiecken trianguliert wird.
-
noledge schrieb:
Wie kann ich in einem Polygion eine Diagonale finden, so dass die zwei Polygonhälften so gut es getht gleich viele Dreiecke bei einer Triangulierung besitzen?
Für einen Baum zusammen mit bounding boxes auf jeder Baumebene und dadurch minimiertem Neuzeichenaufwand, wenn man durch ein Fenster nach draußen guckt?
-
Also:
Das Polygon hat keine Löcher und ist einfach. Die entstehende Trianglierung ist egal, man kann auch (wenn es keinen Vorteil hat) von keiner vorher bestehenden Triangulierung ausgehen.
Wichtig ist dass die Lösung optimal ist, dh die Anzahl der Dreiecke sollten sic in den beiden neu entstandenen Polygonen um maximal 1 unterscheiden, wenn das möglich ist.
Fall jemand schon eine funktionsfähige Lösung gepostet hat, möchte ich mich entschuldigen, ich habe noch nicht alle Ansätze hier vollständig durchgedacht
-
Das ca. 1/3 zu 2/3-Verhältnis ist im schlechtesten Fall optimal. Betrachte ein Dreieck D als Zentrum, nimm die Kanten als im Uhrzeigersinn gerichtet an. Setze auf jede der Seiten nochmal ein Dreieck drauf. Die Spitzen der neuen Dreiecke schiebst Du nun parallel zur Grundseite des Dreiecks in entlang der gewählten Richtung der Grundseite (und zwar weit genug). Der äußere Rand des entstehenden Gebildes ist Dein Polygon. Wenn Du weit genug geschoben hast, dann ist die Zerlegung in die Dreiecke, die wir für die Konstruktion verwendet haben auch die einzig mögliche Triangulierung des Polygons, weil es einfach keine anderen Diagonalen gibt. Egal welche der Diagonalen man nun zum schneiden verwendet, man hat auf einer Seite ein Dreieck, auf der anderen Seite 3. -> sogar 1 zu 4.
Natürlich kann man jetzt an jedes der äußeren Teile noch beliebige (gleich große) Polygone anfügen, ohne die Eigenschaften der Konstruktion zu verändern. Je mehr man anhängt, desto näher kommt man an die 1/3 zu 2/3-Zerlegung heran, und besser kann man offensichtlich nie werden.
Klar? Oder soll ich versuchen irgendwo ein Bild hochzuladen (wo?)
-
Vielen Dank Jester,
es sieht so aus, dass die 1/3 zu 2/3 Aufteilung tatsächlich optimal ist,
leider ^^Ich habe das zwar jetzt auch nicht ganz zu Ende gedacht und würde ein Bild auf einen beliebigen One-Click-Hoster gepostet, sehr schätzen.
Unabhängig davon bin ich auf eine Übungsaufgabe aus einem Lehrbuch zu Computational Geometry auf ein Kapitel gestoßen, in dem ein Algorithmus
vorgestellt wird, der in O(n log n) eine solche Zerteilung generiert, bei der beide entstehenden Polygone maximal floor([2/3]*n)+2 Ecken haben, was ja auf das selbe hinausläuft.
-
Hi,
ich habe kurz gemalt: http://s29.postimg.org/jhyw9eh53/drittel_beispiel.png
Das Dreieck D ist in der Mitte grau eingezeichnet. Die gestrichelten Polygone können beliebig große Restpolygone sein. Solange die gleich groß sind wirst Du immer am Dreieck D schneiden müssen, und das wird nicht besser als 1/3 zu 2/3 bzw. keine Seite größer als 2/3.
