Back to index

nux  3.0.0
Algo.cpp
Go to the documentation of this file.
00001 /*
00002  * Copyright 2010-2012 Inalogic® Inc.
00003  *
00004  * This program is free software: you can redistribute it and/or modify it
00005  * under the terms of the GNU Lesser General Public License, as
00006  * published by the  Free Software Foundation; either version 2.1 or 3.0
00007  * of the License.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranties of
00011  * MERCHANTABILITY, SATISFACTORY QUALITY or FITNESS FOR A PARTICULAR
00012  * PURPOSE.  See the applicable version of the GNU Lesser General Public
00013  * License for more details.
00014  *
00015  * You should have received a copy of both the GNU Lesser General Public
00016  * License along with this program. If not, see <http://www.gnu.org/licenses/>
00017  *
00018  * Authored by: Jay Taoko <jaytaoko@inalogic.com>
00019  *
00020  */
00021 
00022 #include "../NuxCore.h"
00023 #include "MathInc.h"
00024 
00025 
00026 namespace nux
00027 {
00028 
00029   int PointInside2DPolygon(Point2* polygon, int n, Point2 pt, const int onedge)
00030   {
00031     nuxAssert(n > 3);
00032     if(n < 3)
00033       return 0;
00034     //cross points count of x
00035     int __count = 0;
00036 
00037     //neighbor bound vertices
00038     Point2D<float> p1, p2;
00039 
00040     //left vertex
00041     p1 = polygon[0];
00042 
00043     //check all rays
00044     for(int i = 1; i <= n; ++i)
00045     {
00046       //point is an vertex
00047       if(pt == p1) return onedge;
00048 
00049       //right vertex
00050       p2 = polygon[i % n];
00051 
00052       //ray is outside of our interests
00053       if(pt.y < Min<float>(p1.y, p2.y) || pt.y > Max<float>(p1.y, p2.y))
00054       {
00055         //next ray left point
00056         p1 = p2; continue;
00057       }
00058 
00059       //ray is crossing over by the algorithm (common part of)
00060       if(pt.y > Min<float>(p1.y, p2.y) && pt.y < Max<float>(p1.y, p2.y))
00061       {
00062         //x is before of ray
00063         if(pt.x <= Max<float>(p1.x, p2.x))
00064         {
00065           //overlies on a horizontal ray
00066           if(p1.y == p2.y && pt.x >= Min<float>(p1.x, p2.x)) return onedge;
00067 
00068           //ray is vertical
00069           if(p1.x == p2.x)
00070           {
00071             //overlies on a ray
00072             if(p1.x == pt.x) return onedge;
00073             //before ray
00074             else ++__count;
00075           }
00076 
00077           //cross point on the left side
00078           else
00079           {
00080             //cross point of x
00081             double xinters = (pt.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
00082 
00083             //overlies on a ray
00084             if(fabs(pt.x - xinters) < constants::dbl_epsilon) return onedge;
00085 
00086             //before ray
00087             if(pt.x < xinters) ++__count;
00088           }
00089         }
00090       }
00091       //special case when ray is crossing through the vertex
00092       else
00093       {
00094         //p crossing over p2
00095         if(pt.y == p2.y && pt.x <= p2.x)
00096         {
00097           //next vertex
00098           const Point2& p3 = polygon[(i+1) % n];
00099 
00100           //pt.y lies between p1.y & p3.y
00101           if(pt.y >= Min<float>(p1.y, p3.y) && pt.y <= Max<float>(p1.y, p3.y))
00102           {
00103             ++__count;
00104           }
00105           else
00106           {
00107             __count += 2;
00108           }
00109         }
00110       }
00111 
00112       //next ray left point
00113       p1 = p2;
00114     }
00115 
00116     //EVEN
00117     if(__count % 2 == 0) return(0);
00118     //ODD
00119     else return(1);
00120   }
00121 }
00122