Linie geht durch ein Rechteck oder nicht

atlastraeger

Hallo Forum!

Ich suche einen Algorithmus, der zurückgibt, ob eine Linie (angegeben durch Startpunkt x1,y1 und Endpunkt x2,y2) innerhalb eines Rechtecks (angegeben durch Startpunkt xb1, yb1 und Endpunkt xb2, yb2) liegt.

Kennt jemand einen effektiven Algorithmus zu dieser Problemstellung?

Vielen Dank im Voraus.

evilissimo

Hier ist erst mal ne einfache Art:

if( ( ( x1 > xb1 && x1 < xb2) && (x2 > xb1 && x2 < xb2) && (y1 > yb1 && y1 < yb2) && (y2 > yb1 && y2 < yb2) ) = true )
     cout << "Die Linie liegt im Bereich des Rechtecks" << endl;

else cout "Linie Ausserhalb des Rechtecks" << endl;

sie berücksichtigt aber nicht ob Punkt(xb1,yb1) < Punkt(xb2,yb2) sondern geht einfach davon aus

atlastraeger

Hi, erst mal vielen Dank für die schnelle Antwort.

Leider habe ich mich etwas unpräzise ausgedrückt. Es geht mir nicht darum, ob die Linie komplett im Rechteck liegt, sondern ob ein (beliebig kleiner) Teil der Linie im Rechteck liegt, d.h. ob die die Linie das Rechteck schneidet oder nicht.
Sorry für mein Schludern

Danke !

pmw

Lass mich raten: Du nimmst am Bundeswettbewerb Informatik teil Pass mit dem Frage in Foren auf. Das kann zur Disqualifikation führen, wenn am zu viel fragt

evilissimo

also ich geb dir nur nen Ansatz.
Damit kannst nur Werte im Positiven bereich überprüfen:

^
     |  hier
     | 
----------->
     |
     |

if( (xb1 > x1 && xb2 < x2) && (yb1 > y1 && yb2 < y2) ) 
    cout << "Linie schneidet Rechteck" << endl;
else
    cout << "Rechteck wird nicht geschnitten" << endl;

Denk dran das gilt nur für den obengenannten Koordinaten bereich also x >= 0 und y >= 0

Sollten andere Werte vorkommen musst du es selbst rausfinden...

//Nachtrag: Ausserdem muss immer gelten das xb1 < xb2 , yb1 < yb2 , x1 < x2 und y1 < y2
Sonst funktioniert das da oben nicht!

atlastraeger

@eViLiSSiMo: Danke!

Sunday

also Schnittpunkte von Linie berechnen, lernt man in der Schule (8. Klasse oder so)!

doppelmuffe

@eViLiSSiMo:
sicher?

evilissimo

Stimmt ich hab nen Fehler gemacht es müsste heißen:

if( (xb1 >= x1 && xb2 =< x2) && (yb1 >= y1 && yb2 =< y2) )
    cout << "Linie schneidet Rechteck" << endl;
else
    cout << "Rechteck wird nicht geschnitten" << endl;

// Edit: Es könnte dann aber sein das das Rechteck nur tangiert wird.

infos findest du sicher auch in diversen clipping algorithmen.(hodgman,..)

doppelmuffe

dann guck mal für:

xb1 = 90
xb2 = 95
yb1 = 10
yb2 = 15
x1 = 1
y1 = 1
x2 = 100
y2 = 100