Linienüberschneidungs Algo gesucht!

Übersicht

BlitzBasic

Allgemein

	Jan_ Ehemaliger Admin Betreff: Linienüberschneidungs Algo gesucht!	Do, Jun 24, 2004 14:32 Antworten mit Zitat
Hiho Ich suche unbedingt, nen Algorhythmus, der Herausfindet, ob sich 2 linien überschneiden. Bitte um Hilfe. Wer den gibt, kommt in das j0k3 hat Folgendes geschrieben: Buch der coolen Leute THX
between angels and insects

Jan_

Ehemaliger Admin

Betreff: Linienüberschneidungs Algo gesucht!

Do, Jun 24, 2004 14:32
Antworten mit Zitat

Hiho

Ich suche unbedingt, nen Algorhythmus, der Herausfindet, ob sich 2 linien überschneiden.
Bitte um Hilfe.

Wer den gibt, kommt in das j0k3 hat Folgendes geschrieben:

Buch der coolen Leute

THX

between angels and insects

	Dreamora	Do, Jun 24, 2004 14:34 Antworten mit Zitat
Überprüfe die linken endpunkte von beiden und merke dir welche Linie den höheren Y wert hat dann überprüfe die rechten endpunkte und guck wieder die Y werte an. Wenn nun die andere Linie den höheren Y wert hat, dann haben sie sich geschnitten, ansonsten nicht.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Do, Jun 24, 2004 14:34
Antworten mit Zitat

Überprüfe die linken endpunkte von beiden und merke dir welche Linie den höheren Y wert hat

dann überprüfe die rechten endpunkte und guck wieder die Y werte an. Wenn nun die andere Linie den höheren Y wert hat, dann haben sie sich geschnitten, ansonsten nicht.

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Jan_ Ehemaliger Admin	Do, Jun 24, 2004 14:47 Antworten mit Zitat
gut, ist klar! Ich hatte die idee, jedes Pixel abzufragen sich selber hau hätte ich weiß Gott auch drauf kommen können. gut, ich muss dich enttäuschen, ich das Buch nicht! schade, trotzdem Danke!
between angels and insects

Jan_

Ehemaliger Admin

Do, Jun 24, 2004 14:47
Antworten mit Zitat

gut, ist klar!

Ich hatte die idee, jedes Pixel abzufragen *sich selber hau*

hätte ich weiß Gott auch drauf kommen können.
gut, ich muss dich enttäuschen, ich das Buch nicht!
schade, trotzdem Danke!

between angels and insects

	MVB	Do, Jun 24, 2004 15:02 Antworten mit Zitat
Nein. Das ist nicht richtig! Beispiel: Linie1: x1=10 y1=20 x2=20 y2=50 Linie2: x1=30 y1=50 x2=40 y2=20 Diese beiden Linien schneiden sich definitiv nicht.
aquamonit.de\|BlitzMax\|MaxGUI

MVB

Do, Jun 24, 2004 15:02
Antworten mit Zitat

Nein. Das ist nicht richtig!
Beispiel:
Linie1:
x1=10
y1=20
x2=20
y2=50
Linie2:
x1=30
y1=50
x2=40
y2=20

Diese beiden Linien schneiden sich definitiv nicht.

aquamonit.de|BlitzMax|MaxGUI

	Jan_ Ehemaliger Admin	Do, Jun 24, 2004 15:06 Antworten mit Zitat
ja, man muss X noch prüfen, soweit ist das klar!
between angels and insects

Jan_

Ehemaliger Admin

Do, Jun 24, 2004 15:06
Antworten mit Zitat

ja, man muss X noch prüfen, soweit ist das klar!

between angels and insects

	MVB	Do, Jun 24, 2004 15:12 Antworten mit Zitat
Hier: www.blitzbase.de/quellcode/linienkreuzung.bb
aquamonit.de\|BlitzMax\|MaxGUI

MVB

Do, Jun 24, 2004 15:12
Antworten mit Zitat

Hier: www.blitzbase.de/quellcode/linienkreuzung.bb

aquamonit.de|BlitzMax|MaxGUI

	BladeRunner Moderator	Do, Jun 24, 2004 15:13 Antworten mit Zitat
Liniengleichung: y=mx+n wobei m= die Steigung und n die abweichung vom Nullpunkt. Ermittle m per: (y1-y2)/(x1-x2) (start und endpunkt der linie). n= y an x=0. mach das für beide linien und setze sie dann gleich: m1x+n1=m2x+n2. Löse nach x auf und überprüfe ob es im Wertebereich der ersten Linie (startx-Endx) zu einem Ergebnis kommt. Wenn ja schneiden sie sich. EDIT: s.o. schon fix und fertig.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Do, Jun 24, 2004 15:13
Antworten mit Zitat

Liniengleichung:
y=mx+n

wobei m= die Steigung
und n die abweichung vom Nullpunkt.

Ermittle m per: (y1-y2)/(x1-x2) (start und endpunkt der linie).
n= y an x=0.
mach das für beide linien und setze sie dann gleich:
m1x+n1=m2x+n2.
Löse nach x auf und überprüfe ob es im Wertebereich der ersten Linie (startx-Endx) zu einem Ergebnis kommt. Wenn ja schneiden sie sich.

EDIT: s.o. schon fix und fertig.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	Dreamora	Do, Jun 24, 2004 16:24 Antworten mit Zitat
das mit der liniengleichung braucht man nur, wenn man den genauen Punkt wissen will, aber wenn man nur rausfinden will, ob sie sich schneiden ist sehr sehr viel verschwendete rechenzeit für nix. Kannst ja mal nach "Scanline Algorithm" suchen im netz Hatte die verschiedenen algo zwar grad vor 1 monat aber da wir aktuell relativ komplexe algos haben, weiss ich ihn nimmer vollständig genug um net noch mehr chaos zu erzeugen.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Do, Jun 24, 2004 16:24
Antworten mit Zitat

