spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hi,
also ich finds schonmal gut, dass das Problem einigermaßen schwer ist und vielleicht sogar der mit dem besten Algo gewinnt, und nicht jemand mit irgendwelchen Assemblertricks.
Ich finds nur etwas erschreckend, dass mir so auf Anhieb keine exakte einfache Formel dafür einfällt... und ich wollt auch nicht gleich mit Integralen auf Spatzen schießen.

Aber ich hab auch noch nicht lang nachgedacht, mal gucken, ob ich noch Zeit finde...

So, ich hab schonma erste Ergebnisse.

Habe das ganze mittels Monte-Carlo gelöst.
Hier mal die Ergebnisse:




Laufzeit: 0.849s

Hm, ma n neuen run gemacht.

0.0005 Sekunden mit den Testcases die David erstellt hatte.

Zitat von »"rootnode"«

Hm, ma n neuen run gemacht.

0.0005 Sekunden mit den Testcases die David erstellt hatte.

Da schließe ich mich an. Allerdings sind die Testcases zu klein! Wir brauchen größere. Die Schwankungen in den Messzeiten sind zu hoch.

Testcases her!

Ich habe mal einen analytischen Ansatz verfolgt. Bei der Komplexität bin ich mir noch nicht schlüssig. Das hängt ganz davon ab, wie sich die Anzahl der Kreisbögen, die die Kontur des Schnittes bilden, in Abhängigkeit von der Anzahl der geschnittenen Kreise verhält.

Wenn der Zusammenhang proportional ist, dann fällt mein Algorithmus in die Klasse O(n^2 + n).
Allerdings gibt es - zumindest für überschaubare Beispiele Anordnungen, bei denen die Anzahl Konturkreisbögen stärker zunimmt, als die Anzahl der verschnittenen Kreise.

Beispiel:
Ich wähle eine Grundform, die sich aus x identischen Kreisbögen zusammensetzt, so wie es z.B. in Testfall 7 (vier gleich große Kreise auf einem Quadrat angeordnet) der Fall ist. Vier Kreise bilden da einen Schnitt, der durch vier gleiche Kreisbögen begrenzt ist.
Wenn ich nun einen Kreis in der Mitte platziere, dessen Radius nicht an die "Ecken" heran reicht, wohl aber über die Seiten hinaus geht, vergrößert man mit diesem fünften Kreis die Anzahl der Kreisbögen der Kontur des Schnittes um 4 auf 8.
Ich bin mir relativ sicher, dass sich solche Spielchen nicht beliebig fortsetzen lassen, aber eine schlüssige Herleitung einer Obergrenze will mir nicht gelingen :?

Über Denkanstöße würde ich mich sehr freuen !

Ich hab auch mal kurz geschaut...

Ich liege ca bei O(s*n+n), wobei s die Anzahl der Samples ist (ca 200 reichen). Da s eine Konstante ist, wäre das O(n).
Bin ma gespannt was für Ergebnisse so noch kommen.

Nicht schön, aber selten:

Der rote Kreis verdoppelt die Anzahl der den Schnitt begrenzenden Kreisbögen von 4 auf 8.
Oder - anders herum betrachtet - kappt jeder der großen Kreise ein kleines Stück vom kleinen roten ab. Bei n Kappungen und den nochmals n zwischen diesen liegenden Abschnitte des roten Kreises ergeben sich 2*(n-1) Kreisbögen.