C++ – Error, Implementing Winding Number Algorithm, (OpenGL, C++)

cgeometrygraphicsopengl

I am trying to implement the Winding Number Algorithm to test if a point is within another polygon. Although the results from my algorithm are wrong and not consistent. I have been working on this for ages now and it has become a bit of a pain!

I have basically converted pseudo code from notes and websites, such as, softsurfer.com

I successfully detect if my player and building object bounding boxes overlap. I return the result to a struct, (BoxResult) which lets me know if there has been a collision and returns the box which it has collided with (Below)

struct BoxResult{
bool collide;
Building returned;
};

void buildingCollision(){
int wn = 0;                         //winding number count
BoxResult detect = boxDetection();  //detect if any bounding boxes intersect
    if(detect.collide){ //If a bounding box has collided, excute Winding Number Algorithm.
        for(int i = 0; i < player.getXSize(); i++){
            Point p;
            p.x = player.getXi(i);
            p.y = player.getYi(i);
            wn = windingNum(detect.returned,p);
            cout << wn << endl;
            //Continue code to figure out rebound reaction
        }
    }
}

I then test for a collision between the building and the player (Below). I have tried 5 different attempts and hours of debugging to understand where the error is occuring, however I am implementing the most ineffienct method which just uses maths (Below).

      int windingNum(Building & b, Point & p){
int result = 0;             //Winding number is one, if point is in poly
float total;            //Counts the total angle between different vertexs
double wn;

    for(int i = 0; i <= b.getXSize()-1;i++){
    float acs, nom, modPV, modPV1, denom, angle;
        if(i ==  3){
                //Create the different points PVi . PVi+1
                Point PV, PV1;
                PV.x = (b.getXi(i) + wx) * p.x; 
                PV.y = (b.getYi(i) + wy) * p.y;
                PV1.x = (b.getXi(0) + wx) * p.x; 
                PV1.y = (b.getYi(0) + wy) * p.y;

                modPV = sqrt( (PV.x * PV.x) + (PV.y * PV.y));       //Get the modulus of PV
                modPV1 = sqrt( (PV1.x * PV1.x) + (PV1.y * PV1.y));  //Get modulus of PV1

                nom = (PV1.x * PV.x) + (PV1.y * PV.y);              //Dot product of PV and PV1
                denom = modPV * modPV1;     //denomintor of winding number equation
                angle = nom / denom;
                acs = acos(angle) * 180/PI;     //find the angle between the different points
                total = total + acs;        //add this angle, to the total angle count
            }
            if(i < 3){
                //Create the different points PVi . PVi+1
                Point PV, PV1;
                PV.x = (b.getXi(i) + wx) * p.x; 
                PV.y = (b.getYi(i) + wy) * p.y;
                PV1.x = (b.getXi(i+1) +wx) * p.x; 
                PV1.y = (b.getYi(i+1) +wy) * p.y;

                modPV = sqrt((PV.x * PV.x) + (PV.y * PV.y));        //Get the modulus of PV
                modPV1 = sqrt((PV1.x * PV1.x) + (PV1.y * PV1.y));   //Get modulus of PV1

                nom = (PV1.x * PV.x) + (PV1.y * PV.y);              //Dot product of PV and PV1
                denom = modPV * modPV1;     //denomintor of winding number equation
                angle = nom / denom;
                acs = acos(angle) * 180/PI;  //find the angle between the different points
                total = total + acs;        //add this angle, to the total angle count
                }
    }

    wn = total;
    if(wn < 360){
        result = 0;}
    if(wn == 360){
        result = 1;}

    return result;
}

For reasons I do not understand acs = acos(angle) always returns 1.#IND000.
Btw so you know, I am just testing the algorithm against another square, hence the two if statements if i == 3 and if i < 3.

Also incase you need to know these, wy and wx are the world co-ordinates which are translated. Thus moving the player around the world e.g. to move the player forward everything is translated by a minus number for wy.

Further, a Building object would look something like the following struct below:

struct Building {
vector<float> x;   //vector storing x co-ords
vector<float> y;   //vector storing y co-ords
float ymax, ymin, xmax, xmin //values for bounding box
vector<int> polygons; //stores the number points per polygon (not relevant to the problem)
}

If anyone can help I would amazingly grateful! I just wish I could see where it is all going wrong! (Something I am sure all programmers have said in there time lol) Thanks for readings…

Best Answer

The two lines calculating the modulus of PV and PV1 are incorrect. They should be

modPV  = sqrt(PV.x  * PV.x  + PV.y  * PV.y );
modPV1 = sqrt(PV1.x * PV1.x + PV1.y * PV1.y);

Does that fix the problem?