Linien kreuzen

Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Neue Antwort erstellen

Firstdeathmaker

Betreff: Linien kreuzen

 BeitragDi, Jan 06, 2009 21:52
Antworten mit Zitat
Benutzer-Profile anzeigen
Hier zwei kleine aber feine Funktionen um zu überprüfen, ob und wo sich zwei zweidimensionale Linien treffen + Beispiel.

Die Funktion "overlap" prüft nur, ob sich zwei Linien überschneiden.
Die Funktion "getIntersection" liefert dann den Schnittpunkt wo sich die beiden Geraden überschneiden.


Code: [AUSKLAPPEN]



Rem
   Beispiel
End Rem
Benchmark()

Graphics 800,600
Local line0:Float[4];line0[0]=100;line0[1]=100;line0[2]=400;line0[3]=300
Local line1:Float[4];line1[0]=500;line1[1]=50
Repeat
   line1[2] = MouseX()
   line1[3] = MouseY()

   Cls
      DrawLine line0[0],line0[1],line0[2],line0[3]
      DrawLine line1[0],line1[1],line1[2],line1[3]
      
      If overlap(line0[0],line0[1],line0[2],line0[3],line1[0],line1[1],line1[2],line1[3])
         DrawText "overlapping",10,10
         Local p:Float[] = getIntersection(line0[0],line0[1],line0[2],line0[3],line1[0],line1[1],line1[2],line1[3])
         DrawOval p[0]-4,p[1]-4,8,8
         DrawText "x: "+p[0]+" y: "+p[1],10,30
      EndIf
   Flip
Until KeyHit(KEY_ESCAPE)
End

Function Benchmark()
   Print ""
   Print "Starting Benchmark"
   Local line0:Float[4];line0[0]=100;line0[1]=100;line0[2]=400;line0[3]=300
   Local line1:Float[4];line1[0]=500;line1[1]=50;line1[2]=220;line1[3]=220
   Local loops:Float = 1000000
   Local passes:Int = 3
   
   Print "loops = "+Int(loops)+"  passes = "+passes
   Print ""
   For Local i2:Int = 0 Until passes
      Print "pass "+(i2+1)
   Local time:Int = MilliSecs()
   For Local i:Int = 0 Until loops
      overlap(line0[0],line0[1],line0[2],line0[3],line1[0],line1[1],line1[2],line1[3])
   Next
   Print "overlap: "+(MilliSecs()-time)/loops+" ms per call"
   time = MilliSecs()
   For i:Int = 0 Until loops
      getIntersection(line0[0],line0[1],line0[2],line0[3],line1[0],line1[1],line1[2],line1[3])
   Next
   Print "intersec:"+(MilliSecs()-time)/loops+" ms per call"
   Next
End Function

Rem
   bbdoc: This function checks, if two given lines overlap
   x0,y0 = start coordinates of line 1
   x1,y1 = end coordinates of line 1
   x2,y2 = start coordinates of line 2
   x3,y3 = end coordinates of line 2
   returns: true if lines overlap, false if not
   author: algorithm found on www.topcoder.com by lbackstrom
End Rem   
Function overlap:Int(x0:Float, y0:Float, x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float)
   Return (((y3 - y0) * (x2 - x0) > (y2 - y0) * (x3 - x0)) <> ((y3 - y1) * (x2 - x1) > (y2 - y1) * (x3 - x1))) And (((y2 - y0) * (x1 - x0) > (y1 - y0) * (x2 - x0)) <> ((y3 - y0) * (x1 - x0) > (y1 - y0) * (x3 - x0)))
End Function

   
Rem
   bbdoc: This function checks, if two given lines overlap
   x0,y0 = start coordinates of line 1
   x1,y1 = end coordinates of line 1
   x2,y2 = start coordinates of line 2
   x3,y3 = end coordinates of line 2
   returns: float[2], coordinates where lines intersect
   author: firstdeathmaker
