c#版点在面内算法

c#版点在面内算法2010-12-19点在面算法,就是放射线算法,原理很简单,就是把一个点向任意方向发射（本程序是向下）,如果跟这个面有奇数个交点,证明点在面里面,若是偶数个,则是在外面（包括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.}