farbige Figur erkennen

[Baron Fel]

Hallo!
Ich bin mir net hundertprozentig sicher ob das hier hingehört, aber ich denke schon.

Ich habe einn Programm(soll mal ein Spiel werden, wenn es groß ist^^), bei dem auf einer Spielfläche erst ein Kreis erzeugt wird und danach Linien dazu kommen, die immer zwei Punkte des Kreisbogens miteinander verbinden...
Es ist für zwei Spieler gedacht und deshalb gibt es zwei Farben...
Die Spieler färben die vorher noch grauen Linien abwechselnd in ihrer Farbe ein.
Wer zuerst durch das Einfärben einer Linie ein Dreieck in seiner Farbe erzeugt, der hat verloren....

Nun habe ich ein Problem...
Die Kreise und Linien, etc habe ich mit Canvas und den ensprechenden Methoden gemacht...
Nun muss ich aber irgendwie prüfen ob eben ein Dreieck in der Spielerfarbe existiert...
Ich weiß net wie ich das anstellen soll und ich wär euch sehr dankbar...
Hab auch ein Bild eingefügt, wo eine Situation zu sehen ist, die theoretisch zu nem Entscheid führen müsste...

http://mitglied.lycos.de/baronfel/su...creen-prob.gif

P.S.: lasst euchnet von den ganzen anderen Sachen stören^^, das sind nur Parameter und Überwachungssachen...
Achso und ich wäre euch sehr dankbar, wenn ihr mir nicht sagen würdet, dass ich das mit OpenGL oder DirectX machen soll^^dazu hab ich keine Zeit^^

trotzdem schonmal danke im vorraus :hi: :hi:

[marabu]

Hallo Baron Fel,

Zitat:

Zitat von Baron Fel

Die Kreise und Linien, etc habe ich mit Canvas und den ensprechenden Methoden gemacht... Nun muss ich aber irgendwie prüfen ob eben ein Dreieck in der Spielerfarbe existiert...
Ich weiß net wie ich das anstellen soll und ich wär euch sehr dankbar...

wenn du die Koeffizienten der Geradengleichungen für deine Sekanten in einer geeigneten Struktur (zB. 2-dimensionales array) speicherst, dann kannst du für je zwei Sekanten leicht den Schnittpunkt ausrechnen. Die Prüfung, ob dieser Schnittpunkt außerhalb deines Kreises liegt, sollte nicht allzu schwierig sein.

Grüße vom marabu

[Baron Fel]

naja, das Prob iss nur, das ich die Linien nicht durch ne gleichung erstelle sondern durch lineto, also das verbinden tweierpunkte...

oder sollte ichaus den Punkten die Gleichung für jede Linie erechnen???
das werden ne menge und ich müsste unglaublich viele Variationen prüfen, die sich ja immer genau drei scheniden müssen...

[mschaefer]

Sonntagsmoin

1. Mach es über ein DynArray oder Listen
2. Denk nicht über Bitmapparsing nach (Linien haben mehr als ein Punkt breite !!!)
3. kümmere Dich um einen flotten Algorithmus der die Listen durchgeht.

Wenn Du keine Zeit hast Dich mit GL zu beschäftigen, dann hast Du auch keine
um Bitmapparsing zu überstehen.

Grüße // Martin

[DGL-luke]

vielleicht solltest du gleich damit anfangen, dreiecke und nciht-dreiecke zu zeichnen. nicht-dreiecke sind einfach linien, und dreiecke bestehen aus drei Linien plus drei Bools. wenn eine linie eines dreiecks dann markiert wird, kanst du das entsprechende bool auf true setzen, wen alle drei true sind -> Ex.

in deinem onmouseup musst du nur noch alle Strecken nach Punkt-In-Strecke prüfen, dafür gibt es bei den Schweizern oder auch hier in der DP genug codebeispiele.

[Baron Fel]

Zitat:

Zitat von mschaefer

