220 ? ? }
221 ? ? currentNearest = currentTree->root;
222?
223 ? ? /*第二步：递归地向上回退， 在每个结点进行如下操作：
224 ? ? (a)如果该结点保存的实例比当前最近点距离目标点更近，则以该例点为“当前最近点”
225 ? ? (b)当前最近点一定存在于某结点一个子结点对应的区域，检查该子结点的父结点的另
226 ? ? 一子结点对应区域是否有更近的点（即检查另一子结点对应的区域是否与以目标点为球
227 ? ? 心、以目标点与“当前最近点”间的距离为半径的球体相交）；如果相交，可能在另一
228 ? ? 个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点，接着递归进行最
229 ? ? 近邻搜索；如果不相交，向上回退*/
230?
231 ? ? //当前最近邻与目标点的距离
232 ? ? double currentDistance = measureDistance(goal, currentNearest, 0);
233?
234 ? ? //如果当前子kd树的根结点是其父结点的左孩子，则搜索其父结点的右孩子结点所代表
235 ? ? //的区域，反之亦反
236 ? ? KdTree* searchDistrict;
237 ? ? if (currentTree->isLeft())
238 ? ? {
239 ? ? ? ? if (currentTree->parent->rightChild == NULL)
240 ? ? ? ? ? ? searchDistrict = currentTree;
241 ? ? ? ? else
242 ? ? ? ? ? ? searchDistrict = currentTree->parent->rightChild;
243 ? ? }
244 ? ? else
245 ? ? {
246 ? ? ? ? searchDistrict = currentTree->parent->leftChild;
247 ? ? }
248?
249 ? ? //如果搜索区域对应的子kd树的根结点不是整个kd树的根结点，继续回退搜索
250 ? ? while (searchDistrict->parent != NULL)
251 ? ? {
252 ? ? ? ? //搜索区域与目标点的最近距离
253 ? ? ? ? double districtDistance = abs(goal[(d+1)%k] - searchDistrict->parent->root[(d+1)%k]);
254?
255 ? ? ? ? //如果“搜索区域与目标点的最近距离”比“当前最近邻与目标点的距离”短，表明搜索
256 ? ? ? ? //区域内可能存在距离目标点更近的点
257 ? ? ? ? if (districtDistance < currentDistance )//&& !searchDistrict->isEmpty()
258 ? ? ? ? {
259?
260 ? ? ? ? ? ? double parentDistance = measureDistance(goal, searchDistrict->parent->root, 0);
261?
262 ? ? ? ? ? ? if (parentDistance < currentDistance)
263 ? ? ? ? ? ? {
264 ? ? ? ? ? ? ? ? currentDistance = parentDistance;
265 ? ? ? ? ? ? ? ? currentTree = searchDistrict->parent;
267 ? ? ? ? ? ? }
268 ? ? ? ? ? ? if (!searchDistrict->isEmpty())
269 ? ? ? ? ? ? {
270 ? ? ? ? ? ? ? ? double rootDistance = measureDistance(goal, searchDistrict->root, 0);
271 ? ? ? ? ? ? ? ? if (rootDistance < currentDistance)
272 ? ? ? ? ? ? ? ? {
273 ? ? ? ? ? ? ? ? ? ? currentDistance = rootDistance;
274 ? ? ? ? ? ? ? ? ? ? currentTree = searchDistrict;
275 ? ? ? ? ? ? ? ? ? ? currentNearest = currentTree->root;
276 ? ? ? ? ? ? ? ? }
277 ? ? ? ? ? ? }
278 ? ? ? ? ? ? if (searchDistrict->leftChild != NULL)
279 ? ? ? ? ? ? {
280 ? ? ? ? ? ? ? ? double leftDistance = measureDistance(goal, searchDistrict->leftChild->root, 0);
281 ? ? ? ? ? ? ? ? if (leftDistance < currentDistance)
282 ? ? ? ? ? ? ? ? {
283 ? ? ? ? ? ? ? ? ? ? currentDistance = leftDistance;
284 ? ? ? ? ? ? ? ? ? ? currentTree = searchDistrict;
285 ? ? ? ? ? ? ? ? ? ? currentNearest = currentTree->root;
286 ? ? ? ? ? ? ? ? }
287 ? ? ? ? ? ? }
288 ? ? ? ? ? ? if (searchDistrict->rightChild != NULL)
289 ? ? ? ? ? ? {
290 ? ? ? ? ? ? ? ? double rightDistance = measureDistance(goal, searchDistrict->rightChild->root, 0);
291 ? ? ? ? ? ? ? ? if (rightDistance < currentDistance)
292 ? ? ? ? ? ? ? ? {
293 ? ? ? ? ? ? ? ? ? ? currentDistance = rightDistance;
294 ? ? ? ? ? ? ? ? ? ? currentTree = searchDistrict;
295 ? ? ? ? ? ? ? ? ? ? currentNearest = currentTree->root;
296 ? ? ? ? ? ? ? ? }
297 ? ? ? ? ? ? }
298 ? ? ? ? }//end if
299?
300 ? ? ? ? if (searchDistrict->parent->parent != NULL)
301 ? ? ? ? {
302 ? ? ? ? ? ? searchDistrict = searchDistrict->parent->isLeft()??
303 ? ? ? ? ? ? ? ? ? ? ? ? ? ? searchDistrict->parent->parent->rightChild:
304 ? ? ? ? ? ? ? ? ? ? ? ? ? ? searchDistrict->parent->parent->leftChild;
305 ? ? ? ? }
306 ? ? ? ? else
307 ? ? ? ? {
308 ? ? ? ? ? ? searchDistrict = searchDistrict->parent;
309 ? ? ? ? }
310 ? ? ? ? ++d;
311 ? ? }//end while
312 ? ? return currentNearest;
313 }
314