1 //判斷射線與也線段是否相交, 相交返回1，不相交返回0，在邊上返回-1
2 int IsIntersectant( CPoint ptStart, CPoint ptEnd, CPoint pd )
3 {
4 double tempx = 0;
5 double tempy = 0;
6 //記錄多邊形邊的端點坐標；
7 double startx = ptStart.x;
8 double starty = ptStart.y;
9 double endx = ptEnd.x;
10 double endy = ptEnd.y;
11
12 double maxX = startx;
13 double minX = endx;
14 if (startx<endx)
15 {
16 minX = startx;
17 maxX = endx;
18 }
19
20 //保證開始點在下(y坐標大)，作為下端點
21 if(starty<endy)
22 {
23 double temp=starty;
24 starty=endy;
25 endy=temp;
26 temp=startx;
27 startx=endx;
28 endx=temp;
29 }
30
31 //首先排除沒有交點的情況
32 if((pd.y>starty && pd.y>endy) || (pd.y<starty && pd.y<endy)) //水平射線在該直線段的上下兩端之外
33 {
34 return 0;
35 }
36 if(pd.x>startx && pd.x>endx) //水平射線的起點在該直線段的右邊
37 {
38 return 0;
39 }
40
41 //如果是水平線段，在線段上返回-1，否則返回0
42 if (starty ==endy)
43 {
44 if (pd.x<=maxX&&pd.x>=minX)
45 {
46 return -1;
47 }
48 return 0;
49 }
50
51 //判斷點pd是否是多邊形邊上的點，通過距離判斷
52 tempx = pd.x - startx;
53 tempy = pd.y - starty;
54 double dStartToX = sqrt(tempx*tempx+tempy*tempy);
55
56 tempx = pd.x - endx;
57 tempy = pd.y - endy;
58 double dXToEnd = sqrt(tempx*tempx+tempy*tempy);
59
60 tempx = startx - endx;
61 tempy = starty - endy;
62 double dStarToEnd = sqrt(tempx*tempx+tempy*tempy);
63
64 if (dStarToEnd == (dStartToX + dXToEnd))
65 {
66 return -1;
67 }
68
69 //h_x記錄點pd(x,y)引水平線與直線段所在直線的交點x坐標(直線坐標y=kx+b)
70 double h_x=(pd.y-starty)*(endx-startx)/(endy-starty)+startx;
71
72 if(pd.x>h_x)//pd點在交點的右邊，則射線與線段不相交
73 {
74 return 0;
75 }
76 if(pd.y==starty) //水平射線與直線段的上端點相交，不計交點，只考慮與直線段的下端點相交
77 {
78 return 0;
79 }
80
81 return 1;
82
83 }
84 BOOL PtInPolygon( CPoint *ptList, int ptCount, CPoint pd )
85 {
86 if (ptCount<3)
87 {
88 return FALSE;
89 }
90
91 int cross_num = 0;
92 int iFlag = 0;
93 //從點pd，向右引水平射線
94
95 for(int i=0;i<ptCount-1;i++)
96 {
97 iFlag = IsIntersectant(ptList[i], ptList[i+1], pd);
98 if (iFlag < 0)
99 {
100 return TRUE;
101 }
102 else
103 {
104 cross_num += iFlag;
105 }
106 }
107
108 //末端點與首端點連接線
109 iFlag = IsIntersectant(ptList[ptCount-1], ptList[0], pd);
110 if (iFlag < 0)
111 {
112 return TRUE;
113 }
114 else
115 {
116 cross_num += iFlag;
117 }
118
119 if(cross_num%2==1) //交點個數為奇
120 {
121 return TRUE;
122 }
123 else if(cross_num%2==0) //交點個數為偶
124 {
125 return FALSE;
126 }
127
128 return FALSE;
129
130 }

轉載于:https://www.cnblogs.com/hbf369/archive/2011/12/09/2281559.html

總結

以上是生活随笔為你收集整理的判断点是否在多边形内——射线法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。