From f58535d13c6a6c2db9ed0a582d8d97c5bb8295b0 Mon Sep 17 00:00:00 2001 From: agv Date: Thu, 27 Jul 2017 16:34:17 +0300 Subject: [PATCH] 0028569: Improve the performance of 2d classifier (CSLib_Class2d) changes: CSLib_Class2d (header and source file) --- src/CSLib/CSLib_Class2d.cxx | 340 ++++++++++++++++++++++++------------ src/CSLib/CSLib_Class2d.hxx | 6 +- 2 files changed, 236 insertions(+), 110 deletions(-) diff --git a/src/CSLib/CSLib_Class2d.cxx b/src/CSLib/CSLib_Class2d.cxx index 35e84cba4c..0783f3d4d7 100644 --- a/src/CSLib/CSLib_Class2d.cxx +++ b/src/CSLib/CSLib_Class2d.cxx @@ -18,6 +18,7 @@ #include #include +#include #include static inline @@ -30,47 +31,92 @@ static inline //purpose : //======================================================================= CSLib_Class2d::CSLib_Class2d(const TColgp_Array1OfPnt2d& TP2d, - const Standard_Real aTolu, - const Standard_Real aTolv, + const Standard_Real theTolu, + const Standard_Real theTolv, const Standard_Real umin, const Standard_Real vmin, const Standard_Real umax, const Standard_Real vmax) + : MyPnts2d (NULL), + MyBoxes1d (NULL), + mySizeBox (0), + myNBoxes (0), + N (0) { - Umin=umin; - Vmin=vmin; - Umax=umax; - Vmax=vmax; // - if(umax<=umin || vmax<=vmin) { - MyPnts2dX=NULL; - MyPnts2dY=NULL; - N=0; - } - // - else { + if(umax > umin && vmax > vmin) + { Standard_Integer i, iLower; - Standard_Real du,dv,*Pnts2dX,*Pnts2dY, aPrc; + Standard_Real du,dv,*Pnts2dX,*Pnts2dY, aPrc; + Umin=umin; + Vmin=vmin; + Umax=umax; + Vmax=vmax; // aPrc=1.e-10; N = TP2d.Length(); - Tolu = aTolu; - Tolv = aTolv; - MyPnts2dX = new Standard_Real [N+1]; - MyPnts2dY = new Standard_Real [N+1]; + Tolu = theTolu; + Tolv = theTolv; + MyPnts2d = new Standard_Real [2*N+2]; + MyBoxes1d = NULL; + Pnts2dX = MyPnts2d; + Pnts2dY = Pnts2dX + 1; + du=umax-umin; dv=vmax-vmin; - Pnts2dX = (Standard_Real *)MyPnts2dX; - Pnts2dY = (Standard_Real *)MyPnts2dY; - // + iLower=TP2d.Lower(); - for(i = 0; i 63) { + const Standard_Integer aDegBox = static_cast + (0.5 * log2(static_cast(N-1))); + mySizeBox = 1 << aDegBox; + myNBoxes = (N + mySizeBox - 1) / mySizeBox; + MyBoxes1d = new Standard_Real[2 * myNBoxes]; + + Standard_Integer iBox(0), maskBox(mySizeBox-1); + const gp_Pnt2d& aP0 = TP2d(iLower); + Pnts2dX[0] = Transform2d(aP0.X(), umin, du); + Pnts2dY[0] = Transform2d(aP0.Y(), vmin, dv); + MyBoxes1d[0] = Pnts2dY[0]; + MyBoxes1d[1] = Pnts2dY[0]; + + for (i = 1; i MyBoxes1d[iBox+1]) + MyBoxes1d[iBox+1] = anY; + iBox+=2; + MyBoxes1d[iBox] = anY; + MyBoxes1d[iBox+1] = anY; + } + else if (anY < MyBoxes1d[iBox]) + MyBoxes1d[iBox] = anY; + else if (anY > MyBoxes1d[iBox+1]) + MyBoxes1d[iBox+1] = anY; + } + Pnts2dX[2*N]=Pnts2dX[0]; + Pnts2dY[2*N]=Pnts2dY[0]; + // now iBox must be equal to 2*myNBoxes-2 + if (Pnts2dY[0] < MyBoxes1d[iBox]) + MyBoxes1d[iBox] = Pnts2dY[0]; + if (Pnts2dY[0] > MyBoxes1d[iBox+1]) + MyBoxes1d[iBox+1] = Pnts2dY[0]; + } + else { + for(i = 0; iaPrc) { Tolu/=du; @@ -85,13 +131,13 @@ CSLib_Class2d::CSLib_Class2d(const TColgp_Array1OfPnt2d& TP2d, //purpose : //======================================================================= void CSLib_Class2d::Destroy() { - if(MyPnts2dX) { - delete [] (Standard_Real *)MyPnts2dX; - MyPnts2dX=NULL; + if(MyPnts2d) { + delete [] MyPnts2d; + MyPnts2d=NULL; } - if(MyPnts2dY) { - delete [] (Standard_Real *)MyPnts2dY; - MyPnts2dY=NULL; + if(MyBoxes1d) { + delete [] MyBoxes1d; + MyBoxes1d=NULL; } } @@ -186,41 +232,73 @@ Standard_Integer CSLib_Class2d::SiDans_OnMode(const gp_Pnt2d& P, Standard_Integer CSLib_Class2d::InternalSiDans(const Standard_Real Px, const Standard_Real Py) const { - Standard_Integer nbc, i, ip1, SH, NH; + Standard_Integer nbc, i, SH, NH; Standard_Real *Pnts2dX, *Pnts2dY; Standard_Real x, y, nx, ny; // nbc = 0; i = 0; - ip1 = 1; - Pnts2dX = (Standard_Real *)MyPnts2dX; - Pnts2dY = (Standard_Real *)MyPnts2dY; - x = (Pnts2dX[i]-Px); - y = (Pnts2dY[i]-Py); - SH = (y<0.)? -1 : 1; - // - for(i=0; i0. && nx>0.) { - nbc++; + NH = (ny<0.)? -1 : 1; + if(NH!=SH) { + if(x>0. && nx>0.) { + nbc++; + } + else { + if(x>0.0 || nx>0.) { + if((x-y*(nx-x)/(ny-y))>0.) { + nbc++; + } + } + } + SH = NH; } - else { - if(x>0.0 || nx>0.) { - if((x-y*(nx-x)/(ny-y))>0.) { - nbc++; - } - } + x = nx; y = ny; + } + } + else + { + // Find Y-boxes that include Py. Box with index iBox refers the range of + // points starting from iBox*sizeBox. + for (Standard_Integer iBox = 0; iBox < myNBoxes; iBox++) { + if ((MyBoxes1d[2*iBox] - Tolv - Py) * (MyBoxes1d[2*iBox+1] + Tolv - Py) < 0.) + { + Standard_Integer lastBox = (iBox + 1) * mySizeBox; + if (lastBox > N) + lastBox = N; + x = (Pnts2dX[2*iBox*mySizeBox]-Px); + y = (Pnts2dY[2*iBox*mySizeBox]-Py); + for (i = iBox*mySizeBox; i < lastBox; i++) + { + nx = Pnts2dX[2*(i+1)] - Px; + ny = Pnts2dY[2*(i+1)] - Py; + if (ny * y < 0.) { + if (x > 0. && nx > 0.) + nbc++; + else if (x > 0.0 || nx > 0.) { + if ((x - y*(nx-x)/(ny-y)) > 0.) + nbc++; + } + } + x = nx; y = ny; + } } - SH = NH; } - x = nx; y = ny; } return(nbc&1); } + //modified by NIZNHY-PKV Fri Jan 15 09:03:48 2010f //======================================================================= //function : InternalSiDansOuOn @@ -229,71 +307,117 @@ Standard_Integer CSLib_Class2d::InternalSiDans(const Standard_Real Px, Standard_Integer CSLib_Class2d::InternalSiDansOuOn(const Standard_Real Px, const Standard_Real Py) const { - Standard_Integer nbc, i, ip1, SH, NH, iRet; + Standard_Integer nbc, i, ip1, SH, NH, iRet = 0; Standard_Real *Pnts2dX, *Pnts2dY; Standard_Real x, y, nx, ny, aX; - Standard_Real aYmin; // nbc = 0; i = 0; ip1 = 1; - Pnts2dX = (Standard_Real *)MyPnts2dX; - Pnts2dY = (Standard_Real *)MyPnts2dY; - x = (Pnts2dX[i]-Px); - y = (Pnts2dY[i]-Py); - aYmin=y; - SH = (y<0.)? -1 : 1; - for(i=0; i-Tolu && ny-Tolv) { - iRet=-1; - return iRet; - } - //find Y coordinate of polyline for current X gka - //in order to detect possible status ON - Standard_Real aDx = (Pnts2dX[ip1] - Pnts2dX[ip1-1]); - if( (Pnts2dX[ip1-1] - Px) * nx < 0.) - { - - Standard_Real aCurPY = Pnts2dY[ip1] - (Pnts2dY[ip1] - Pnts2dY[ip1-1])/aDx *nx; - Standard_Real aDeltaY = aCurPY - Py; - if(aDeltaY >= -Tolv && aDeltaY <= Tolv) + Pnts2dX = MyPnts2d; + Pnts2dY = Pnts2dX + 1; + if (MyBoxes1d == NULL) + { + x = (Pnts2dX[0]-Px); + y = (Pnts2dY[0]-Py); + SH = (y<0.)? -1 : 1; + for(i=0; i-Tolu && ny-Tolv) { + iRet=-1; + return iRet; + } + //find Y coordinate of polyline for current X gka + //in order to detect possible status ON + Standard_Real aDx = (Pnts2dX[2*ip1] - Pnts2dX[2*(ip1-1)]); + if( (Pnts2dX[2*(ip1-1)] - Px) * nx < 0.) { - iRet=-1; - return iRet; + + Standard_Real aCurPY = + Pnts2dY[2*ip1] - (Pnts2dY[2*ip1] - Pnts2dY[2*(ip1-1)])/aDx *nx; + Standard_Real aDeltaY = aCurPY - Py; + if(aDeltaY >= -Tolv && aDeltaY <= Tolv) + { + iRet=-1; + return iRet; + } } - } - // + // - NH = (ny<0.)? -1 : 1; - if(NH!=SH) { - if(x>0. && nx>0.) { - nbc++; + NH = (ny<0.)? -1 : 1; + if(NH!=SH) { + if(x>0. && nx>0.) { + nbc++; + } + else { + if(x>0. || nx>0.) { + aX=x-y*(nx-x)/(ny-y); + if(aX>0.){ + nbc++; + } + } + } + SH = NH; } - else { - if(x>0. || nx>0.) { - aX=x-y*(nx-x)/(ny-y); - if(aX>0.){ - nbc++; - } - } - } - SH = NH; - } - else {// y has same sign as ny - if (ny N) + lastBox = N; + x = (Pnts2dX[2*iBox*mySizeBox]-Px); + y = (Pnts2dY[2*iBox*mySizeBox]-Py); + for (i = iBox*mySizeBox; i < lastBox; i++) + { + nx = Pnts2dX[2*(i+1)] - Px; + ny = Pnts2dY[2*(i+1)] - Py; + if (nx * nx < aTolu2 && ny * ny < aTolv2) { + iRet = -1; + break; + } + //find Y coordinate of polyline for current X gka + //in order to detect possible status ON + if (x /*(Pnts2dX[2*(ip1-1)] - Px)*/ * nx < 0.) + { + const Standard_Real aDeltaY = ny - (ny - y)/(nx - x) * nx; + if (aDeltaY*aDeltaY <= aTolv2) { + iRet = -1; + break; + } + } + if (ny * y < 0.) { + if (x > 0. && nx > 0.) + nbc++; + else if (x > 0. || nx > 0.) { + if ((x - y*(nx-x)/(ny-y)) > 0.) + nbc++; + } + } + x = nx; y = ny; + } // for(.. i ..) + if (iRet < 0) + break; } - } - x = nx; y = ny; - }// for(i=0; i