Andos 124 Report post Posted March 20, 2002 Please show me some simple formulas to find out if a point is in a deformed square. ( a square polygon ) I''ve seen LOTS of tutorials to make the point in polygon tests but I don''t understand anything of it... I''m from Denmark and I''m only 16 years old... 0 Share this post Link to post Share on other sites

Yann L 1802 Report post Posted March 20, 2002 quote:Please show me some simple formulas to find out if a point is in a deformed square There is no ''simple'' one. For a standard bounding rectangle it''s trivial. But as soon as it becomes a general polygon, it''s more complex.The simplest way would be to treat the quad as two triangles and perform a point in triangle test, which is not that problematic. This would also allow concave quads. You''ll get point in triangle tests on almost any computational geometry page (read: Google), it''s a standard algorithm. 0 Share this post Link to post Share on other sites

LilMikey 122 Report post Posted March 20, 2002 For a point in polygon test, couldn''t you take the normalized normal of the triangle / polygon and the normalized normal of point + 2 verticies of the triangle / polygon and if they''re equal, it''s in the triangle, if they aren''t it''s not? If you wind it right, a coplanar point in the polygon will have the same normal and a coplanar point outside the polygon will have the inverse of it''s normal.Please...It''s a question, not an answer. 0 Share this post Link to post Share on other sites

Yann L 1802 Report post Posted March 20, 2002 Hmm, well it kind of works. You''ll have to be very carefull when selecting the 2 reference vertices, or it might fail. It won''t work on concave polygons.This is the easiest and fastest point-in-triangle code I know of. It uses a somewhat similar method to yours, but takes all points into account to determine normal (vertex ordering) differences. It only works on triangles. If you want to use it for arbitrary polygons (incl. concave), triangulate them first. //----------------------------------------------------------------------------// CHECKS IF 2D POINT P IS IN TRIANGLE ABC. RETURNS 1 IF IN, 0 IF OUT// Given a triangle ABC and a point P, determines if P is inside// of ABC (regardless of vertex ordering - CCW or CW). 2D version only, but// this handles the 3D case if appropriately projected to the XY, YZ, or XZ// planes (by dropping corresponding component; i.e. drop Z in XY projection).//----------------------------------------------------------------------------int Pt2dInTri(Vect2d A, Vect2d B, Vect2d C, Vect2d P){ // FIRST CHECK THE SIGN OF THE Z-COMPONENT OF THE NORMAL BY CALCULATING // THE CROSS-PRODUCT (ABxBC). THIS WILL DETERMINE THE ORDERING OF THE // VERTICES. IF NEGATIVE, VERTICES ARE CLOCKWISE ORDER; OTHERWISE CCW. // THEN EVALUATE SIGN OF Z-COMPONENTS FOR ABxAP, BCxBP, and CAxCP TO // DETERMINE IF P IS IN "INSIDE" HALF-SPACE FOR EACH EDGE IN TURN ("INSIDE" // IS DETERMINED BY SIGN OF Z OF NORMAL (VERTEX ORDERING). // NOTE: FULL CROSS-PRODS ARE NOT REQUIRED; ONLY THE Z-COMPONENTS Vect2d dAB=B-A, dBC=C-B; // "REPEATS" if ((dAB.x*dBC.y-dAB.y*dBC.x) < 0) // CW { if (dAB.x*(P.y-A.y) >= dAB.y*(P.x-A.x)) return(0); // ABxAP if (dBC.x*(P.y-B.y) >= dBC.y*(P.x-B.x)) return(0); // BCxBP if ((A.x-C.x)*(P.y-C.y) >= (A.y-C.y)*(P.x-C.x)) return(0); // CAxCP } else // CCW { if (dAB.x*(P.y-A.y) < dAB.y*(P.x-A.x)) return(0); // ABxAP if (dBC.x*(P.y-B.y) < dBC.y*(P.x-B.x)) return(0); // BCxBP if ((A.x-C.x)*(P.y-C.y) < (A.y-C.y)*(P.x-C.x)) return(0); // CAxCP } return(1); // "INSIDE" EACH EDGE''S IN-HALF-SPACE (PT P IS INSIDE TRIANGLE) }; 0 Share this post Link to post Share on other sites

