Jak sprawdzić czy 2 odcinki się przecinają?

[Cekol]

Hejo.

Wiecie może jak sprawdzić czy 2 odcinki się przecinają?

 

Mam 8 zmiennych: XSTART1 YSTART1 XEND1 YEND1 XSTART2 YSTART2 XEND2 YEND2

W tym XSTART1 YSTART1 XEND1 YEND1 to zmienne początku i końca pozycji pierwszego odcinka

a XSTART2 YSTART2 XEND2 YEND2 to zmienne początku i końca pozycji 2 odcinka.

I muszę teraz wymyśle algorytm sprawdzający, czy te dwa odcinki się przecinają, lecz nie mam pomysłu jak to zrobić xD

Proszę pomóżcie, a w zamian temu kto dobrze poda rozwiązanie najszybciej, będzie on w autorach mojej gry :D

[gnysek]

http://www.algorytm.org/index.php?option=c...3&Itemid=28

 

na dole są źródła ale skomplikowane :P

[Tymon]

Ja bym na Twoim miejscu po prostu przekształcił równanie dwóch prostych.

[Cekol]

@gnysek:

Też znalazłem tą stronę, nawet patrzałem na te przykłady (c++) co są na dole strony, ale nic z tego nie czaje xD

 

@Tymon:

Hmm? przekształcił równanie dwóch prostych? ale że co? xD

[Tymon]

Coś takiego: Ax + B

 

EDIT

Proste rozwiązanie.

 

Kiedy 2 proste się przecinają? Wtedy kiedy nie są równoległe. Czyli A1 != A2.

Kiedy 2 odcinki mogą się w ogóle przecinać? Kiedy istnieje część wspólna między przedziałami <xStart1,xEnd1> i <xStar2,xEnd2> oraz <yStart1,yEnd1> i <yStar2,yEnd2>.

Teraz połącz oba warunki i masz rozwiązanie.

 

Zakodzić, czy sobie poradzisz?

 

Nikas, za trolowanie 7 dni kontroli przez moderatorów.

[Cekol]

@Tymon

Może zakodź ;)

to pierwsze "Kiedy 2 proste się przecinają? Wtedy kiedy nie są równoległe. Czyli a1 != a2." jeszcze rozumiem, ale tego następnego, nie za bardzo.

[Tymon]

https://gmclan.org/up152_11_odcinki.html

Tylko to akurat jest trochę złe, nie uwzględniłem jednego czynnika i metoda trochę leży.

Z resztą sam zobacz. Później postaram się coś wymyślić coby rozwiązało problem.

 

Łe, było by prościej z odcinkami.

[Nicolas]

Napisalem takie dwa skrypty (pierwszy uzywa drugiego, wiec oba sa wymagane):

GML

/***********************************************

Wyznacza punkt przeciecia dwoch odcinkow

P1P2 i P3P4

 

argument0: P1

argument1: P2

argument2: P3

argument3: P4

 

Zwracane wartosc:

0: nie ma

1: punkt znaleziony i zapisany

***********************************************/

 

var p1, p2, p3, p4, x1, x2, y1, y2, r;

p1 = argument0;

p2 = argument1;

p3 = argument2;

p4 = argument3;

 

r = instance_create(-10, -10, result);

 

 

if (!crossing(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y, r))

return 0;

 

//na jednej prostej

if (r.same)

{

var sx, sy, sx2, sy2, len, dis;

sx = (p1.x + p2.x)/2;

sy = (p1.y + p2.y)/2;

sx2 = (p3.x + p4.x)/2;

sy2 = (p3.y + p4.y)/2;

dis = sqrt((sx - sx2) * (sx - sx2) + (sy - sy2) * (sy - sy2));

len = sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y))/2;

len =+ sqrt((p3.x - p4.x) * (p3.x - p4.x) + (p3.y - p4.y) * (p3.y - p4.y))/2;

 

//w wypadku nakladajacych sie nie zapisujemy punkty przeciecia

//jest ich nieograniczenie wiele (w realu, tu ilosc pikseli)

