Я использую линию развертки по монотонным ребрам, когда вычисляю пересечение (у меня есть функция сортировки, которая сортирует ребра внутри конструктора, и я проверяю их в порядке), даже если я получаю в качестве пересечения некоторые точки вершины для некоторых ребер, хотя у меня есть много тестов для устранения этих случаев.
Это код для 4-го метода (который пока дает мне лучшие результаты, но не все пересечения, но, по крайней мере, некоторое хорошее пересечение по сравнению с другими):
//4 method
double* QSweep::findIntersection(edge_t edge1,edge_t edge2) {
point_t p1=myPoints_[edge1[0]];
point_t p2=myPoints_[edge1[1]];
point_t p3=myPoints_[edge2[0]];
point_t p4=myPoints_[edge2[1]];
double xD1,yD1,xD2,yD2,xD3,yD3,xP,yP,h,denom;
double* pt=new double[3];
// calculate differences
xD1=p2[0]-p1[0];
xD2=p4[0]-p3[0];
yD1=p2[1]-p1[1];
yD2=p4[1]-p3[1];
xD3=p1[0]-p3[0];
yD3=p1[1]-p3[1];
xP=-yD1;
yP=xD1;
denom=xD2*(-yD1)+yD2*xD1;
if (denom==0) {
return NULL;
}
else{
h=(xD3*(-yD1)+yD3*xD1)/denom;
}
std::cout<<"h is"<<h<<endl;
if ((h>0)&&(h<1)){
pt[0]=p3[0]+xD2*h;
pt[1]=p3[1]+yD2*h;
pt[2]=0.00;
}
else{
return NULL;
}
// return the valid intersection
return pt;
}
void QSweep:: intersection(){
nbIntersections=0;
double* vector;
for (int i=2;i<myEdges_.size()-1;i++){
vector=findIntersection(myEdges_[i-1],myEdges_[i]);
if (vector!=NULL){
nbIntersections++;
myIntersections.push_back(vector);
swap(myEdges_[i-1], myEdges_[i]);
}
}
}
Функция пересечения всегда одна и та же, поэтому я просто нахожу функцию findIntersection.
Для метода 1 и 2 я использую следующую версию функции findIntersection:
double* QSweep::computeIntersection(double m1, double b1, double m2, double b2){
double* v=new double[3];
v[0]= (b2-b1)/(m1-m2);
v[1]= (m1*b2-m2*b1)/(m1-m2);
v[2]=0.00;
return v;
}
double* QSweep::findIntersection(edge_t edge1, edge_t edge2){
//equation for the support line of the first edge
double a=myPoints_[edge1[0]][0];
double b=myPoints_[edge1[0]][1];
double c=myPoints_[edge1[1]][0];
double d=myPoints_[edge1[1]][1];
double m1=getSlope(a,b,c,d);
double b1=getYIntercept(a,b,c,d);
double x=myPoints_[edge2[0]][0];
double y=myPoints_[edge2[0]][1];
double s=myPoints_[edge2[1]][0];
double t=myPoints_[edge2[1]][1];
double m2=getSlope(x,y,s,t);
double b2=getYIntercept(x,y,s,t);
double* vector;
double line2InLine1=evalEqnLineD(myPoints_[edge2[0]],edge1);
double line2InLine1New=evalEqnLineD(myPoints_[edge2[1]],edge1);
double line1InLine2=evalEqnLineD(myPoints_[edge1[0]],edge2);
double line1InLine2New=evalEqnLineD(myPoints_[edge1[1]],edge2);
if (m1==m2){
return NULL;
}
else{
if ((line1InLine2*line1InLine2New)<0 && (line2InLine1*line2InLine1New)<0){
vector=computeIntersection(m1,b1,m2,b2);
if ((vector[0]>a && vector[0]<c)&&(vector[0]>x && vector[0]<s)){
return vector;
}
else{
return NULL;
}
}
else{
return NULL;
}
}
return vector;
}
Я начну снова с самого начала, чтобы увидеть, что общего у точек пересечения, которые я хочу, есть. Даже с некоторыми испытаниями я получаю не только хорошие точки пересечения, но и другие точки на графике, так что я действительно растерялся.