怎的找到矢量数组里特定的几个值
怎样找到矢量数组里特定的几个值
我有一个矢量数组D3DXVECTOR3 Pos[50],它表示空间的50个点；
另有一个固定点P，我想找到点P距离Pos数组中的点最近的五个点。
该怎样实现？请过路大侠指点一下。谢谢！
------解决方案--------------------
你如果就干这一票，傻算就行了。否则建立 kdtree，然后找 k=5 个最近邻。
------解决方案--------------------
云风的那本《编程感悟》有个利用C++模板展开冒泡的示例。任何一本算法书都有堆算法。
D3DXVECTOR3 min[5];
实现 ShiftAndPush 顾名思义。
以上是针对常数5的手工展开。如果5不是常数，可把每次的Distance放入std::priority_queue（堆）中，最后取前5个元素即可。（注意设置谓词，priority_queue是大根堆）
我有一个矢量数组D3DXVECTOR3 Pos[50],它表示空间的50个点；
另有一个固定点P，我想找到点P距离Pos数组中的点最近的五个点。
该怎样实现？请过路大侠指点一下。谢谢！
------解决方案--------------------
你如果就干这一票，傻算就行了。否则建立 kdtree，然后找 k=5 个最近邻。
------解决方案--------------------
云风的那本《编程感悟》有个利用C++模板展开冒泡的示例。任何一本算法书都有堆算法。
D3DXVECTOR3 min[5];
// 设 min[0] 最近、min[1] 次近等等
// 初始化 min[] 放一些距离很大的值
for (i = 0; i < 50; ++i) {
if (Distance(Pos[i], P) < min[0])
ShiftAndPush(Pos[i], min, 0);
else if (Distance(Pos[i], P) < min[1])
ShiftAndPush(Pos[i], min, 1);
else if (Distance(Pos[i], P) < min[2])
ShiftAndPush(Pos[i], min, 2);
else if (Distance(Pos[i], P) < min[3])
ShiftAndPush(Pos[i], min, 3);
else if (Distance(Pos[i], P) < min[4])
ShiftAndPush(Pos[i], min, 4);
}
实现 ShiftAndPush 顾名思义。
以上是针对常数5的手工展开。如果5不是常数，可把每次的Distance放入std::priority_queue（堆）中，最后取前5个元素即可。（注意设置谓词，priority_queue是大根堆）