Databases
StackOverflow2013
Postsdbo
POError, Implementing Winding Number Algorithm, (OpenGL, C++)
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POError, Implementing Winding Number Algorithm, (OpenGL, C++)
    text
    copied!<p>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! </p> <p>I have basically converted pseudo code from notes and websites, such as, <a href="http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm#wn_PinPolygon()" rel="nofollow noreferrer">softsurfer.com</a></p> <p>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)</p> <pre><code>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 &lt; player.getXSize(); i++){ Point p; p.x = player.getXi(i); p.y = player.getYi(i); wn = windingNum(detect.returned,p); cout &lt;&lt; wn &lt;&lt; endl; //Continue code to figure out rebound reaction } } } </code></pre> <p>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).</p> <pre><code> int windingNum(Building &amp; b, Point &amp; 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 &lt;= 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 &lt; 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 &lt; 360){ result = 0;} if(wn == 360){ result = 1;} return result; } </code></pre> <p>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 &lt; 3. </p> <p>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.</p> <p>Further, a Building object would look something like the following struct below:</p> <pre><code>struct Building { vector&lt;float&gt; x; //vector storing x co-ords vector&lt;float&gt; y; //vector storing y co-ords float ymax, ymin, xmax, xmin //values for bounding box vector&lt;int&gt; polygons; //stores the number points per polygon (not relevant to the problem) } </code></pre> <p>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...</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload