程式隨筆
0%

【四元樹】透過四元樹搜尋範圍內的座標

Posted on Edited on Disqus:

將之前四元樹的程式改良後寫成筆記，之後用到才不會忘記 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/// <summary>
    /// Class QuadTreeNode.
    /// </summary>
    public class QuadTreeNode<T>
        where T : IQuadTreeNodeData
    {
        /// <summary>
        /// 西北象限.
        /// </summary>
        /// <value>
        /// The north west.
        /// </value>
        public QuadTreeNode<T> NorthWest { get; set; }
        /// <summary>
        /// 東北象限.
        /// </summary>
        /// <value>
        /// The north east.
        /// </value>
        public QuadTreeNode<T> NorthEast { get; set; }
        /// <summary>
        /// 西南象限.
        /// </summary>
        /// <value>
        /// The south west.
        /// </value>
        public QuadTreeNode<T> SouthWest { get; set; }
        /// <summary>
        /// 東南象限.
        /// </summary>
        /// <value>
        /// The south east.
        /// </value>
        public QuadTreeNode<T> SouthEast { get; set; }

        /// <summary>
        /// 邊界
        /// </summary>
        public BoundingBox BoundingBox { get; set; }

        /// <summary>
        /// 節點數量
        /// </summary>
        public int BucketCapacity { get; set; }

        /// <summary>
        /// 節點
        /// </summary>
        public List<T> Points { get; set; }

        /// <summary>
        /// Initializes a new instance of the <see cref="QuadTreeNode{T}"/> class.
        /// </summary>
        /// <param name="boundingBox">The bounding box.</param>
        /// <param name="capacity">The capacity.</param>
        public QuadTreeNode(BoundingBox boundingBox, int capacity)
        {
            BoundingBox = boundingBox;
            BucketCapacity = capacity;
            Points = new List<T>();
        }
    }

要使用四元樹，就要將資料結點實作這個介面 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/// &lt;summary&gt;
    /// Interface IQuadTreeNodeData.
    /// &lt;/summary&gt;
    public interface IQuadTreeNodeData
    {
        /// &lt;summary&gt;
        /// Gets or sets the position.
        /// &lt;/summary&gt;
        /// &lt;value&gt;
        /// The position.
        /// &lt;/value&gt;
        Coordinate Position { get; set; }
    }

