Hi, 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...