Andos 124 Report post Posted March 21, 2002 I don''t understand this.You use complicated english.Trivial, vertices, concave, arbitary, coplanar, inverse of it''s normal?What does this mean? 0 Share this post Link to post Share on other sites

Guest Anonymous Poster Report post Posted March 21, 2002 convex polygon:walk through every edge (side, line whatever its called) of the polygon, and test the point against it. if it''s on the left side of every line in the polygon (or directly on the line if you will), the point is inside. 0 Share this post Link to post Share on other sites

Andos 124 Report post Posted March 21, 2002 But how do I check if the dot is on the other side of the sides/lines?I''ve asked my math teacher but she didn''t know how to do it.Do you know any formulas or some other ways to find out? 0 Share this post Link to post Share on other sites

Yann L 1802 Report post Posted March 21, 2002 OK, so you want a point in polygon test for deformed squares (quads).Your polygon is something like:------------|A B|| || ||D C|------------ (Damn, I suck at ASCII, I hope this thing doesn''t screw up...)A,B,C,D are the 4 corner points (vertices) of your polygon.Now divide it into 2 triangles: A,B,C and A,C,D. just think of it, as if you would slice it in two halfs, with a line through A->C.Finally, you use the algorithm I posted earlier to test your point (P) against both triangles:if( Pt2dInTri(A, B, C, P) ) return(1); // point is in the first triangleif( Pt2dInTri(A, C, D, P) ) return(1); // point is in the second trianglereturn(0); // point is in neither one, so it is not in the polygon It will return 1, if the point P is in the quad A,B,C,D. 0 Share this post Link to post Share on other sites

Guest Anonymous Poster Report post Posted March 21, 2002 <<But how do I check if the dot is on the other side of the <<sides/lines?<<I''ve asked my math teacher but she didn''t know how to do it.<<Do you know any formulas or some other ways to find out? Andos, your math teacher sucks! :-)check out this link, it covers the thing i talked about before (on which side the point is in respect to the line):http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/ 0 Share this post Link to post Share on other sites

S1CA 1418 Report post Posted March 21, 2002 By coincidence this topic came up on GDAlgorithms recently. Eric Haines has done an article about point in polygon methods (and their relative performance):http://www.acm.org/pubs/tog/editors/erich/ptinpoly/ --Simon O''ConnorCreative Asylum Ltdwww.creative-asylum.com 0 Share this post Link to post Share on other sites

Andos 124 Report post Posted March 21, 2002 Yann L:I don''t understand you code here:if( Pt2dInTri(A, B, C, P) ) return(1);What is the mathematical formula?Like:if bla bla bla return (1)What does "p" do? It''s in the formula. 0 Share this post Link to post Share on other sites

Andos 124 Report post Posted March 21, 2002 Hey at maby you could write an extension for me. The extension SDK can be found at the download section of www.clickteam.comYou know... I''m making games with the Multimedia Fusion program and people that can code in C or something can make extensions to that. Creating those extension shold be an easy task for you hardcore programmers. Try out the demo for MMF 1.5 You''ll love it. Then you can understand how extensions work. 0 Share this post Link to post Share on other sites

Andos 124 Report post Posted March 21, 2002 Ahh. Forgot to explain what an extensions is... An extension for Multimedia Fusion is an object (.cox) file that can things that MMF can''t do. 0 Share this post Link to post Share on other sites

Yann L 1802 Report post Posted March 21, 2002 quote:I don't understand you code here:if( Pt2dInTri(A, B, C, P) ) return(1); It's just a function call to the Pt2dInTri() function I posted above.quote:What does "p" do? It's in the formula P are the coordinates of the point you want to test, if it is in the quad or not.quote:What is the mathematical formula?Like:if bla bla bla return (1) It's not that easy, I'm affraid. A point in polygon test is much too complex to be squeezed in a simple mathematical equation. It's an algorithm that requires lots of separate equations and conditional branching depending on their result. Can't put that into a single formula.What programming language do you use ?[Edit]S1CA: very nice article. The timing tables are interesting, gave me some ideas to optimize my collision detection...[edited by - Yann L on March 21, 2002 4:02:58 PM] 0 Share this post Link to post Share on other sites