Kako rece filmil 01.06.2003.:
Citat:
Jednostavan način da se utvrdi da li se dve duži seku je da se ispita
položaj krajnjih tačaka jedne duži u odnosu na drugu duž. Preseka ne
može biti ako obe krajnje tačke leže sa iste strane duži.
Ima tome jedno 10 godina kako je u tadasnjim casopisu
"Racunari" (neka mi autor teksta oprosti - ime sam zaboravio)
bio resavan slican problem, a ja sam koju godinu kasnije imao prakticne potrebe da to sprovedem u delo.
Prvi deo problema je:
1. Da li se duzi AB(x1,y1, x2,y2) i CD(x3,y3, x4,y4) seku?
Evo tadasnjeg resenja u Turbo Pascalu:
Code:
Function Cross(x1,y1,x2,y2,x3,y3,x4,y4:Real):Boolean;
Var A1,B1,C1,A2,B2,C2:Real;
Begin
A1:=Y2-Y1; A2:=Y4-Y3; B1:=X2-X1; B2:=X4-X3;
C1:=(X1*Y2)-(X2*Y1); C2:=(X3*Y4)-(X4*Y3);
Cross:=(((A1*X3-B1*Y3-C1>0) Xor (A1*X4-B1*Y4-C1>0)) And
((A2*X1-B2*Y1-C2>0) Xor (A2*X2-B2*Y2-C2>0)));
End;
A evo sada i ceo program u C++:
Code:
#include <iostream>
#include <stdlib.h>
using namespace std;
bool Cross1(double x1,double y1,double x2,double y2, double x3,double y3,double x4,double y4);
int main(int argc, char *argv[])
{
if (Cross1(2,4,5,1, 2,2,4,6)) cout<<"Seku se!\n\n"; else cout<<"NE seku se!\n\n";
if (Cross1(2,4,5,1, 5,3,8,6)) cout<<"Seku se!\n\n"; else cout<<"NE seku se!\n\n";
system("PAUSE");
return 0;
}
bool Cross1(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4){
double a1,b1,c1,a2,b2,c2;
a1=y2-y1; a2=y4-y3; b1=x2-x1; b2=x4-x3;
c1=(x1*y2)-(x2*y1); c2=(x3*y4)-(x4*y3);
cout<<"AB: "<<x1<<"\t"<<y1<<"\t"<<x2<<"\t"<<y2<<endl; //ovo mozes izbaciti
cout<<"CD: "<<x3<<"\t"<<y3<<"\t"<<x4<<"\t"<<y4<<endl; //ovo mozes izbaciti
if ( ( ((a1*x3-b1*y3-c1)>0)||((a1*x4-b1*y4-c1)>0) ) &&
( ((a2*x1-b2*y1-c2)>0)||((a2*x2-b2*y2-c2)>0)) ) return true;
else return false;
}
Ovo ce ti kao rezultat ispisati:
AB: 2 4 5 1
CD: 2 2 4 6
Seku se!
AB: 2 4 5 1
CD: 5 3 8 6
NE seku se!
Press any key to continue . . .
Pa ti sad prodji kroz sve stranice pravougaonika, pa proveri..
Ako je uslov preseka da duz preseca pravougaonik ispunjen samo ako se oba temenae duzi nalaze van pravougaonika onda preboj broj preseka.
- Ako je paran onda se oba temena duzi nalaze van pravougaonika
- Ako je neparan onda je jedna tacke unutar pravougaonika.
- Ako je broj preseka == 0, onda naravno nema preseka...
Ovo ti inace vazi za sve poligone, a ne samo za pravougaonik.
Da li duž seče pravougaonik?
Re: Da li duž seče pravougaonik?