End Rem   
Function getIntersection:Float[](x0#,y0#,x1#,y1#,x2#,y2#,x3#,y3#)
   x1:-x0
   y1:-y0
   x3:-x2
   y3:-y2
   b:Float = ((y2-y0)*x1+(x0-x2)*y1) / (x3*y1-y3*x1)
   Local l:Float[2]
   l[0] = x2 + b*x3
   l[1] = y2 + b*y3
   Return l
End Function


www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image
  • Zuletzt bearbeitet von Firstdeathmaker am Mi, Jan 21, 2009 20:12, insgesamt einmal bearbeitet
 

c64

 BeitragMi, Jan 07, 2009 20:38
Antworten mit Zitat
Benutzer-Profile anzeigen
THX!!
Betreten verboten! Kinder haften für ihre Eltern!

Geeecko

 BeitragSo, Jan 18, 2009 23:46
Antworten mit Zitat
Benutzer-Profile anzeigen
Code: [AUSKLAPPEN]

Function overlap(x0:Float, y0:Float, x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float)
   'Return (CCW(x0, y0, x2, y2, x3, y3) <> CCW(x1, y1, x2, y2, x3, y3)) And (CCW(x0, y0, x1, y1, x2, y2) <> CCW(x0, y0, x1, y1, x3, y3))
   Return (((y3 - y0) * (x2 - x0) > (y2 - y0) * (x3 - x0)) <> ((y3 - y1) * (x2 - x1) > (y2 - y1) * (x3 - x1))) And (((y2 - y0) * (x1 - x0) > (y1 - y0) * (x2 - x0)) <> ((y3 - y0) * (x1 - x0) > (y1 - y0) * (x3 - x0)))
End Function

Ist schneller als dein Code Wink Die helperfunction kann gelöscht werden.
Bei 10000 Aufrufen braucht es mit helper ca. 8ms, ohne 4.
So viel können kleine funktionen ausmachen xD

lg MD

EDIT:
Bei Vielen vielen sehr vielen ^ vielen 5748 Kollisions-prüfungen könnte das nützlich sein, weil man dann fast mehr als den doppelten speed bekommt. bei 3 kollisionen natühjrlich nicht

Firstdeathmaker

 BeitragMi, Jan 21, 2009 20:10
Antworten mit Zitat
Benutzer-Profile anzeigen
Hast recht, deine ist wirklich doppelt so schnell. Hab deine mal, wenn das ok ist, in den Code oben übernommen, damit Leute die nur nach den beiden Funktionen suchen den oberen code nehmen können.

Hab gerade einen kleinen Benchmark gemacht:

overlap: 6885 (meine alte Funktion)
overlap2: 3746 (deine verbesserte)
overlapC: 3690 (deine verbesserte nach C portiert und in BMax eingebunden)

Alle Zeiten in ms, für 100.000.000 Aufrufe. Man sieht: Durch das benutzen einer einzigen Funktion wird das ganze extrem stark beschleunigt. Portieren nach C bringt fast garnix.
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

Geeecko

 BeitragMi, Jan 21, 2009 21:13
Antworten mit Zitat
Benutzer-Profile anzeigen
Jojo, sicher, kein ding xD
Was mich wundert, das die eine Funktion so viel ausmacht.
Da vermisst man inline in BMax dann doch schon Wink

kog

 BeitragMi, Jan 21, 2009 21:21
Antworten mit Zitat
Benutzer-Profile anzeigen
Hmm sind die Werte eigentlich gut?
Code: [AUSKLAPPEN]
Starting Benchmark
loops = 1000000  passes = 3

pass 1
overlap: 1.60000000e-005 ms per call
intersec:0.000111000001 ms per call
pass 2
overlap: 1.70000003e-005 ms per call
intersec:0.000111000001 ms per call
pass 3
overlap: 1.60000000e-005 ms per call
intersec:0.000112000002 ms per call


da es komische zahlen hat

Firstdeathmaker

 BeitragDo, Jan 22, 2009 16:36
Antworten mit Zitat
Benutzer-Profile anzeigen
Hmm, das kommt sehr auf deinen Rechner an, was hast du für Daten und was für einen Benchmarkcode hast du verwendet?

Also wenn ich den unten geposteten Code nehme und durchlaufen lasse, komme ich auf folgende Zahlen:

overlap: 6.8780000000000002e-005
overlap2: 3.7169999999999998e-005
overlapC: 3.7030000000000003e-005
intersection: 9.5999999999999991e-007
intersectionC: 8.6000000000000002e-007

(mittlere Zeit pro Durchlauf einer Funktion in ms)

Für alle welche die Schreibweise nicht wissen: 1.2e-002 bedeutet: 1.2 * 10 ^ -2
D.h. man muss das Komma oder den Punkt um 2 Stellen nach links verschieben wenn man es in normaler Schreibweise haben möchte. Beispiel:

6.8780000000000002e-005 entspricht: 0.00006878

Was mich verwirrt kog ist, dass du so unterschiedliche Werte bekommst:

Zitat:
overlap: 1.60000000e-005 ms per call

ist besser als das was ich hier bei meinen Rechnern gemessen habe. Ich habe einen Intel Dual Core T2400 mit 1,83 GHZ und einen AMD 3500+ mit 2,21 GHZ. Den obigen Test habe ich auf dem Dual Core laufen lassen. Mich würde mal interessieren was du für nen Prozessor hast, bzw wie du den getaktet hast.

Zitat:
intersec:0.000111000001 ms per call

Ist dagegen wesentlich schlechter als alles was ich bisher hier bei mir gemessen habe. Vergleich:

0.000111000001
0.00000095999999999999991 ->mein Ergebnis ist um den Faktor 100 besser.

Irgendwie ein komischer Unterschied...


Test.bmx
Code: [AUSKLAPPEN]
SuperStrict

Import "functions.c"


Extern
   Function overlapC(x0:Float , y0:Float , x1:Float , y1:Float , x2:Float , y2:Float , x3:Float , y3:Float)
   Function getIntersectionC(x0:Float, y0:Float, x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float, result:Float Ptr)
End Extern



For Local i:Int = 0 Until 1000
   overlap(0 , 0 , 400 , 400 , 200 , 0 , 0 , 200)
Next


Local steps:Double = 100000000.0
Local laps:Int = 3
Local time:Int
Local r:Float[2]
Local rp:Float Ptr = Varptr(r[0])
Global logfile:TStream = WriteFile("log.txt")

Function logLine(s:String)
   Print s
   WriteLine(Logfile , s)
End Function


For Local j:Int = 0 Until laps
   logLine "### Lap " + (j + 1)+" ###"
   
   time = MilliSecs()
   For Local i:Int = 0 Until steps
      overlap(0 , 0 , 400 , 400 , 200 , 0 , 0 , 200)
   Next
   time = MilliSecs() - time
   logLine "overlap: " + time/steps
   
   
   
   time = MilliSecs()
   For Local i:Int = 0 Until steps
      overlap2(0 , 0 , 400 , 400 , 200 , 0 , 0 , 200)
   Next
   time = MilliSecs() - time
   logLine "overlap2: " + time/steps
   
   time = MilliSecs()
   For Local i:Int = 0 Until steps
      overlapC(0 , 0 , 400 , 400 , 200 , 0 , 0 , 200)
   Next
   time = MilliSecs() - time
   logLine "overlapC: " + time/steps
   
   Print ""
   time = MilliSecs()
   For Local i:Int = 0 Until steps
   'getIntersectionC(0 , 0 , 400 , 400 , 200 , 0 , 0 , 200,rp)
   Next
   time = MilliSecs() - time
   logLine "intersection: " + time/steps
   
   
   time = MilliSecs()
   For Local i:Int = 0 Until steps
   'getIntersectionC(0 , 0 , 400 , 400 , 200 , 0 , 0 , 200,rp)
   Next
   time = MilliSecs() - time
   logLine "intersectionC: " + time / steps
   logLine ""
   logLine ""

next


logLine "finished"
CloseFile logfile
End


Function overlap2:Int(x0:Float, y0:Float, x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float)
    Return (((y3 - y0) * (x2 - x0) > (y2 - y0) * (x3 - x0)) <> ((y3 - y1) * (x2 - x1) > (y2 - y1) * (x3 - x1))) And (((y2 - y0) * (x1 - x0) > (y1 - y0) * (x2 - x0)) <> ((y3 - y0) * (x1 - x0) > (y1 - y0) * (x3 - x0)))
End Function


Function overlap:Int(x0#,y0#,x1#,y1#,x2#,y2#,x3#,y3#)
   Return (ccw(x0,y0,x2,y2,x3,y3) <> ccw(x1,y1,x2,y2,x3,y3)) And (ccw(x0,y0,x1,y1,x2,y2) <> ccw(x0,y0,x1,y1,x3,y3))
End Function



Function CCW:Int(ax#,ay#,bx#,by#,cx#,cy#)
   Return (cy-ay) * (bx-ax) > (by-ay)*(cx-ax)
End Function

Function getIntersection(x0#,y0#,x1#,y1#,x2#,y2#,x3#,y3#, b_ptr:Float Ptr)
   x1:-x0
   y1:-y0
   x3:-x2
   y3:- y2
   Local b:Float = ((y2-y0)*x1+(x0-x2)*y1) / (x3*y1-y3*x1)
   b_ptr[0] = x2 + b*x3
   b_ptr[1] = y2 + b*y3
End Function


functions.c
Code: [AUSKLAPPEN]

int overlapC(float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3){
    return (((y3 - y0) * (x2 - x0) > (y2 - y0) * (x3 - x0)) != ((y3 - y1) * (x2 - x1) > (y2 - y1) * (x3 - x1))) && (((y2 - y0) * (x1 - x0) > (y1 - y0) * (x2 - x0)) != ((y3 - y0) * (x1 - x0) > (y1 - y0) * (x3 - x0)));
}

float* getIntersectionC(float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3, float* rp){
    x1-=x0;
    y1-=y0;
    x3-=x2;
    y3-=y2;
    x1 = ((y2-y0)*x1+(x0-x2)*y1) / (x3*y1-y3*x1);

    rp[0] = x2 + x1*x3;
    rp[1] = y2 + x1*y3;
    return rp;
}
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

kog

 BeitragDo, Jan 22, 2009 17:09
Antworten mit Zitat
Benutzer-Profile anzeigen
Da siehst du das aktuelle System: http://www.sysprofile.de/id88104


Der Benchmark ist mit dem Teil gemacht das dabei war beim Code.

Firstdeathmaker

 BeitragDo, Jan 22, 2009 19:21
Antworten mit Zitat
Benutzer-Profile anzeigen
Okay, dann kommts hin. Der neue Benchmark ist allerdings sehr viel aussagekräftiger.
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group