要搜尋範圍的DTO 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/// <summary>
    /// Class BoundingBox.
    /// </summary>
    public class BoundingBox
    {
        /// <summary>
        /// 左上角節點
        /// </summary>
        public Coordinate LeftTop { get; set; }

        /// <summary>
        /// 右下角節點
        /// </summary>
        public Coordinate RightBottom { get; set; }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/// <summary>
    /// Class Coordinate.
    /// </summary>
    public class Coordinate
    {
        /// <summary>
        /// 緯度
        /// </summary>
        public double Latitude { get; set; }
        /// <summary>
        /// 經度
        /// </summary>
        public double Longitude { get; set; }
    }

四元樹搜尋邏輯 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
/// <summary>
    /// Class QuadTreeService.
    /// </summary>
    public static class QuadTreeService
    {
        /// <summary>
        /// Inserts the specified node.
        /// </summary>
        /// <param name="node">The node.</param>
        /// <param name="data">The data.</param>
        /// <returns></returns>
        public static bool Insert<T>(QuadTreeNode<T> node, T data)
            where T : IQuadTreeNodeData
        {
            // Bail if our coordinate is not in the boundingBox
            if (!CheckBoundingBoxContainData(node.BoundingBox, data))
            {
                return false;
            }

            // Add the coordinate to the points array
            if ((node.Points.Count + 1) <= node.BucketCapacity)
            {
                node.Points.Add(data);
                return true;
            }

            // Check to see if the current node is a leaf, if it is, split
            if (node.NorthWest == null)
            {
                Subdivide(node);
            }

            // Traverse the tree
            if (Insert(node.NorthWest, data)) return true;
            if (Insert(node.NorthEast, data)) return true;
            if (Insert(node.SouthWest, data)) return true;
            if (Insert(node.SouthEast, data)) return true;

            return false;
        }

        /// <summary>
        /// 搜尋在範圍內的所有節點
        /// </summary>
        /// <param name="node">四元樹節點</param>
        /// <param name="range">範圍</param>
        /// <param name="datas"></param>
        public static void SearchDataInRange<T>(
            QuadTreeNode<T> node, 
            BoundingBox range, 
            ref List<T> datas)
            where T : IQuadTreeNodeData
        {
            //如果QuadTree完全在要搜尋的Range之內，
            //那包含在它底下的分裂節點都不用判斷,一定全部都在範圍內
            if (CheckBoundingBoxIncludeInRange(node.BoundingBox, range))
            {
                GetNodeAllPointData(node, ref datas);
                return;
            }

            // If range is not contained in the node's boundingBox then bail
            if (!CheckIntersectionBoundingBox(node.BoundingBox, range))
            {
                return;
            }

            foreach (var item in node.Points)
            {
                // Gather points contained in range
                if (CheckBoundingBoxContainData(range, item))
                {
                    datas.Add(item);
                }
            }

            // Bail if node is leaf
            if (node.NorthWest == null)
            {
                return;
            }

            // Otherwise traverse down the tree
            SearchDataInRange(node.NorthWest, range, ref datas);
            SearchDataInRange(node.NorthEast, range, ref datas);
            SearchDataInRange(node.SouthWest, range, ref datas);
            SearchDataInRange(node.SouthEast, range, ref datas);
        }

        /// <summary>
        /// 建立四元樹.
        /// </summary>
        /// <param name="data">The data.</param>
        /// <param name="boundingBox">QuadTree Bounding</param>
        /// <returns></returns>
        public static QuadTreeNode<T> CreateQuadTree<T>(List<T> data, BoundingBox boundingBox)
            where T : IQuadTreeNodeData
        {
            var TreeNode = new QuadTreeNode<T>(
                boundingBox: boundingBox,
                capacity: 1);

            foreach (var d in data)
            {
                Insert(TreeNode, d);
            }

            return TreeNode;
        }

        /// <summary>
        /// 取得節點以及所有子節點的Point Data
        /// </summary>
        /// <param name="node">The node.</param>
        /// <param name="datas">The datas.</param>
        static void GetNodeAllPointData<T>(QuadTreeNode<T> node, ref List<T> datas)
            where T : IQuadTreeNodeData
        {
            datas.AddRange(node.Points);

            if (node.NorthWest == null)
            {
                return;
            }
            GetNodeAllPointData(node.NorthWest, ref datas);
            GetNodeAllPointData(node.NorthEast, ref datas);
            GetNodeAllPointData(node.SouthWest, ref datas);
            GetNodeAllPointData(node.SouthEast, ref datas);
        }

        /// <summary>
        /// 確認兩個區域是否有交集
        /// </summary>
        /// <param name="BoundingBox">The bounding box.</param>
        /// <param name="range">The range.</param>
        /// <returns></returns>
        static bool CheckIntersectionBoundingBox(BoundingBox BoundingBox, BoundingBox range)
        {

            if (BoundingBox.LeftTop.Latitude.ToString() == BoundingBox.RightBottom.Latitude.ToString() &&
                BoundingBox.LeftTop.Longitude.ToString() == BoundingBox.RightBottom.Longitude.ToString())
            {
                //Point
                var Lng =  range.LeftTop.Longitude <= BoundingBox.LeftTop.Longitude &&
                           BoundingBox.LeftTop.Longitude <= range.RightBottom.Longitude;

                var Lat =  range.RightBottom.Latitude <= BoundingBox.LeftTop.Latitude &&
                           BoundingBox.LeftTop.Latitude <= range.LeftTop.Latitude;
                return Lng && Lat;
            }
            else
            {
                var MinCx = Math.Max(range.LeftTop.Longitude, BoundingBox.LeftTop.Longitude);
                var MaxCy = Math.Min(range.LeftTop.Latitude, BoundingBox.LeftTop.Latitude);

                var MaxCx = Math.Min(range.RightBottom.Longitude, BoundingBox.RightBottom.Longitude);
                var MinCy = Math.Max(range.RightBottom.Latitude, BoundingBox.RightBottom.Latitude);

                return (MinCx < MaxCx) && (MinCy < MaxCy);
            }
        }

        /// <summary>
        /// 確認BoundingBox是否完全包含在要搜尋的區域範圍內(小於等於).
        /// </summary>
        /// <param name="BoundingBox">The bounding box.</param>
        /// <param name="range">The range.</param>
        /// <returns></returns>
        static bool CheckBoundingBoxIncludeInRange(BoundingBox BoundingBox, BoundingBox range)
        {
            var LTLng = (range.LeftTop.Longitude <= BoundingBox.LeftTop.Longitude &&
                        BoundingBox.LeftTop.Longitude <= range.RightBottom.Longitude);

            var LTLat = (range.RightBottom.Latitude <= BoundingBox.LeftTop.Latitude &&
                        BoundingBox.LeftTop.Latitude <= range.LeftTop.Latitude);

            var RBLng = (range.LeftTop.Longitude <= BoundingBox.RightBottom.Longitude &&
                        BoundingBox.RightBottom.Longitude <= range.RightBottom.Longitude);

            var RBLat = (range.RightBottom.Latitude <= BoundingBox.RightBottom.Latitude &&
                        BoundingBox.RightBottom.Latitude <= range.LeftTop.Latitude);

            return LTLng && LTLat && RBLng && RBLat;
        }

        static bool CheckBoundingBoxContainData(BoundingBox boundingBox, IQuadTreeNodeData data)
        {
            var CheckLng = (boundingBox.LeftTop.Longitude <= data.Position.Longitude &&
                            data.Position.Longitude <= boundingBox.RightBottom.Longitude);

            var CheckLat = (boundingBox.RightBottom.Latitude <= data.Position.Latitude &&
                            data.Position.Latitude <= boundingBox.LeftTop.Latitude);

            return CheckLng && CheckLat;
        }

        /// <summary>
        /// 四元樹分裂
        /// </summary>
        /// <param name="node">四元樹節點</param>
        static void Subdivide<T>(QuadTreeNode<T> node)
            where T:IQuadTreeNodeData
        {
            var box = node.BoundingBox;

            //中心點
            double LatMid = (box.LeftTop.Latitude + box.RightBottom.Latitude) / 2.0;
            double LngMid = (box.LeftTop.Longitude + box.RightBottom.Longitude) / 2.0;

            //左上
            var NorthWest = new BoundingBox
            {
                LeftTop = new Coordinate
                {
                    Latitude = box.LeftTop.Latitude,
                    Longitude = box.LeftTop.Longitude
                },
                RightBottom = new Coordinate
                {
                    Latitude = LatMid,
                    Longitude = LngMid
                }
            };
            node.NorthWest = new QuadTreeNode<T>(NorthWest, node.BucketCapacity);

            //右上
            var NorthEast = new BoundingBox
            {
                LeftTop = new Coordinate
                {
                    Latitude = box.LeftTop.Latitude,
                    Longitude = LngMid
                },
                RightBottom = new Coordinate
                {
                    Latitude = LatMid,
                    Longitude = box.RightBottom.Longitude
                }
            };
            node.NorthEast = new QuadTreeNode<T>(NorthEast, node.BucketCapacity);

            //左下
            var SouthWest = new BoundingBox
            {
                LeftTop = new Coordinate
                {
                    Latitude = LatMid,
                    Longitude = box.LeftTop.Longitude
                },
                RightBottom = new Coordinate
                {
                    Latitude = box.RightBottom.Latitude,
                    Longitude = LngMid
                }
            };
            node.SouthWest = new QuadTreeNode<T>(SouthWest, node.BucketCapacity);

            //右下
            var SouthEast = new BoundingBox
            {
                LeftTop = new Coordinate
                {
                    Latitude = LatMid,
                    Longitude = LngMid
                },
                RightBottom = new Coordinate
                {
                    Latitude = box.RightBottom.Latitude,
                    Longitude = box.RightBottom.Longitude
                }
            };
            node.SouthEast = new QuadTreeNode<T>(SouthEast, node.BucketCapacity);

        }
    }

————使用方法—————–
**
**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
void Main()
{
 Stopwatch timer = new Stopwatch();
 timer.Reset();
 timer.Start();
 var YouWantToSearchData = new List<UserQuery.YourCoordinateData>();
 for (int i = 0; i < 5000000; i++)
 {
  YouWantToSearchData.Add(
   new YourCoordinateData
   {
    Position = new Coordinate 
    {
      Latitude = GetRandomNumber(22,26),
      Longitude = GetRandomNumber(120,122)
    } 
   });
 } 
 var QuadTree = QuadTreeService.CreateQuadTree(YouWantToSearchData,GetBoundingBox()); //建立四元樹
 string.Format("建資料花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds).Dump();

 //要搜尋的範圍
 BoundingBox range = new BoundingBox
 {
  LeftTop = new Coordinate { Latitude = 24.997123, Longitude = 121.21940612793 },
  RightBottom = new Coordinate {Latitude =24.958553314209,Longitude = 121.485925}
 };

 //一般搜尋
 timer.Reset();
 timer.Start();
 var Result1 = Search(range,YouWantToSearchData);
 string.Format("搜尋資料花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds).Dump();

 //四元樹搜尋
 timer.Reset();
 timer.Start();
 var Result2 = new List<YourCoordinateData>();
 QuadTreeService.SearchDataInRange(QuadTree,range,ref Result2);
 string.Format("四元樹搜尋資料花了: {0} ticks ({1} msec)", timer.ElapsedTicks, timer.ElapsedMilliseconds).Dump();

 string.Format("一般搜尋資料筆數: {0}",Result1.Count()).Dump();
 string.Format("四元樹搜尋資料筆數: {0}",Result2.Count()).Dump();
}

public List<YourCoordinateData> Search(BoundingBox range,  List<YourCoordinateData> Datas) 
{
 return Datas.Where(x => range.RightBottom.Latitude  <= x.Position.Latitude  && x.Position.Latitude <= range.LeftTop.Latitude &&
                            range.LeftTop.Longitude  <= x.Position.Longitude  && x.Position.Longitude <= range.RightBottom.Longitude).ToList();
}

public class YourCoordinateData : IQuadTreeNodeData 
{
 public Coordinate Position{get;set;}
}

//台灣的範圍
public BoundingBox GetBoundingBox()
{
 return new BoundingBox
 {
  //台灣範圍
  LeftTop = new Coordinate
  {
   Latitude = 26,
   Longitude = 120
  },
  RightBottom = new Coordinate
  {
   Latitude = 22,
   Longitude = 122
  }
 };
}

//隨機取得經緯度亂數
static Random random = new Random();
public static double GetRandomNumber(double minimum, double maximum)
{
 return random.NextDouble() * (maximum - minimum) + minimum;
}

分別實驗了10萬筆與500萬筆的搜尋數據，當然筆數擴張的越大，這個數據差距會越大

[![](https://3.bp.blogspot.com/-ZxXLvUMEaU8/V-jEmww86II/AAAAAAAAH98/12-o58aYKrcsVPIi6iPjGxEbt8ngHFFvwCLcB/s1600/1.png)](https://3.bp.blogspot.com/-ZxXLvUMEaU8/V-jEmww86II/AAAAAAAAH98/12-o58aYKrcsVPIi6iPjGxEbt8ngHFFvwCLcB/s1600/1.png)
10萬筆
[![](https://2.bp.blogspot.com/-Kba3y7eAdFo/V-jFYZ5hXoI/AAAAAAAAH-I/_Mk3UU4NCII26OC6RqXubc5SdEkAMawogCLcB/s1600/2.png)](https://2.bp.blogspot.com/-Kba3y7eAdFo/V-jFYZ5hXoI/AAAAAAAAH-I/_Mk3UU4NCII26OC6RqXubc5SdEkAMawogCLcB/s1600/2.png)
500萬筆