nux-1.16.0
|
00001 /* 00002 * Copyright 2010 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) < Const::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