✔ Denkaufgabe: Kollisionsabfrage

[thomy800]

Hi.

Ich habe ein kleines logisches Problem. Man stelle sich einen Intervall a=0 und b vor. Dieser Intervall wiederholt sich unendlich, heißt, wenn b überschritten wurde, gehts wieder bei a los.
Nun werden 2 Linien in diesen Intervall eingetragen. Position (immer zwischen a und b) und Länge zufällig.
Die Frage ist: berühren/überschneiden sich die Linien?

Einige können sich vielleicht denken, was die Aufgabe für einen Sinn hat: Kollisionsabfrage. Eigentlich kein Problem, aber, dadurch dass sich der Intervall unendlich wiederholt, ist das etwas komplizierter.

Ich habe schon eine Formel entwickelt, aber leider funktioniert die nicht ganz...

p1,p2 => Startpunkte der beiden Linien
l1,l2=>Länge der Linien
a ist egal, da 0
b ist der Intervall
Kollision wenn: (p1<=p2 and p2<=(p1+l1) )or (((p2+l2)<=(p1+l1) or p2<=p1) and (p2+l2) mod b>=p1)

Hat jemand ne schicke Idee?

MfG thomy

 

[Gumbo]

Verstehe ich dich richtig, dass die Linie A ab der Position 5 mit einer Länge von 10 die zweite Linie B ab der Position 1 mit der Länge 2 in einem Interval [0,9] überschneiden würde? Also

A |???? ????|
A | ??      |
  0        9

 

[thomy800]

Ja. Genau so mein ich das

 

[arkanoid]

Im Grunde würde ich da folgendermaßen drangehen:

Wenn wir davon ausgehen, dass der Startpunkt der beiden Linien von 0 bis unendlich liegt, dann müssen wir die Startpunkte jeweils ins Intervall runterrechnen...
Dann haben wir beispielsweise die Darstellung wie Gumbo sie gemacht hat (ich übernehm diese einfach mal)... nur dass wir noch die Darstellung über den Intervall hinauslaufen lassen...

A |     ????|????
B | ??      |
  0        9

Dann gleichen wir eine der Linien (ich denke mal die längste wäre am praktischsten) an den 0-Punkt an (dh. Startpunkt und Endpunkt werden um den Wert des Startpunkts in Richtung 0 verschoben...)

A |???????? |
B | ??      |
  0        9

Das Selbe machen wir dann auch mit der anderen Linie... sollte dabei der Startpunkt unter 0 kommen, so wird einfach die Größe des Intervalls hinzuaddiert (zu Start- und Endpunkt)

A |???????? |
B |      ?? |
  0        9

und dann brauchen wir nur schauen, ob der Startpunkt der Linie kleiner als der Endpunkt der anderen Linie ist...

(Alles was hier durchgeführt wurde, soll natürlich nur rechnerisch gemacht werden... die Linien sollen wahrscheinlich ja nicht verschoben werden)

Ich hoffe, das war die Richtung in die es gehen sollte...

 

[thomy800]

Ganz so einfach ist das nicht. Bei deinem Bsp. kam zufällig bei Linie A nur noch eine Linie heraus. Im Normalfall kommen allerdings 2 Teillinien Heraus: 0=>ende mod b und anfang => b.
Aber mit den beiden Startpunkten hast du mich auf eine Idee gebracht, die mir vorher noch nicht ganz klar war: und zwar, dass ich beide Startpunkte prüfen kann, ob sie innerhalb der anderen Linie liegen. Bisher hatte ich immer nur Linie A in bezug auf B betrachtet, nicht aber andersrum

(wichtig für solch einen Fall:

A |    ??         |
B |   ????        |

*edit*
Was haltet ihr von folgener Formel:

 (p2>=p1 and p2<=p1+l1) or (p1+l1>=b and p2<=(p1+l1)%b) or
(p1>=p2 and p1<=p2+l2) or (p2+l2>=b and p1<=(p2+l2)%b)              //selbe nur nochmal vertauscht

(bei einem Intervall von (0,9) wäre b= 10)

 

[arkanoid]

Dass es sich dabei um 2 Teillinien handeln kann, ist mir klar...
Ich versuche ja deswegen das Problem zu umgehen, indem ich einfach über den Intervall hinausrechne...

Nehmen wir an, wir haben
Intervall [0, 9]

L1s (für Linie1 Start): 2
L1 l (für Linie1 Länge): 10

L2s: 22
L2l: 2

Dann berechne ich doch erstmal die Längere Linie runter auf
L1s = 0
L1e = 10

Die 2. Linie muss noch in den Intervall gebracht werden...
Also L2s = 20mod9 = 4

Ich bringe diese Linie um die Selbe Verschiebung nach hinten:
L2s = L2s - Verschiebung = 2

Ich prüfe:
L2s < L1s + Verschiebung?
und habe dann doch schon mein Ergebnis...

Solange du rechnerisch an dieses Intervall gebunden bist, dann kannst du doch auch theoretisch einfach weiter schauen als bis zum Intervall...

Rechne das einfach mal mit ein paar Beispiel Szenarien durch, dann sollte das eigentlich klappen, wenn ich mich nicht irgendwo vertue...

 

[thomy800]

Dann berechne ich doch erstmal die Längere Linie runter auf
L1s = 0
L1e = 10

Heißt, du rechnest -L1s?

Die 2. Linie muss noch in den Intervall gebracht werden...
Also L2s = 20mod9 = 4

Wenn ich mich nicht irre, dann meinst du sicher mod 10, da 9 mod 9 = 0 und 9 liegt eigentlich noch im Intervall.
Und 20 mod 9 ist bei mir 2... meinst du 22?
Und die Längen der Linien, die werden doch gar nicht in deinen Formeln verwendet?

 

[arkanoid]

Heißt, du rechnest -L1s?

ha genau

Wenn ich mich nicht irre, dann meinst du sicher mod 10, da 9 mod 9 = 0 und 9 liegt eigentlich noch im Intervall.
Und 20 mod 9 ist bei mir 2... meinst du 22?

ja meinte ich ;-)
und stimmt, es müsste mod 10 heißen...

Und die Längen der Linien, die werden doch gar nicht in deinen Formeln verwendet?

Nein, nicht wirklich. Im Grunde kannst du alles entweder über L1s und L1e oder über L1s und L1l berechnen, da L1e und L1l ja irgendwie voneinander abhängig sind in Bezug auf L1s

 

[thomy800]

Ich kann mir aber nicht so ganz vorstellen, dass die Längen völlig irrelevant sind :suspekt:

ich habe das mal mit einem Bsp durchgerechnet, welches nicht kollidiert:

b=10

L1s=9
L1l=4

L2s=4
L2l=2

L1s=0 v=9
(mod 10 nicht notwendig, da schon im intervall)
L2s=-7
-7<0+9 => ja

Also kann da etwas nciht stimmen...

 

[thomy800]

Hab nochmal neu überlegt. Bin da auf 2 Möglichkeiten gekommen:

1)
s1, e1=s1+l1
s2, e2=s2+l2

(s2>=s1 and s2<=e1) or (e1>=b and s2<=e1%b) or
(s1>=s2 and s1<=e2) or (e2>=b and s1<=e2%b)

2)
folgene Gleichung gilt nur, wenn: L!=0

s1, e1=(s1+l1)%b
s2, e2=(s2+l2)%b

(s2>=min(s1,e1) and s2<=max(s1,e1))==(s1<e1) or
(s1>=min(s2,e2) and s1<=max(s2,e2))==(s2<e2) or abs(l1)>=b or abs(l2)>=b

Könnten die stimmen?