1. Mach es über ein DynArray oder Listen
2. Denk nicht über Bitmapparsing nach (Linien haben mehr als ein Punkt breite !!!)
3. kümmere Dich um einen flotten Algorithmus der die Listen durchgeht.

Danke für die schnelle Hilfe, aber was soll in das arry, oder die Liste????

[alzaimar]

Zitat:

Zitat von Baron Fel

Danke für die schnelle Hilfe, aber was soll in das arry, oder die Liste????

Die Linien. Du definierst Dir eine Klasse 'TLinie'. Die besteht aus zwei Punkten (X,Y). Wenn Du der Klasse noch eine Methode spendierst, die
prüft, ob eine andere Linie die Linie innerhalb des Kreises schneidet, dann hast fast gewonnen.
Denn ein Dreieck ist doch so definiert, das Line L1 die Line L2 schneidet. L2 schneidet L3 und L3 wieder L1.

[mschaefer]

Also ich würde ein DynArray anlegen das nur die Endpunkte der roten Linine aufnimmt..
Also wenn du eine Linie zeichnest einen Einträg mit den Punktkoordinaten von(x.y) bis(x.y)
Beim Eintragen könntest Duz diese dann runden (auf den nächsten/vorherigen 5er) um Zeichenungenauigkeiten auszugleichen.

Um dann herauszubekommen ob es eine Verbindung gibt muß ein Algorithmus von einem beliebigen Punkt starten und von dort zum Verbindungspunkt gehen. Dann sucht er ob dieser in einer weiteren Verbindung der Liste vorkommt(2.) Strecke. Und von da an muß es eine Rückverbindung zum 3. geben. Das ganze findet man auch unter dem Begriff Critical-Path-Method / Traveling-Salesman-Problem.

zunächst erstmal soviel..

Grüße // Martin

[alzaimar]

Toll. Und da bist Du ganz alleine drauf gekommen?

[mschaefer]

Täusche Dich nicht!

Mathematisch gibt es da bisher keine optimale Lösung. Das sind meist Erfahrungsansätze die hier programmiert sind. Und da kann man sich noch gut die Zähne dran ausbeissen. Aber wenn Du soviel weiter bist dann man tao!

Um auf das Linienschneiden mal einzugehen. Wenn eine Linie gezeichnet wird. Muß Sie selbst testen ob Sie andere Linien schneidet. Insofern ist die Idee mit der Klasse gut. Die Linie wird dann in Linienabschnitte zerlegt und deren Endpunkte ebenfalls in die Lienineliste mit den Endpunkten eingetragen. Die Orginallinie ist dann selbst schon wieder überflüssig.

