Auswertung und Lösungen des Contests #03: "Kreisschnitt"

Einsendungen

Folgende Personen haben eine Lösung eingereicht:

Der legendäre exakte Algorithmus

Zur Bestimmung der korrekten Werte habe ich einen sehr langsamen (im schlimmsten Fall liegt er sogar in O(N4)), aber zuverlässigen Algorithmus implementiert. Er kann hier heruntergeladen werden und funktioniert wie folgt …

Die Schnittfläche der Kreise ist stets konvex. Man kann sie aus der Fläche eines konvexen Polygons, dessen Eckpunkte die Schnittpunkte der Kreise sind, und einem Kreissegment pro Kante berechnen. Das haben auch Andere erkannt und dies bei ihren Implementierungen ausgenutzt.

Es werden die Schnittpunkte bestimmt, die in allen Kreisen liegen. Diese Punkte bilden die Eckpunkte der gesuchten Fläche. Als Nächstes wird ein beliebiger Punkt innerhalb der Fläche bestimmt, und die Punkte werden gegen den Uhrzeigersinn um diesen Referenzpunkt sortiert. Das ist nötig, um die Fläche des Polygons berechnen zu können, die einen Teil der Gesamtfläche ausmacht.

Nun muss noch die Fläche der Kreissegmente an den Polygonkanten bestimmt werden. Dazu wird für jeden der Schnittpunkte in einer Menge vermerkt, welche Kreise an ihm beteiligt sind. Das sind im Normalfall nur zwei, aber wenn sich mehrere Kreise an derselben Stelle schneiden, enthält diese Menge mehr als nur zwei Einträge. Um nun herauszufinden, von welchem Kreis das Segment an einer Kante stammt, werden alle Kreise in Betracht gezogen, die jeweils an beiden Punkten der Kante beteiligt sind. Das Kreissegment mit der kleinsten Fläche ist dann das Gesuchte. Wichtig bei der Auswahl des kleinsten Segments ist, dass die Richtung der Kante beachtet wird.

Nachdem die Flächen der Kreissegmente zur Fläche des Polygons addiert wurden, liegt das Ergebnis vor. Der Algorithmus behandelt noch ein paar Spezialfälle, die man sich aber am besten im Quellcode selbst anschaut.

Hier gibt es noch ein Programm (in C# geschrieben), das meinen ursprünglichen exakten Algorithmus demonstriert, der aber leider auf Grund von Genauigkeitsproblemen beim Schnitt vieler Kreise im selben Punkt verworfen werden musste.

Das Testverfahren

Die Lösungen mussten sich zunächst einigen vordefinierten Tests unterziehen, von denen ein Großteil bereits in der Vorlage gegeben war. Anschließend folgten eine Million zufällige Tests mit jeweils 2 bis Kreisen, die sich schneiden oder auch nicht. Bei ungefähr der Hälfte der Tests wurden für die Kreiskoordinaten und die Radien nur ganzzahlige Werte verwendet. Gerade hier entstehen nämlich häufig Probleme, die bei zufälligen Fließkommazahlen so gut wie nie auftreten. Die Lösung von Stefan Seegel musste bei dieser Testphase leider ausgelassen werden, weil sie scheinbar in eine Endlosschleife gerät. Die Toleranz wurde, damit dieser Contest nicht ohne Gewinner ausgeht, von 0.0005 auf 0.005 angehoben.

Das Testprogram kann hier heruntergeladen werden. Benötigt wird dafür noch die Datei random.h, in der die Implementierung eines Mersenne Twister-Zufallsgenerators enthalten ist.

Testausgabe

Teste Korrektheit mit vordefinierten Tests:
Teste Funktion von big_muff: ..........F..F..... - Fehlerhaft
Teste Funktion von CodingCat: ................... - Korrekt
Teste Funktion von Helmut: ................... - Korrekt
Teste Funktion von Phili: ..........FFFF..F.. - Fehlerhaft
Teste Funktion von rootnode: ..........F..F..... - Fehlerhaft
Teste Funktion von Stefan Seegel: ................F.. - Fehlerhaft

Teste Korrektheit mit 1000000 Zufallstests:
Teste Funktion von big_muff: Fehler bei #8202
Teste Funktion von CodingCat: Fehler bei #31
Teste Funktion von Helmut: Korrekt
Teste Funktion von Phili: Fehler bei #30
Teste Funktion von rootnode: Fehler bei #8202

Das Fehler-Log, das die detaillierten Umstände der aufgetretenen Fehler enthält, gibt es hier.

And the Winner is …

Damit hat Helmut die einzige funktionierende Lösung abgeliefert und ist – oh, welche Überraschung – der Gewinner dieses Contests! Ich danke ihm und den anderen Teilnehmern dafür, dass sie sich an dieser doch recht schwierigen Aufgabe versucht haben, und kann versichern, dass der nächste Wettbewerb wieder einfacher wird.