點在面算法,就是放射線算法,原理很簡單,就是把一個點向任意方向發射（本程序是向下）,如果跟這個面有奇數個交點,證明點在面裡面,若是偶數個,則是在外面(包括0)，算法主要是優化效率。本人水平有限，算法中肯定有不足之處，請大家海涵！
主要函數如下。
1. struct TabPoint
2. {
3. private double x;
4. public double X
5. {
6. get { return x; }
7. set { x = value; }
8. }
9.
10. private double y;
11. public double Y
12. {
13. get { return y; }
14. set { y = value; }
15. }
16. }
17.
18. struct Polygon
19. {
20. public ArrayList pointsArray;
21. private double minx;
22. public double MinX
23. {
24. get { return minx; }
25. set { minx = value; }
26. }
27.
28. private double miny;
29. public double MinY
30. {
31. get { return miny; }
32. set { miny = value; }
33. }
34.
35. private double maxx;
36. public double MaxX
37. {
38. get { return maxx; }
39. set { maxx = value; }
40. }
41.
42. private double maxy;
43. public double MaxY
44. {
45. get { return maxy; }
46. set { maxy = value; }
47. }
48. }
49.
50. class Analyse
51. {
52. private readonly double dis = 0.0000000001;
53.
54. //返回值：true點在面內 false點在面外
55. public bool JudgeMeetPoint(TabPoint tpt, ArrayList polygonPtArray)
56. {
57.
58. int MeetPointNum = 0;
59.
60. int PolygonPtSize = polygonPtArray.Count;
61. for (int k = 1; k < PolygonPtSize; k++)
62. {
63. TabPoint pt1 = (TabPoint)polygonPtArray[k - 1];
64. TabPoint pt2 = (TabPoint)polygonPtArray[k];
65.
66. if (((tpt.X <= pt1.X && tpt.X >= pt2.X) ||
67. (tpt.X >= pt1.X && tpt.X <= pt2.X)) &
68. (tpt.Y >= pt1.Y || tpt.Y >= pt2.Y) &
69. (pt1.X != pt2.X && pt1.Y != pt2.Y))
70. {
71. //判斷點是否在線上
72. if (JudgePtInLine(pt1, pt2, tpt))
73. {
74. return true;
75. }
76.
77. //處理特殊情況，交點是端點的情況
78. double temp;
79. //temp相當於被除數(斜率的分母) 80. temp = pt1.X - pt2.X;
81. if (temp >= -dis && temp <= dis)
82. {
83. //處理交點情況
84. double dx = tpt.X - pt1.X;
85. if (dx >= -dis && dx <= dis)
86. {
87. int[] indexs = new int[2];
88. indexs[0] = 0;
89. indexs[1] = 0;
90. GetNotSame(polygonPtArray, k, ref indexs);
91. TabPoint linePt1, linePt2;
92. linePt1 = (TabPoint)polygonPtArray[indexs[0]];
93. linePt2 = (TabPoint)polygonPtArray[indexs[1]];
94. if (k > indexs[0])
95. {
96. break;
97. }
98. else
99. {
100. k = indexs[0] + 1;
101. }
102. if (tpt.Y > pt1.Y && ((tpt.X >= linePt1.X && tpt.X <= linePt2.X) ||
103. (tpt.X >= linePt2.X && tpt.X <= linePt1.X)))
104. MeetPointNum++;
105. }
106. }
107. else
108. {
109. double kk, bb;
110. double MeetPtY, MeetPtX;
111. kk = (pt1.Y - pt2.Y) / (pt1.X - pt2.X);
112. bb = pt1.Y - kk * pt1.X;
113. MeetPtY = kk * tpt.X + bb;
114. MeetPtX = tpt.X;
115. //處理特殊情況，交點是端點的情況
116. double dx, dy, dx2, dy2;
117. dx = MeetPtX - pt1.X;
118. dy = MeetPtY - pt1.Y;
119. dx2 = MeetPtX - pt2.X;
120. dy2 = MeetPtY - pt2.Y;
121. if ((dx >= -dis && dx <= dis && dy >= -dis
122. && dy <= dis))
123. {
124. TabPoint pt3;
125. if (k == 1)
126. {
127. pt3 = (TabPoint)polygonPtArray[PolygonPtSize - 2];
128. }
129. else
130. {
131. pt3 = (TabPoint)polygonPtArray[k - 2];
132. }
133. //提取交點的上下兩點分別在垂線的兩側
134. if (tpt.Y > MeetPtY && ((MeetPtX >= pt3.Y && MeetPtX <= pt2.X) ||
135. (MeetPtX >= pt2.X && MeetPtX <= pt3.X)))
136. MeetPointNum++;
137. }
138. else if (!(dx2 >= -dis && dx2 <= dis && dy2 >= -dis
139. && dy2 <= dis))
140. {
141. if (tpt.Y > MeetPtY)
142. MeetPointNum++;
143. }
144. }
145. }
146. }
147.
148. if (MeetPointNum % 2 == 1)
149. return true;
150. else
151. return false;
152. }
153. //判斷點是否在線上
154. private bool JudgePtInLine(TabPoint tpt1, TabPoint tpt2, TabPoint tpt)
155. {
156. double dx1 = GetDistance(tpt1, tpt2);
157. double dx2 = GetDistance(tpt, tpt1);
158. double dx3 = GetDistance(tpt, tpt2);
159. double dx = dx3 + dx2 - dx1;
160.
161. if (dx >= -0.0000000001 && dx <= 0.0000000001)
162. {
163. return true;
164. }
165. return false;
166. }
167. //求取兩點之間的距離
168. private double GetDistance(TabPoint tpt1, TabPoint tpt2)
169. {
170. double x = tpt1.X - tpt2.X;
171. if (x <= 0)
172. {
173. x = -x;
174. }
175. double y = tpt1.Y - tpt2.Y;
176. if (y <= 0)
177. {
178. y = -y;
179. }
180.
181. return System.Math.Sqrt(x * x + y * y);
182. }
183. //在鏈表中獲取x軸不相同的點
184. private void GetNotSame(ArrayList pointArray, int index, ref int[] indexs)
185. {
186. indexs[0] = indexs[1] = -1;
187. int size = pointArray.Count;
188. TabPoint buftpt, tpt;
189. tpt = (TabPoint)pointArray[index];
190.
191. for (int i = index; i < size; i++)
192. {
193. buftpt = (TabPoint)pointArray[i];
194. if (buftpt.X != tpt.X)
195. {
196. indexs[0] = i;
197. break;
198. }
199. }
200.
201. if (indexs[0] == -1)
202. {
203. for (int i = 0; i < size; i++)
204. {
205. buftpt = (TabPoint)pointArray[i];
206. if (buftpt.X != tpt.X)
207. {
208. indexs[0] = i;
209. break;
210. }
211. }
212. }
213.
214.
215. for (int j = index; j >= 0; j--)
216. {
217. buftpt = (TabPoint)pointArray[j];
218. if (buftpt.X != tpt.X)
219. {
220. indexs[1] = j;
221. break;
222. }
223. }
224. if (indexs[1] == -1)
225. {
226. for (int j = size - 1; j >= 0; j--)
227. {
228. buftpt = (TabPoint)pointArray[j];
229. if (buftpt.X != tpt.X)
230. {
231. indexs[1] = j;
232. break;
233. }
234. }
235. }
236. }
237.
238. public bool JudgeInRect(TabPoint minPt,TabPoint maxPt,TabPoint pt)
239. {
240. if (pt.X >= minPt.X && pt.X <= maxPt.X && pt.Y >= minPt.Y && pt.Y <= maxPt.Y)
241. {
242. return true;
243. }
244. else
245. {
246. return false;
247. }
248. }
