4. 2d-linienkollision?

2d-linienkollision?

  • ?

    hi,

    wie kann ich ausschliesslich mit int-werten am schnellsten herausfinden, ob zwei linien sich im zweidimensionalen raum schneiden?

    thx!
    daoper

    0
  • C

    Meinst du mit "Linien" Geraden oder Strecken? Im ersten Fall schneiden sie sich immer, solange ihre Richtungsvektoren nicht parallel sind. Bei Strecken kannst du erst den Schnittpunkt der drunterliegenden Geraden bestimmen und dann überprüfen, ob er zwischen den Endpunkten liegt.

    0
  • ?

    CStoll schrieb:

    Bei Strecken kannst du erst den Schnittpunkt der drunterliegenden Geraden bestimmen und dann überprüfen, ob er zwischen den Endpunkten liegt.

    aber dafür muss ich doch auch auf floats zugreifen, oder? wie sähe das denn in code aus?

    0
  • ?

    irgendwer 'ne idee, wie ich das ausschliesslich mit ints bewerkstelligen könnte?

    0
  • T

    hm.. also ich würde mal sagen, sie schneiden sich, wenn sie sich kreuzen. und ich glaube, das müßte mit einfachen vergleichen zwischen der x&Y werte der endpunkte rauszufinden sein.. oder nicht??

    0
  • J

    Würde es vielleicht genügen, zu überprüfen, ob die Endpunkte jeweils auf verschiedenen Seiten der durch die Strecken definierten Geraden liegen? Das müßte sich mit ints bewerkstelligen lassen.

    0
  • C

    Sicher könntest du den Schnittpunkt auch mit int's berechnen, wenn du an die Genauigkeit nicht zu große Ansprüche stellst (um festzustellen, ob der Schnittpunkt innerhalb der Strecke liegt, dürfte es in den meisten Feällen reichen).

    Aber Jester's Ansatz ist wohl eleganter:
    Du stellst die beiden Geradengleichungen in der Form aix+bix+ci=0 auf, dann setzt du jeweils die Endpunkte der anderen Strecke dort ein und vergleichst die Vorzeichen der Ergebnisse. (wenn jedes Mal verschiedene Vorzeichen rauskommen, schneiden sich die Strecken)

    0
  • ?

    CStoll schrieb:

    Aber Jester's Ansatz ist wohl eleganter:
    Du stellst die beiden Geradengleichungen in der Form aix+bix+ci=0 auf, dann setzt du jeweils die Endpunkte der anderen Strecke dort ein und vergleichst die Vorzeichen der Ergebnisse. (wenn jedes Mal verschiedene Vorzeichen rauskommen, schneiden sich die Strecken)

    das hört sich gut an. habe ich es richtig verstanden, dass ich die "2-punkte-version" der geradengleichung nutzen muss? wie sähe die denn in code aus?

    0
  • C

    daoper schrieb:

    das hört sich gut an. habe ich es richtig verstanden, dass ich die "2-punkte-version" der geradengleichung nutzen muss?

    Nein, genau genommen brauchst du die Normal(en)form deiner Geraden, die du aber aus der zwei-Punkte-Form recht leicht berechnen kannst (senkrecht zum Richtungsvektor (mx,my)T steht der benötigte Normalenvektor (my,-mx)T - den letzten Parameter c kannst du dann bestimmen, indem du einen der Endpunkte einsetzt).

    wie sähe die denn in code aus?

    Etwa so:

    mx1 = x21-x11;
my1 = y21-y11;
a1=my1;b1=-mx1;c1=-(a1*x11+b1*y11);
//analog berechnest du a2,b2,c2 für die zweite Gerade

d11=a1*x12+b1*y12+c1;
d12=a1*x22+b1*y22+c1;
//analog d21 und d22

return d11*d12<=0 && d21*d22<=0

    (Pij=(xij,yij) ist der i-te Endpunkt der j-ten Geraden)

    0
Anmelden zum Antworten