### Sweep line algorithm applied to segment intersection

Hello! I need advice on updating binary search three. I am working on implementation of Bentley-Ottoman algorithm for finding intersections of line segments in the plane. Code I designed works properly for all, but certain types of triangles. What is happening is that one intersection inside the triangle is never detected due to a fact that segments which intersect in that point never become neighbors in binary search tree. Anyone got an idea how to resolve this problem? Thank you :)
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205`` ``````class segment{ double x1,y1,x2,y2; int name; double nosac[3]; public: segment():x1(0),y1(0),x2(0),y2(0),name(0){nosac[0]=nosac[1]=nosac[2]=0;} segment(double X1,double Y1,double X2,double Y2); void asign_name(int NAME){name=NAME;} int return_name(){return name;} int position(vector point); vector left(){vector P(2); P[0]=x1; P[1]=y1; return P;} vector right(){vector K(2); K[0]=x2; K[1]=y2; return K;} friend vector intersect(segment a, segment b); friend segment vrati_segment(vector S, int name); friend bool kriterij_yY(segment a, segment b); friend class kriterij_xXYy; }; segment::segment(double X1,double Y1,double X2,double Y2):name(0){ if(X1X2){x1=X2; y1=Y2; x2=X1; y2=Y1;} else{ if(Y1>Y2){x1=X1; y1=Y1; x2=X2; y2=Y2;} else if (Y1 t){ if(x1==t[0] && y1==t[1])return 0; else if(x2==t[0] && y2==t[1])return 2; else if(min(x1,x2)<=t[0] && t[0]<=max(x1,x2) && min(y1,y2)<=t[1] && t[1]<=max(y1,y2) && (t[1]-y1)*(x2-x1)-(t[0]-x1)*(y2-y1)==0)return 1; else return -1; } vector intersect(segment a, segment b){ vector N; double p=b.nosac[0]*a.nosac[1]-a.nosac[0]*b.nosac[1]; if(!p){ N.push_back(0); N.push_back(0); N.push_back(0); } else{ N.push_back((b.nosac[1]*a.nosac[2]-a.nosac[1]*b.nosac[2])/p); N.push_back((a.nosac[0]*b.nosac[2]-b.nosac[0]*a.nosac[2])/p); if(min(a.x1,a.x2)<=N[0] && min(b.x1,b.x2)<=N[0] && max(a.x1,a.x2)>=N[0] && max(b.x1,b.x2)>=N[0] && min(a.y1,a.y2)<=N[1] && min(b.y1,b.y2)<=N[1] && max(a.y1,a.y2)>=N[1] && max(b.y1,b.y2)>=N[1])N.push_back(1); else N.push_back(0); } return N; } segment vrati_segment(vector S, int NAME){ segment pom; for(int i=0; ib.y1)) || ((a.y1==b.y1 && a.x1==b.x1) && (a.x2!=b.x2 || a.y2!=b.y2)));} }; class prioritet{ public: bool operator()(vector a, vector b)const {return a[0]>b[0] || (a[0]==b[0] && a[1]b.x1)) || ((a.y1==b.y1 && a.x1==b.x1) && (a.x2!=b.x2 || a.y2!=b.y2))); } bool uQ (priority_queue ,vector >,prioritet> Q, vector point){ bool nalazise(false); while(!Q.empty() && !nalazise){ vector pom; pom=Q.top(); Q.pop(); if(pom==point)nalazise=true; } return nalazise; } void napuniQ(vector &S, priority_queue,vector >,prioritet> &Q){ for(int i=0; i rub; rub=(S[i]).left(); if(!uQ(Q,rub))Q.push(rub); rub=(S[i]).right(); if(!uQ(Q,rub))Q.push(rub); } } vector< vector > sweep_line(vector &S){ vector > P; priority_queue ,vector >,prioritet> Q; napuniQ(S,Q); set T; set :: iterator Ti; while(!Q.empty()){ vector point; point=Q.top(); Q.pop(); vector Lr,Tr,Dr; for(int i=0; i lUt,lUtUd,dUt; merge(Lr.begin(),Lr.end(),Tr.begin(),Tr.end(),inserter(lUt,lUt.begin()),kriterij_yY); merge(lUt.begin(),lUt.end(),Dr.begin(),Dr.end(),inserter(lUtUd,lUtUd.begin()),kriterij_yY); merge(Dr.begin(),Dr.end(),Tr.begin(),Tr.end(),inserter(dUt,dUt.begin()),kriterij_yY); if(lUtUd.size()>1){ P.push_back(point); // ---> intersection detected } vector > za_azuriranje; vector az; int rbr_s, rbr_pr, rbr_slj; for(int i=0; i > azuriraj; for(int i=0; i pres; if(lUt.empty()){ for(int i=0; ipoint[0] || (pres[0]==point[0] && pres[1]point[0] || (pres[0]==point[0] && pres[1]point[0] || (pres[0]==point[0] && pres[1]
Last edited on
Isn't there anyone who was working on this problem out there? I could really use some insight in what is going wrong here.
Topic archived. No new replies allowed.