#03: "Kreisschnitt", Geschwindigkeit, 17.02.2008

1
…
- 2
- 3
- 4
5
6
7
8

Werbeanzeige

CodingCat

1x Contest-Sieger

Beiträge: 420

Beruf: Student (KIT)

07.02.2008, 08:48

C-/C++-Quelltext

// zwei sehr sehr große Kreise, die sich irgendwo mandelförmig schneiden (Worst Case)

TestCase tc16; 
tc16.circles.push_back(Circle(96.0, 86.682671, 100.0)); 
tc16.circles.push_back(Circle(-56.0, -43.3, 100.0)); 
tc16.correct_result = 0.000598545;
test_cases.push_back(tc16);

Kann irgendjemand dieses Referenzergebnis bestätigen?

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

07.02.2008, 09:54

Wieso ist das "worst case"?

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

CodingCat

1x Contest-Sieger

Beiträge: 420

Beruf: Student (KIT)

07.02.2008, 10:26

Weil die Schnittfläche grenzwertig klein ist (zumindest für Näherungsalgos) und dabei auch noch extrem geformt (Kreise haben Radius von 100).

Zum Seitenanfang

rklaffehn

Treue Seele

Beiträge: 267

Wohnort: Braunschweig

07.02.2008, 12:08

Die Schittfläche zweier Kreise lässt sich mit einer geschlossenen Formel berechnen:

Weisstein, Eric W. "Circle-Circle Intersection." From MathWorld--A Wolfram Web Resource.
http://mathworld.wolfram.com/Circle-CircleIntersection.html

Damit ist der Fall einfach.

God is real... unless declared integer.
http://www.boincstats.com/signature/user_967277_banner.gif

Zum Seitenanfang

CodingCat

1x Contest-Sieger

Beiträge: 420

Beruf: Student (KIT)

07.02.2008, 12:31

Du meinst, verschiedene Algos für verschiedene Fälle? Es ist ja nicht wie in deinem Artikel gegeben, dass sich alle Kreise immer in einem Punkt schneiden. Allerdings wäre das natürlich durchaus eine Möglichkeit, diese Formel für den Sonderfall zweier Kreise zu implementieren. Für zwei Kreise habe ich das Problem jetzt aber bereits gelöst.

Zum Seitenanfang

rklaffehn

Treue Seele

Beiträge: 267

Wohnort: Braunschweig

07.02.2008, 17:27

Eigentlich wollte ich nur sagen, dass man die Fläche gut berechnen kann, wenn man nur zwei Kreise hat, die sich wirklich schneiden.

Damit kann man sich dann eine (hinreichend) exakte Lösung für Testfälle basteln

Als Sonderfall im Algorithmus macht das vermutlich nicht viel Sinn, weil das bei bis zu 10000 Kreisen ein sehr seltener Randfall sein wird. Schaden kann es aber auch nicht

God is real... unless declared integer.
http://www.boincstats.com/signature/user_967277_banner.gif

Zum Seitenanfang

CodingCat

1x Contest-Sieger

Beiträge: 420

Beruf: Student (KIT)

07.02.2008, 18:34

Jo, kommt drauf an, wo der Schwerpunkt beim Testen liegt, wobei vermutlich bei Geschwindigkeit wieder die Verarbeitung vieler Kreise im Mittelpunkt steht. Für Referenzlösungen ist das natürlich durchaus eine feine Sache, um die Korrektheit zu überprüfen - wobei ich da dann jetzt doch lieber faul die Auflösung der Näherung hochdrehe. ;-)

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

15.02.2008, 22:09

So, jetzt habe ich meinen in der Theorie 100% exakten Algorithmus endlich, nach vielen Versuchen, hingekriegt - glaube ich jedenfalls. Ich habe ihn zunächst mal in C# implementiert (morgen dann C++ ...) und zum Testen ein kleines Programm mit GUI geschrieben. Probiert's doch mal aus. Wenn jemand einen Fehler in meinem Algorithmus findet, wäre ich sehr dankbar, wenn er ihn mir mitteilen würde!

Für die Bewertung brauchen wir schließlich auch einen verlässlichen korrekten Algorithmus, um die Referenzlösungen zu berechnen.
Die grafische Ausgabe lässt vielleicht schon erahnen, wie der Algorithmus funktioniert. Es wird sicher interessant sein zu sehen, wie viele verschiedene Ansätze es hier gibt. Die beiden, die ich bisher bekommen habe, sind jedenfalls völlig verschieden von dem, was mir bisher so durch den Kopf gegangen war.

Hier der Link zum Programm (.NET-Framework wird benötigt - ich glaube, es ist Version 2):
https://www.spieleprogrammierer.de/contest/03/kreisschnitt.exe

Zur Geschwindigkeit kann ich noch nichts sagen - einerseits, weil es C# ist und andererseits, weil ich noch nicht gut optimiert habe. Ich vermute allerdings, dass CodingCat schneller sein wird ...

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Anonymous

unregistriert

16.02.2008, 10:05

Zitat von »"David Scherfgen"«

So, jetzt habe ich meinen in der Theorie 100% exakten Algorithmus endlich, nach vielen Versuchen, hingekriegt - glaube ich jedenfalls. Ich habe ihn zunächst mal in C# implementiert (morgen dann C++ ...) und zum Testen ein kleines Programm mit GUI geschrieben. Probiert's doch mal aus. Wenn jemand einen Fehler in meinem Algorithmus findet, wäre ich sehr dankbar, wenn er ihn mir mitteilen würde!

Tja, wie ich schon mal im Channel sagte, das ist diesmal etwas zu kompliziert geraten. Ich kann mich noch nicht wirklich durchringen, damit anzufangen. Schliesslich soll es Spass machen und nicht in Arbeit ausarten. f'`8k

Gruß, TGGC (making great games since 1992)