当我计算交点时,我在单调边缘上使用扫描线(我有一个排序函数,它对构造函数内的边缘进行排序,我测试它们我有序),即使我获得了一些作为顶点的点作为交点一些边缘,即使我有很多测试来消除这种情况。
这是第四种方法的代码(它给了我迄今为止最好的结果,但不是所有的交叉点,但与其他方法相比至少有一些好的交叉点):
//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;
}
我会从头开始,看看我想要的交叉点有什么共同点。即使对一些测试很困难,我什至没有得到好的交点,而是图表上的其他点,所以我真的很困惑。