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

[marabu]

Hallo Baron Fel,

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 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 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