Gehe erstmal Kaffeetrinken...(Linien und Krümel...I


Grüße // Martin

[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 :wink: . Schau dir mal TObjectList an.

[OT] Dein Name kam mir gleich so bekannt vor :wink: [/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. :roll:
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>

[Baron Fel]

1 Tag später...
Ich hab jetzt eine Variante, bei der man manuell erkenne muss, ob ein Dreieck vorliegt entwickelt(als Vorlage für die nächste), doch da tritt ein Problem auf, welches ich net so ganz verstehe...

Ich habe ein Image, mit dem Namen spielfeld. Darauf zeichne ich mit canvas.ellipse nen Kreis in clgray.
Anschließend wollte ich die Koordinaten aller Punkte in Stringlisten tragen..eine für x, eine für y...
doch bitte erklärt mir warum dieser Code:

Delphi-Quellcode:

for ix:=0 to spielfeld.width do
  begin
   for iy:=0 to spielfeld.height do
    begin
     if spielfeld.canvas.pixels[ix,iy]=clgrey then
      begin
       xwerte.add(inttostr(ix));
       ywerte.add(inttostr(iy));
      end;
    end;
  end;

auch Koordinaten von Punkten in die Liste einträgt, die nicht grau sind, also clBtnFace....??? :wiejetzt:

[Khabarakh]

Was denn jetzt, clBlack oder clBtnFace (besser clGray) :wink: ?

[OT] Ja, dein Name war mir noch in Erinnerung. Sollte ich mal wieder lesen :wink: [/OT]

[negaH]

Es wurde zwar schonmal vorgeschlagen, aber ich denke die Idee ist nicht klar rübergekommen.

Betrachte dein Program in zwei Teilen:

1.) die Konstruktionsregel des Spielfeldes
2.) Anzeige und Auswertung des Spielfeldes

Die Konstruktionsregel des Spieles wird so programmiert das sie von Hause aus, also auf ganz natürliche Weise, von Anfang an weis ob und welche Linien ein Dreieck ergeben werden. Die Auswerteregel muß nun nur überprüfen ob 3 solcher Linien in einer Farbe eingefärbt wurden. Ergo: Denke über Datenstrukturen nach die Linien und Dreiecke verknüpft konstruieren und speichern können. Vorteil: du kannst die Parameter der nötigen Spielstärke direkt in diese Konstruktionsregeln des Spielfeldes einbauen. Denn je mehr Linien Dreiecke ergeben um so schwerer wird das Spiel.

Die Darstellung dieser Datenstrukturen ist nun relativ unabhängig und hat im Grunde garnichts mit Bitmaps und Pixelauswertungen zu tuen, sondern eher mit Vektorengrafiken. Denn bei jedem Mausklick kannst du exakt mithilfe mathematischer Formeln berechnen in welchem Liniensegement=Vektor sich der Spieler befindet.

Statt also stupid irgendwelche Linien in eine Pixel-Bitmap einzuzeichenen und dann auf komplizierte Art und Weise die Bitmap auszuwerten, konstruiere dein Spiel nach deinen Regeln, und somit stellt die grafische Zeichnung der Bitmap immer nur ein Abbild deiner Vektoren dar.

Gruß Hagen

[Baron Fel]

na gut, das wird wohl das beste sein, aber habt ihr ne Ahnung warum es nicht fuinktioniert??ß

Ähm, beim Thema Vektrorgrafiken, ich hab da bei google, etc noch nichts wie ne Art kurze Einführung, oder so gefunden...
habt ihr sowasoder ist es einfach nur dieses System, was man verstehen muss???

zum Prob: Ich will sozusagen alle Punkte vom Kreis in ner Stringlist, also die coords...
nur er gibt mir alle Pixel im Spielfeld aus. :cry:

[Khabarakh]

Wie schon oben geschrieben, war das nur verschrieben mit clBlack/clGrey/clBtnFace?
Wozu brauchst du überhaupt die Pixel des Kreises? Wie negaH schon geschrieben hat, solltest du alles ausrechnen und nicht auslesen. Dein Bitmap darf nur das Abbild deiner inneren mathematischen Berechnungen sein (zu denen alzaimer ja schon einen guten Ansatz gepostet hat).

[xineohp]

Zitat:

alle Punkte vom Kreis

Das ist scherlich möglich, da der Kreis bzw. die Linie im Allgemeinen unendlich viele Punkte hat, oder hab ich da was falsch verstanden?

[Khabarakh]

Deine Grafikkarte möchte ich sehen :wink: .
Um es deutlich auszudrücken: es geht um die Pixel des Kreises.

[xineohp]

hm, war ja klar, dass ich da irgenwie daneben gelegen habe... :oops:

[Baron Fel]

ähm, ich dachte es würde mir später noch helfen und da hab ich mir eben dies Zeilen ausgedacht(natürlichnet wilkürlich^^)
Doch irgendwie muss da wohl nen Denkfehler drin sein...

ja ich weiß, dass die andere Variante ebsser ist und ich werde es auch so machen, aber es wurmt mich, dass das dort net funzt...

[xDestiny]

Hi @ all!

Ich hab mir ma den Ansatz vom Baron vorgenommen, weil ich das Prinzip nich schlecht finde.

Funktioniert bisher alles. Ich berechne die Funktionsgleichungen aus den gezeichneten Linien und speichere Sie in einem Record ab. Zum anschließenden Zeichnen berechne ich die Schnittpunkte der Linien mit dem Kreis (relativ ungenau). Um herauszufinden, ob drei Linien ein Dreieck bilden, mach ich das so, wies alzaimer gesagt hat.

Jetzt hab ich folgendes Problem:

http://www.xdestiny.de.vu/linien1.jpg

Wie man in dem Screenshot sieht, werden auch Figuren gefüllt, die keine Dreiecke sind, da eine Linie anderer Farbe dadurch geht. Wie kann ich herausfinden, ob eine andersfarbende Linie das Dreieck schneidet.

Delphi-Quellcode:

type
 TPointsArray = array[1..2] of TPoint;
 PPlayer = ^TPlayer;
 TPlayer = record
  Name: String;
  Color: TColor;
  Points: Integer;
 end;
 TLinie = record
  Punkt: TPoint;
  n: Real;
  m: String;
  Player: PPlayer;
 end;

var
  anfP,endP:TPoint;
  Sp1, Sp2: TPlayer;      // Spieler
  ActivePlayer: PPlayer;  // Pointer auf Spieler, der am Zug ist
  Linien: array of TLinie;  // Array mit allen vorhandenen Linieen



function TForm1.SchnPkt(Linie1,Linie2:TLinie):TPoint;
var       m1,m2,x,y:Real;
begin
 if (Linie1.m <> 'n') and (Linie2.m <> 'n') and (Linie1.m <> Linie2.m) then
  begin
   m1 := StrToFloat(Linie1.m);
   m2 := StrToFloat(Linie2.m);

   x := (Linie2.n-Linie1.n)/(m1-m2);

   if (x > 0) and (Ceil((m1*x)+Linie1.n) > 0) and (x < IM_SpielF.Width) and (Ceil((m1*x)+Linie1.n) < IM_SpielF.Height) then
    begin
     Result.X := Ceil(x);
     Result.Y := Ceil((m1*x)+Linie1.n);
    end
   else
    Result := Point(0,0);
  end;
end;


procedure TForm1.Triangles;
var
  i,j,k : Integer;
  AP1,AP2,AP3: TPoint;
begin

if (Length(Linien) >= 3) then
 begin
  for i:=0 to Length(Linien)-1 do
   for j:=i+1 to Length(Linien)-1 do
    for k:=j+1 to Length(Linien)-1 do
     begin
      IM_SpielF.Canvas.Pen.Color := clBlack;
      IM_SpielF.Canvas.Brush.Color := clBtnFace;

      AP1 := SchnPkt(Linien[i],Linien[j]);
      AP1.Y := Convert(AP1.Y);
      AP2 := SchnPkt(Linien[i],Linien[k]);
      AP2.Y := Convert(AP2.Y);
      AP3 := SchnPkt(Linien[k],Linien[j]);
      AP3.Y := Convert(AP3.Y);

      if Inside(AP1) and Inside(AP2) and Inside(AP3) then
       begin
        if (Linien[i].Player^.Name = Linien[j].Player^.Name) and (Linien[i].Player^.Name = Linien[k].Player^.Name) then
         begin
          IM_SpielF.Canvas.Brush.Color := Linien[i].Player^.Color;
          IM_SpielF.Canvas.Polygon([AP1,AP2,AP3]);
         end;
        IM_SpielF.Canvas.Brush.Color := clRed;
        IM_SpielF.Canvas.Ellipse(AP1.X-2,AP1.Y-2,AP1.X+2,AP1.Y+2);
        IM_SpielF.Canvas.Ellipse(AP2.X-2,AP2.Y-2,AP2.X+2,AP2.Y+2);
        IM_SpielF.Canvas.Ellipse(AP3.X-2,AP3.Y-2,AP3.X+2,AP3.Y+2);
       end;
     end;
 end;
end;

Ich hoffe ihr versteht mein Problem und könnt mir helfen...
Thx ... xDestiny