有偿（300¥）：判断一个点是否在封闭形状内的算法

jasonzhu8888

1. 
   
2. struct Point
   
3. {
   
4.         float x;
   
5.         float y;
   
6. };
   
7. 
   
8. bool circle_contains(Point* p_center, float radius, float x, float y)
   
9. {
   
10.         float xx = p_center->x - x;
    
11.         float yy = p_center->y - y;
    
12.         return xx*xx + yy*yy <= radius*radius;
    
13. }
    
14. 
    
15. bool polygon_contains(Point* pypts,int num,float x, float y)
    
16. {
    
17.         int hits = 0;
    
18. 
    
19.         int n = num - 1;
    
20.         Point* plastpt = &pypts[n];
    
21.         float lastx = plastpt->x;
    
22.         float lasty = plastpt->y;
    
23.         float curx, cury;
    
24. 
    
25.         for (int i = 0; i < n; lastx = curx, lasty = cury, i++)
    
26.         {
    
27.                 Point* p = &pypts[i];
    
28.                 curx = p->x;
    
29.                 cury = p->y;
    
30. 
    
31.                 if (cury == lasty)
    
32.                 {
    
33.                         continue;
    
34.                 }
    
35. 
    
36.                 float leftx;
    
37.                 if (curx < lastx)
    
38.                 {
    
39.                         if (x >= lastx)
    
40.                         {
    
41.                                 continue;
    
42.                         }
    
43.                         leftx = curx;
    
44.                 }
    
45.                 else
    
46.                 {
    
47.                         if (x >= curx)
    
48.                         {
    
49.                                 continue;
    
50.                         }
    
51.                         leftx = lastx;
    
52.                 }
    
53. 
    
54.                 float test1, test2;
    
55.                 if (cury < lasty)
    
56.                 {
    
57.                         if (y < cury || y >= lasty)
    
58.                         {
    
59.                                 continue;
    
60.                         }
    
61.                         if (x < leftx)
    
62.                         {
    
63.                                 hits++;
    
64.                                 continue;
    
65.                         }
    
66.                         test1 = x - curx;
    
67.                         test2 = y - cury;
    
68.                 }
    
69.                 else
    
70.                 {
    
71.                         if (y < lasty || y >= cury)
    
72.                         {
    
73.                                 continue;
    
74.                         }
    
75.                         if (x < leftx)
    
76.                         {
    
77.                                 hits++;
    
78.                                 continue;
    
79.                         }
    
80.                         test1 = x - lastx;
    
81.                         test2 = y - lasty;
    
82.                 }
    
83. 
    
84.                 if (test1 < (test2 / (lasty - cury) * (lastx - curx)))
    
85.                 {
    
86.                         hits++;
    
87.                 }
    
88.         }
    
89. 
    
90.         return ((hits & 1) != 0);
    
91. }
    

复制代码

jasonzhu8888

polygon_containes 前面两个参数是输入的多边形坐标，最好首尾的点是同一个形成闭环，也即是输入点至少4个
如  (x0 y0)  (x1 y1) ... (x n-1  y n-1) (x0 y0)