Schnitt zweier Strecken

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Schnitt zweier Strecken

    Hallo,

    wir haben in der FH ein kleines Programm geschrieben, bei dem es im Grunde um den Schnitt zweier Strecken geht.
    Dabei wird per Mausklick eine Art Autobahn gezeichnet, danach ein (primitiver) LKW (also ein Rechteck) auf die Fläche draufgesetzt. Nun soll entschieden werden, ob der LKW auf der Autbahn ist oder nicht.

    Meine Herangehensweise: Ich nehme jede einzelne Strecke in ein Array auf und prüfe dann später den Schnitt mit dem LKW.

    Mein Problem ist, dass ich den Algorithmus zum Schnitt der beiden Strecken noch nicht ganz kapiere.

    Ich wollte mal fragen, ob jemand einen relativ einfachen Algorithmus kennt, oder mir bei meinem helfen kann ihn zu verstehen.

    Das Programm ist eigentlich fertig, nur funktioniert es manchmal nicht.

    Ich hänge den Quellcode mal an, wenn ihn jemand sehen will. Das Ding wurde mit dem Oracle JDeveloper geschrieben.

    Gruß und Danke,

    mad

    Schnittalgorithmus:

    Quellcode

    1. public int guzs(Punkt p2){
    2. // ergebnis = 0 -> Schnitt
    3. int dx1 = p0.getX()-p1.getX();
    4. int dx2 = p2.getX()-p0.getX();
    5. int dy1 = p1.getY()-p0.getY();
    6. int dy2 = p2.getY()-p0.getY();
    8. System.out.println(dx1+","+dx2+","+dy1+","+dy2);
    10. int ergebnis = 0;
    12. if(dx1*dy2 > dx2*dy1) ergebnis = 1;
    13. if(dx2*dy1 > dx1*dy2) ergebnis = -1;
    15. if(dy2*dx1 == dy1*dx2){
    16. if((dx1*dx2 < 0) || (dy1*dy2 < 0)){
    17. ergebnis = -1;
    18. } else if (dx1*dx1 + dy1*dy1 >= dx2*dx2 +dy2*dy2){
    19. ergebnis = 0;
    20. } else ergebnis = 1;
    21. }
    23. return ergebnis;
    24. }
    Alles anzeigen
    Dateien

    • project1.zip

      (2,94 kB, 428 mal heruntergeladen, zuletzt: )

  • Hi,

    ich erkenne den Algorithmus auch nicht.
    Ist das wieder so eine typische Aufgabe bei der man nur "gelerntes" Wissen anwenden darf? Ansonsten würde ich dir die Area Klasse empfehlen: http://java.sun.com/j2se/1.5.0/docs/api/java/awt/geom/Area.html

    Und dann noch einen alternativen Algorithmus:
    Linien zu Vektoren machen.
    Ebene in die Hessesche Normalform bringen.
    Und dann mit Kenntnissen der linearen Algebra überprüfen ob die Gerade auf der Ebene liegt.

  • Naja, der Prof sieht das schon lieber, wenn man seine Algorithmen anwendet, aber ich glaub letztendlich ist es egal, wie man die Aufgabe löst.

    Das ist im übrigen der einzige Algorithmus den ich zu diesem Thema gefunden habe, wenn man ihn komplett verstanden hat, ist er glaub ich auch einfach, weil er auch mit Vektoren arbeitet, aber so wie er ihn beschrieben hat, isses echt doof.

    Naja ich versuch mal deinen Weg, auch wenn der etwas komplizierter klingt, hätte ja sein können, dass jemand den Algorithmus kennt.

    Hier ist der ürbigens auch beschrieben http://www.informatik.uni-siegen.de/ps/teaching/889/Alg210geo1.pdf
    Seiten 3-9

    naja, vielleicht fällt einem ja noch was dazu ein...

    cya

    p.s. die klasse werd ich mir mal anschauen, obwohl der prof will, dass wir die algorithmen selbst entwickeln..

  • "mad" schrieb:

    p.s. die klasse werd ich mir mal anschauen, obwohl der prof will, dass wir die algorithmen selbst entwickeln..

    Im Fach "Algorithmen" zu verstehen ;)

    Auch wenns nicht zur Erklärung des Algorithmus beiträgt.
    Vergleich nochmal den PseudoCode mit deiner Java Implementierung.
    Ich glaube du bist da mit den p's und q's durcheinandergekommen.
    Es sind ein paar Dreher drinne.

    Quellcode

    1. begin
    2. dx1 := q.x - p.x; dy1 := q.y - p.y;
    3. dx2 := r.x - p.x; dy2 := r.y - p.y;
    4. if dx1*dy2 > dy1*dx2 then ori := 1;
    5. if dx1*dy2 < dy1*dx2 then ori := -1;
    6. if dx1*dy2 = dy1*dx2 then
    7. begin
    8. if (dx1*dx2 < 0) or (dy1*dy2 < 0) then
    9. ori := -1
    10. else if (dx1*dx1+dy1*dy1) >= (dx1*dx2 + dy2*dy2) then
    11. ori := 0
    12. else
    13. ori := 1;
    14. end;
    15. end;
    Alles anzeigen

  • na klar...

    Quellcode

    1. public int guzs(Punkt p2){
    2. // ergebnis = 0 -> Schnitt
    3. int dx1 = p0.getX()-p1.getX();
    4. int dy1 = p0.getY()-p1.getY();
    5. int dx2 = p2.getX()-p1.getX();
    6. int dy2 = p2.getY()-p1.getY();
    8. int ergebnis = 0;
    10. if(dx1*dy2 > dx2*dy1) ergebnis = 1;
    11. if(dx1*dy2 < dx2*dy1) ergebnis = -1;
    13. if(dy1*dx2 == dy2*dx1){
    14. if((dx1*dx2 < 0) || (dy1*dy2 < 0)){
    15. ergebnis = -1;
    16. } else if (dx1*dx1 + dy1*dy1 >= dx1*dx2 +dy2*dy2){
    17. ergebnis = 0;
    18. } else ergebnis = 1;
    19. }
    21. return ergebnis;
    22. }
    Alles anzeigen


    cya