WPC-Aufgabe (Programmierwettbewerb)

Jester

Der angegebene Testcode läßt sich nicht gut einbauen, weil wir die Folgen nicht wirklich sortieren (ich zumindest nicht). Es werden nur die nötigen Kosten berechnet. Ich bin mir aber sehr sicher, daß die Implementierungen korrekt sind.

Für kleine Beispiele habe ich auch eine A*-Suche implementiert, die liefert die gleichen Ergebnisse. Allerdings ist sie zu Rechen- und Speicheraufwendig um richtige Beispiele damit durchzurechnen (ist auch etwas ungeschickt implementiert).

Es haben nur 3 Leute mitgemacht?

Jester

Bei der Experten-Aufgabe, ja. Bei der Linienaufgabe genauso.
Ursprünglich hatten sich noch mehr Leute daran versucht, aber nachdem wohl einige Algorithmen fehlerhaft waren haben sich manche entmutigen lassen. Schade eigentlich.

evilissimo

Hast du die Linien Aufgabe denn schon ausgewertet?

BR

Brutus

Nur 3 Leute bei der Linienaufgabe? Hat thomas001 nicht abgegeben? Oder hat ness nicht abgegeben?

Jester

Ups, sind 4 Einsendungen.
Auswertung dazu kommt auch bald.

Jester

Hm, was mach ich nun mit der Streckenaufgabe?

Point origin(0,0);
Point middle(1,1);
Point end(2,2);

Line line1(origin, middle);
Line line2(middle, end);

std::vector<Line> lines;
lines.push_back(line1);
lines.push_back(line2);

cout << wpc_pro(lines) << endl;

Da sind sich die Herren alle einig: 0 soll die Anzahl der Schnittpunkte sein.

Was nun?

Ist 0 das falsche Ergebnis?

Jester schrieb:

Hm, was mach ich nun mit der Streckenaufgabe?
Point origin(0,0);
Point middle(1,1);
Point end(2,2);

Line line1(origin, middle);
Line line2(middle, end);

std::vector<Line> lines;
lines.push_back(line1);
lines.push_back(line2);

cout << wpc_pro(lines) << endl;
Da sind sich die Herren alle einig: 0 soll die Anzahl der Schnittpunkte sein.

Was nun?

Is'n Berührpunkt.

Jester

imho ist das ein Schnittpunkt.
Damit ich aber trotzdem was tun habe werde ich alle Punkte paarweise verschieden wählen. Dadurch kann dieser Fall nicht auftreten.

evilissimo

Lustig :p

Ich bin froh das wir alle das gleiche ergebniss haben *g*

Laut Wikipedia ist es ein Berührpunkt, wenn die erste Ableitung identisch ist (also eine Funktion die andere tangiert). { (1, 0), (1, 1) } { (2, 1), (1, 1) } dürften sich demzufolge beispielsweise schneiden. Wenn die teilnehmenden Programme so etwas sehen, musst du keine paarweise verschiedenen Punkte nehmen.
In jedem Fall würde es mich aber interessieren, ob die Einsendungen so einen Fall erkennen würden.

Jester

Das erkennen sie vermutlich.

Wobei mir nicht klar ist, von welchem Ableitungsbegriff Du sprichst. Wenn ich die Linien senkrecht nach oben mache kannste den normalen Ableitungsbegriff nicht benutzen.

Ist ein Berührpunkt nicht sowieso auch ein Schnittpunkt?

edit: Wikipedia sagt: ja

Wikipedia schrieb:

Ein Schnittpunkt ist in der Mathematik ein gemeinsamer Punkt zweier Kurven. Haben beide Kurven in ihrem gemeinsamen Punkt die gleiche Tangentensteigung, so spricht man von Berührungspunkt.

Wikipedia schrieb:

Ein Schnittpunkt ist in der Mathematik ein gemeinsamer Punkt zweier Kurven. Haben beide Kurven in ihrem gemeinsamen Punkt die gleiche Tangentensteigung, so spricht man von Berührungspunkt.

klingt logisch

evilissimo

http://de.wikipedia.org/wiki/Diskussion:Schnittpunkt

Wikipedia Diskussion schrieb:

Er bezeichnet einen Punkt, in dem sich zwei oder mehrere gerade oder gebogene Linien überkreuzen.

Eine tangentiale Berührung wird im Allgemeinen nicht als Schnittpunkt bezeichnet.

Die scheinen sich da aber auch nicht so sicher zu sein, so wie es aussieht ^^

Jester

Aber
[(0,0), (2,2)]
[(1,1), (2,0)]
schneiden sich nach eurer Rechnung.

evilissimo

Jester schrieb:

Aber
[(0,0), (2,2)]
[(1,1), (2,0)]
schneiden sich nach eurer Rechnung.

Ich sag ja net das mein algo richtig ist. Ich hab nur das erwähnt was auf Wikipedia zu dem Thema noch gesagt wird.

Jester schrieb:

Wobei mir nicht klar ist, von welchem Ableitungsbegriff Du sprichst. Wenn ich die Linien senkrecht nach oben mache kannste den normalen Ableitungsbegriff nicht benutzen.

Die Funktion dieser Linie bildet auf eine 2dimensionale Ebene ab und nimmt Parameter t. Eine allgemeine Kurve halt, in diesem Fall zweidimensional, wovon man ohne Probleme den Vektor der partiellen Ableitungen bilden kann.

Ist ein Berührpunkt nicht sowieso auch ein Schnittpunkt?

edit: Wikipedia sagt: ja

Ich denke nicht, dass du das aus diesem Satz folgern kannst. Genausogut kann der Satz eine Gegenüberstellung von Schnitt- und Berührpunkt sein. Nimm dir mal ne Parabel x² und sieh dir die X-Achse an. Schneidet sie die Parabel? Ich würde sagen nein.

Jester schrieb:

Aber
[(0,0), (2,2)]
[(1,1), (2,0)]
schneiden sich nach eurer Rechnung.

Finde ich korrekt.

Jester

Optimizer schrieb:

Ich denke nicht, dass du das aus diesem Satz folgern kannst.

Da steht doch, was ein Schnittpunkt ist, nämlich ein gemeinsamer Punkt. Und ein Berührpunkt ist ein gemeinsamer Punkt der...

Ergo: Berührpunkt ist Schnittpunkt.

@Ableitung: Und ich kann Dir ohne Probleme zwei Parametrisierungen meiner Strecke mit unterschiedlichen Ableitungen angeben.
Was Du wahrscheinlich haben willst ist lineare Abhängigkeit des Gradienten... und nichtmal das ist hinreichend. Zusätzlich müßten wir noch Parametrisierungen ausschließen, deren Gradient 0 werden können. Aber sag, ist das nicht ein bißchen viel des Guten für so nen einachen Begriff?

Nach der einen Definition ist ein Berührpunkt ein Schnittpunkt, also geht das erste Beispiel schief. Nach der Definition aus der Diskussion ist ein Schnittpunkt ein Punkt in dem sich die Strecken kreuzen. Das tun sie im zweiten Beispiel aber nicht.

Ich kann doch nicht jedesmal Optimizer fragen, ob er das jetzt gerade als Schnittpunkt empfindet oder nicht.

evilissimo

Testest du es trotzdem noch ( aber dann nur mit kreuzenden Linien )?

BR

evilissimo