farbige Figur erkennen

[Baron Fel]

Ok...danke für die Ansätze(und Teillösungen)

Ich werd mal versuchen was ordentliches hinzubekommen...

Ehrlich gesagt hab ich noch net so komplexe Sachen in Delphi gemacht, kenn mich weder mit Dynamischen Arrays aus, noch mit dem Deklarieren von eigenen Klassen, aber das wird schon noch^^

ähm, wenn ich das recht verstehe willst du(ähm...alzaimar) sozusagen TLinie als Menge ihrer Punkte definieren...

[Khabarakh]

Dynamische Arrays und Klassen sind so ziemlich die schlechteste Mischung, die es gibt . Schau dir mal TObjectList an.

[OT] Dein Name kam mir gleich so bekannt vor [/OT]

[mschaefer]

Moin

Mögen die Optimierer gleich zuschlagen. Habe mal eine 'Quick&Dirty'-Liste für 2d zusammengeschraubt
und in den Anhang gelegt. Mit Demo für Lesen und Schreiben, denn mal eben TObjectList ist doch keine
Sonntagskost...

Grüße // Martin

/Edit: Das muß für das Problem natürlich noch etwas umgestellt werden.../Edit

[Baron Fel]

Aha, na gut, das muss ich mir erstma zu Gemüte führen^^
Ich glaube meine favorisierte Variante ist bisher die mit den Geradengleichungen....
Obwohl ichbei dem von dir, mschaefer, noch net so durchblicke...
übrigens das mit dem zeitdruck hat sich jetzt erledigt, aber OpenGL und DirectX dürfen trotzdemin der Trickkiste bleiben^^


P.S.: war ich gemeint, mit dem bekannten Namen???

[alzaimar]

@mschaefer: Ich meinte 'Toll' eigentlich darauf bezogen, das ich 100% das Gleiche, nur 5 min vorher gepostet habe. Im Übrigen Ich kann mir nicht vorstellen, das das Erkennen eines Dreieckes in einer Liste von Linien nicht trivial ist:
Drei Linien Li,Lj und Lk spannen genau dann ein Dreieck auf, wenn Li und Lj, Lj und Lk sowie Lk und Li sich kreuzen. Ist daran etwas falsch?

Delphi-Quellcode:

Procedure HasTriangle (aLines : TLineList);
Var
  i,j,k : Integer;

Begin
  For i := 0 to aLineList.Count - 1 do
    For j:=i+1 to aLineList.Count - 1 do
       If aLines[i].Intersects (aLines[j]) Then // Li schneidet Lj... Jetzt noch ein Lk, das Lj und Li schneidet
         For k:=0 to aLineList.Count - 1 do
           If aLines[j.Intersects (aLines[k]) And aLines[k].Intersects(aLines[i]) Then
              ShowMessage ('Ein Dreieck wird durch die Linien %d, %d und %d erzeugt',[i,j,k]);
End;

Wobei TLine.Intersects (aLine : TLine) True zurückliefert, wenn die Linien sich innerhalb des Kreises kreuzen.

Ich verstehe nicht, was das mit dem Traveling Salesman zu tun hat, der alle Städte in einer Rundreise ... achso, Rundreise -> Dreieck... Hmm... Wer von uns beiden hat da jetzt zu weit gedacht?

[xineohp]

@alzaimar + mschaefer:
Ich glaube, ihr geht von verschiedenen Aufgabenstellungen aus: alzaimar du hast die Frage so verstanden, dass die Dreiecke auch innerhalb des Kreises entstehen dürfen. mschaefer geht aber IMHO davon aus, dass die eckpunkte auf der Kreislinie liegen müssen, womit natürlich eine Schnittpunktberechnung ein ziemlicher Overkill wäre, da es ja reicht die Start und Endpunkte zu vergleichen. Was jetzt genau gewünscht ist hat der Fragesteller zu beantworten

EDIT: Beim dritten Durchlesen bin ich gar nicht mehr so sicher ob ich das Ganze richtig verstanden hatte. Martins Idee geht um einiges tiefer, als ich zu nächst angenommen habe.

[alzaimar]

Ich glaube eher, das Maddin (mschaefer) zu sehr um die Ecke denkt... Oder ich zu wenig... Mir hat er jedenfalls gepostet, das es nicht trivial ist.

[mschaefer]

Moin moin

des Tiefplattdeutschen bin ich nicht mächtig, deshalb beteilige ich mich nicht am Namenverhunzen (altes Indianerprinzip).
Ok habe die Rundreise ziemlich allgemein angesetzt. Aber ich bestehe nun nicht darauf. Laßt uns zunächst mal mit dem einfachen Dreiecksproblem weitermachen.

Die Liste selbst braucht man sich nicht anzuschauen. Wichtig ist nur zu wissen, wie man mit Get Werte herausholt und mit Put reinschiebt. Die Listenunit würde ich selbst voll ausblenden.

Grüße // Martin

[alzaimar]

Namenverhunzungen bleiben aussen vor. Abgemacht.
Mein Ansatz ist doch so gut wie fertig, wieso keine Liste von Linien? Die Daten im Spiel sind doch nichts anderes als eine Liste von Linien, die sich kreuzen. Und wenn sich ein paar Linien so kreuzen, wie ich es definiert habe, ist es doch ein Dreieck, oder nicht? Wieso mit Get/Put Werte reinschieben? Und wo rein?

Alles, was Du bei meinem O(n^3) Algorithmus machen musst, ist, die Intersects-Methode noch definieren. Und die ist ja wohl auch trivial. Was man hier noch einbauen könnte (obwohl es bei den paar Linien keinen Sinn macht), ist, die O(n^3) auf O(n) zu drücken. Die Schnittpunkte der Linien kann man ja als ungerichteten Graphen definieren. Dann brauch ich keine Schnittpunkte mehr suchen, sonden gehe einfach 3 Stufen in die Tiefe und schaue nach, ob ich dann bei mir selbst lande...

[Baron Fel]

also es ist so gemeint, das die Dreiecke ihre Ecken im Kreis aber auch auf der Kreisbahn haben dürfen, also reichen die Anfags-und Endpunkte net aus...

<Edit>
ähm, die TLineList mussich selber erzeugen/deklarieren, oder??
das war die selst erzeugte Klasse???
</Edit>