das mit der liniengleichung braucht man nur, wenn man den genauen Punkt wissen will, aber wenn man nur rausfinden will, ob sie sich schneiden ist sehr sehr viel verschwendete rechenzeit für nix.

Kannst ja mal nach "Scanline Algorithm" suchen im netz

Hatte die verschiedenen algo zwar grad vor 1 monat aber da wir aktuell relativ komplexe algos haben, weiss ich ihn nimmer vollständig genug um net noch mehr chaos zu erzeugen.

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	joKe	Do, Jun 24, 2004 16:44 Antworten mit Zitat
Oh jetzt muss ich da aber viele Leute eintragen oder war das nur auf die bezogen Jan_ ?
Projekt: Pollux Renegades Coop [Maschine: Intel DualCore2 2x 3Ghz \| 4096 DRR2 \| GeForce GTX 260 Ultra]

joKe

Do, Jun 24, 2004 16:44
Antworten mit Zitat

Oh jetzt muss ich da aber viele Leute eintragen
oder war das nur auf die bezogen Jan_ ?

Projekt: Pollux Renegades Coop
[Maschine: Intel DualCore2 2x 3Ghz | 4096 DRR2 | GeForce GTX 260 Ultra]

	Jan_ Ehemaliger Admin	Do, Jun 24, 2004 20:10 Antworten mit Zitat
Ich wollte, nur das Zitat, zu diesen Begriff klarstellen! und wenn, dann müsste es in mein Buch!
between angels and insects

Jan_

Ehemaliger Admin

Do, Jun 24, 2004 20:10
Antworten mit Zitat

Ich wollte, nur das Zitat, zu diesen Begriff klarstellen!

und wenn, dann müsste es in mein Buch!

between angels and insects

	Markus2	Fr, Jun 25, 2004 12:50 Antworten mit Zitat
@Jan_ Bei BlitzBasic.com findest du auch sowas im Code Archiv.

Markus2

Fr, Jun 25, 2004 12:50
Antworten mit Zitat

@Jan_

Bei BlitzBasic.com findest du auch sowas im Code Archiv.

	Gossi	Fr, Jun 25, 2004 16:58 Antworten mit Zitat
Dreamora hat Folgendes geschrieben: das mit der liniengleichung braucht man nur, wenn man den genauen Punkt wissen will, aber wenn man nur rausfinden will, ob sie sich schneiden ist sehr sehr viel verschwendete rechenzeit für nix. Wo liegt denn da die sehr sehr viel verschwendete rechenzeit in bladerunners methode? er hat doch nur ne handvoll normaler formeln benutzt. Also sooooo unglaublich langsam sollte das nicht sein.
Alle Wasser laufen ins Meer, doch wird das Meer nicht voller; an den Ort, dahin sie fließen, fließen sie immer wieder. (...) Was geschehen ist, eben das wird hernach sein. Was man getan hat, eben das tut man hernach wieder, und es geschieht nichts neues unter der Sonne. Geschieht etwas, von dem man sagen könnte: "Sieh, das ist neu"? Es ist längst vorher auch geschehen in den Zeiten, die vor uns gewesen sind.

Gossi

Fr, Jun 25, 2004 16:58
Antworten mit Zitat

Dreamora hat Folgendes geschrieben:

das mit der liniengleichung braucht man nur, wenn man den genauen Punkt wissen will, aber wenn man nur rausfinden will, ob sie sich schneiden ist sehr sehr viel verschwendete rechenzeit für nix.

Wo liegt denn da die sehr sehr viel verschwendete rechenzeit in bladerunners methode? er hat doch nur ne handvoll normaler formeln benutzt. Also sooooo unglaublich langsam sollte das nicht sein.

Alle Wasser laufen ins Meer, doch wird das Meer nicht voller; an den Ort, dahin sie fließen, fließen sie immer wieder. (...) Was geschehen ist, eben das wird hernach sein. Was man getan hat, eben das tut man hernach wieder, und es geschieht nichts neues unter der Sonne. Geschieht etwas, von dem man sagen könnte: "Sieh, das ist neu"? Es ist längst vorher auch geschehen in den Zeiten, die vor uns gewesen sind.

	Jan_ Ehemaliger Admin	Fr, Jun 25, 2004 17:47 Antworten mit Zitat
ja, ich hatte gestern, selber dich methode von Blade aufgestellt. THX, ist super!
between angels and insects

Jan_

Ehemaliger Admin

Fr, Jun 25, 2004 17:47
Antworten mit Zitat

ja, ich hatte gestern, selber dich methode von Blade aufgestellt.

THX, ist super!

between angels and insects

	Dreamora	Fr, Jun 25, 2004 21:39 Antworten mit Zitat
Gossi: wenn du pro frame unzählige Lines prüfst macht es sehr wohl nen unterschied ob du nur ein paar vergleiche hast oder berechnungen aufstellen musst. Es ist unnutze arbeit den Schnittpunkt zu errechnen, wenn du ihn garnicht benötigst.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Fr, Jun 25, 2004 21:39
Antworten mit Zitat

Gossi: wenn du pro frame unzählige Lines prüfst macht es sehr wohl nen unterschied ob du nur ein paar vergleiche hast oder berechnungen aufstellen musst. Es ist unnutze arbeit den Schnittpunkt zu errechnen, wenn du ihn garnicht benötigst.

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Linienüberschneidungs Algo gesucht!

Betreff: Linienüberschneidungs Algo gesucht!