4. Kollision zwischen 2 Strecken berechnen

Kollision zwischen 2 Strecken berechnen

  • I

    Hallo Leute.
    Ich muss herausfinden, ob sich 2 Strecken schneiden oder nicht. Der genaue Schnittpunkt ist allerdings irrelevant.

    Als Ausgangslage habe ich die Eckpunkte der 2 Lininen. Bsw.

    L1 = (x1,y1),(x2,y2)
    L2 = (x3,y3),(x4,y4)

    Ich hoffe, ihr könnt mir helfen. Das währe ech nett von euch!!
    Gruss Ishidur

    0
  • L

    ja zb beide als geradena ansehen also ne geradenglerichung basteln

    also zb

    t∗(x2−x1,y2−y1)+n=g1t*(x2-x1,y2-y1)+n\quad =\quad g1

    auf n kommst du durch nen konkreten wert also x1,x2

    t*\cdots=(x1,x2)$ dann nach n umstellen$ dann den schnittpunkt berechnen und nun schauen ob er auf der strecke liegt dazu reicht es zu zeigen ob der x wert des schnittpunktes zwischen x1 und x2 liegt
    0
  • L

    bessere leosung :

    die jeweiligen x und y werte vergleichen

    und zwar ob x3 oder x4 zwischen x1 und x2 liegen

    dann das selbe fuer die y werte

    ist das der fall scheniden sie sich

    0
  • J

    Falls die Strecken auch mal senkrecht sein dürfen wird das aber nicht so gut funktionieren.

    Dann lieber wie in der LA formulieren.
    Was zu tun bleibt ist ein LGS zu lösen. Ist es eindeutig lösbar, somuß man nur noch schauen, ob beide Lösungen in [0,1] liegen, dann gibt es auch tatsächlich einen Schnitt.

    Ein bißchen aufpassen muß man, wenn man gesagt kriegt unendlich viele Lösungen...
    Dann ist nämlich immer noch alles drin.
    s1 s2
    --- ---

    sowohl mit dem von mir geschilderten Verfahren, also auch mit dem von lokias sagt der Algo zunächst mal unendlich viele Schnittpunkte. Am einfachsten ist es wohl zu testen, ob einer der 4 Endpunkte in der jeweils anderen Geraden enthalten ist.

    MfG Jester

    0
  • L

    ich ueberlege gerade was du mit gls meinst

    es wird mir leider nicht ganz klar

    man hat doch jeweils 2 vektoren

    wenn du jetzt auf linearkombination hinauswillst laeuft das gegen den baum da 2 vektoren meist die ebene aufspannen oder? 😉

    0
  • J

    Ich will folgendes machen:

    geht die Strecke s1 von p1 = (x1,y1) nach p2 = (x2,y2)

    Dann will ich haben:

    g: x = p1 + r*(x2-x1,y2-y1)

    Und für die andere Gerade mache ich das auch. Diese Gerade nenne ich mal h.

    g und h kann man nun schneiden, indem man sie gleichsetzt. Dann erhält man ein LGS in dem die beiden Parameter der Geraden stehen. Erhält man keine Lösung, so schneiden sich die Geraden nicht, also auch nicht die Strecken. Erhält man eine eindeutige Lösung, so sollte man beachten, daß ein Punkt der Geraden auf der Strecke liegt gdw. der Parameter den man in die Gerade einsetzen muß in [0,1] liegt. Das kann man natürlich leicht nachprüfen.

    Nur für den Fall, daß es unendlich viele Lösungen gibt muß man halt noch ein bißchen was tun.

    MfG Jester

    0
  • L

    aso dachte du haettest nen neuen loesungsweg (siehe weiter oben :))

    0
  • J

    Ich hatte schon angefangen zu schreiben bevor Du editiert hast.

    0
  • L

    whatever

    0
  • I

    Hallo Leute, vielen Dank für die vielen Antworten.
    Ich muss an dieser Stelle erwähnen, dass ich eine Lösung suche, welche ich in einem Computerprogramm umsetzten kann. Und soweit ich weiss, kann man in einem Computerprogramm keine Gleichungen gleichsetzten. Ausserdem habe ich mich geirrt bezüglich, dass die Koordinaten des Schnittpunkts irrelevant wären. Ich muss diese nun doch wissen.

    Ich bin durchaus vertraut mit dem Themengebiet der Geometrie, doch in diesem Fall ist eine Lösung im Themengebiet der Algorithmischen Geometrie gefragt.

    Was ich also brauche, ist eine oder meherer Formeln, mit welcher ich die x, sowie y - Koordinaten des Schnittpunkts dieser zwei Strecken berechnen kann.

    Lieber Gruss Ishildur

    0
  • L

    das ganze laesst sich auch tabellarisch loesen

    rechne einmal jesters methode auf dem papier

    der leosungsweg ist immer derselbe also

    kannst du den auch hardcoden

    0
  • I

    Also das mit dem Hardcoden lassen wir doch besser!!
    Es gibt mehrere Tausend Hindernisse...

    Gruss Ishildur

    0
  • J

    Ishildur schrieb:

    Also das mit dem Hardcoden lassen wir doch besser!!
    Es gibt mehrere Tausend Hindernisse...

    Hallo?

    Er hat vorgeschlagen, Du sollst das Auflösen des LGS nach den Variablen einmal durchrechnen und die entstehenden Ausdrück hart kodieren. So nach dem Motto:
    r = a1*a2+b2-b1 oder so, damit Du nicht jedesmal im Code ein LGS lösen mußt.

    Die Parameter sollst Du natürlich nicht fest reinschreiben. 🙄

    MfG Jester

    0
  • L

    hehe ich frag mich gerade was man da noch drunter verstehen kann

    sone volladder bauen oder so 😃

    0
  • I

    @Jester
    Auch Hallo?
    Hast du einmal daran gedacht, dass diese Hindernisse möglicherweise nicht statisch sind? Ach ja, ebenfalls 🙄

    0
  • L

    also.. mit statisch ist nicht gemeint ein seperates ergebnis zu programmieren

    sondern einfach mal die variablen in ihrer rohform zur loesung zu bringen

    jedenfalls das alles so umstellen bis sich ein ergebnis ergibt was man irgendwo fuer den allegemeinen fall uebernehmen kann und nur so einsetzt

    was dann auch mit tabellarischer loesung bezeichnet wird

    man setze also p1+blah=p3+blah
    dann meinetwegen zu einem homogenen linearen gleichungssystem verwandeln

    indem man r1 als formel rausfidet

    dann in die zweite gleichung *yawn*

    naja du wirst das schon schaffen

    *thumbs up*

    0
  • I

    @lookias
    Hallo lookia ich danke dir vielmals für deine Postings!!
    Du aber ich habe da noch eine Frage, folgendes hat mich etwas verwirrt...

    bessere leosung :
    die jeweiligen x und y werte vergleichen
    und zwar ob x3 oder x4 zwischen x1 und x2 liegen
    dann das selbe fuer die y werte
    ist das der fall scheniden sie sich

    Bist du sicher, dass das funktioniert? Also ich habe da so meine Zweifel!
    Stell dir mal folgende Situation vor:
    L1 = {0,0},{100,100};
    L2 = {10,5},{20,5};

    Diese zwei Linien haben nach deinem Gleichungssystem einen Schnittpunkt... 🙄

    0
  • L

    ja timmt war ne fixe idee und auch garnicht richtig

    was ich aber dachte bis vor einer minute 🙂

    0
  • I

    Gibt es denn eine Möglichkeit, herauszufinden, ob zwei strecken sich kreuzen, wenn bekannt ist, dass eine der Beiden entweder waagrecht oder senkrecht ist?

    0
  • J

    Ishildur schrieb:

    @Jester
    Auch Hallo?
    Hast du einmal daran gedacht, dass diese Hindernisse möglicherweise nicht statisch sind? Ach ja, ebenfalls 🙄

    👎
    Sorry Kindchen, aber das muß ich mir von Dir nicht bieten lassen.

    Denk einfach mal ein bißchen drüber nach... und wenn wenn es nicht zur Lösung Deines Problems zu passen scheint, dann kannst Du getrost davon ausgehen, daß Du noch nicht genug gedacht hast.

    0
  • J

    Um's vielleicht nochmal zu verdeutlichen:

    Jemand braucht ne Lösung, für folgendes Problem y=m*x+c dabei sind y,m,c gegeben. Wie kriegt man jetzt das x?

    Naja, man rechnet mal (angen. m!=0)
    x = (y-c)/m.

    Und das kann Du hardcoden als Lösung Deines Problems.
    Dann mußt Du das Umstellen der Gleichung nicht im Programm bewerkstelligen. Genau das kannst Du auch auf Deine Situation übertragen und so war's gemeint.

    Ich frag mich ehrlich gesagt für wie dumm Du uns hältst daß wir Dir vorschlagen die Lösungen hart zu kodieren oder Dich auf statische Hindernisse einzuschränken. Vielleicht solltest Du uns einfach ein bißchen mehr zutrauen.

    MfG Jester

    0
Anmelden zum Antworten