if (dis > len)

return 0;

else

return 1;

}

 

x1 = min(p1.x, p2.x);

x2 = max(p1.x, p2.x);

y1 = min(p1.y, p2.y);

y2 = max(p1.y, p2.y);

 

if (r.x < x1 || r.x > x2 || r.y < y1 || r.y > y2)

{

with(r) instance_destroy();

return 0;

}

 

x1 = min(p3.x, p4.x);

x2 = max(p3.x, p4.x);

y1 = min(p3.y, p4.y);

y2 = max(p3.y, p4.y);

 

if (r.x < x1 || r.x > x2 ||r.y < y1 || r.y > y2)

{

with(r) instance_destroy();

return 0;

}

 

r.prev = argument0;

r.next = argument1;

 

return 1;

 

Crossing:

GML

/***********************************************

Wyznacza punkt przeciecia dwoch prostych

 

argument0: x P1

argument1: y P1

argument2: x P2

argument3: y P2

 

argument4: x P3

argument5: y P3

argument6: x P4

argument7: y P4

 

argument8: id obiektu, w ktorych zapisany zostanie wynik (w jego wsporzednych)

 

Zwracane wartosc:

0: nie ma, badz podane proste sa takie same

1: punkt znaleziony i zapisany

***********************************************/

 

//rownania prostej

var a1, b1, c1, a2, b2, c2, wg, wx, wy;

 

//skroty

var x1, y1, x2, y2, x3, y3, x4, y4;

 

//punkt przeciecia

var xp, yp;

 

x1 = argument0;

y1 = argument1;

x2 = argument2;

y2 = argument3;

 

x3 = argument4;

y3 = argument5;

x4 = argument6;

y4 = argument7;

 

 

a1 = y2 - y1;

b1 = x1 - x2;

c1 = x1 * y2 - x2 * y1;

 

a2 = y4 - y3;

b2 = x3 - x4;

c2 = x3 * y4 - x4 * y3;

 

wg = a1*b2 - a2*b1;

wx = c1*b2 - c2*b1;

wy = a1*c2 - a2*c1;

 

//rownolegle proste nas nie obchodza

if (wg == 0 && wx !=0 && wy != 0)

{

return 0;

}

 

if (wg == 0 && wx == 0 && wy == 0)

argument8.same = 1;

else

argument8.same = 0;

 

xp = wx/wg;

yp = wy/wg;

 

argument8.x = wx/wg;

argument8.y = wy/wg;

 

return 1;

 

Musisz miec pusty obiekt result z zmienna same. W nim zapisza sie wyniki crossing (punkt przeciecia prostych), z ktorych skrypt do sprawdzania przecinania sie dwoch odcinkow.

[Marek.S]

Tymon użył równania dla prostych...

nie uwzględnia długości odcinka. =P

[Cekol]

Nicolas , a nie dało by się bez tego obiektu ? :(

żeby były same zmienne i matematyka.

 

Nie muszę mieć tego punktu przecięcia odcinków, tylko samo, czy linie się przecinają :)

[Nicolas]

Takim sposobem byloby to zbyt przekombinowane, ale sa na pewno inne. Ja sprawdzam czy punkt przeciecia prostych, na ktorych leza te odcinki nalezy do obu odcinkow. Obiekt traktuje jako zbior 3 zmiennych (x, y, same). Niby moglbym rozdzielic to na 3 skrypty (sprawdzajacy czy same, liczacy x i liczacy y), ale to przesada. Inne wyjscie to zapisanie wyniku do jednej zmiennej za pomoca przesuniec bitowych, ale (zakladajac, ze zmienna ma 4 bajty), 1 bit poszedlby na same i po 15 na x i y (1 by sie zmarnowal). W takim wypadku x i y musialyby byc mniejsze od 32768. Jezeli takie ograniczenia nie przeszkadzaja mozna zmienic.

 

Jezeli jednak nie potrzebujesz punktu przeciecia zrob cos takiego:

http://www.math.us.edu.pl/~pgladki/faq/node104.html