查找列表中最接近的点到一个对象名单

我对INT的坐标列表像查找列表中最接近的点到一个对象名单

list<pair<int,int> > coordinates;

我需要找到的最近点到一个原点，

class Point{ 
public: 
float x; 
float y; 
};

我可以找到与自定义比较对象和排序，但我想知道有更快的方式与min？我试过

class DistanceComparator{ 
public: 
    DistanceComparator(const Point& p){origin=p;} 
    inline bool operator<(std::pair<int,int> & lhs,std::pair<int,int > & rhs) 
    { 
     float deltaX1=lhs.first-origin.x; 
     float deltaY1=lhs.second-origin.y; 
     float deltaX2=rhs.first-origin.x; 
     float deltaY2=rhs.second-origin.y; 
     return (deltaX1*deltaX1+deltaY1*deltaY1)<(deltaX2*deltaX2+deltaY2*deltaY2); 
    } 
private: 
    Pointorigin; 
};

但是<只需要一个参数。这个怎么做？

来源

2012-11-02 Damir

你的解决方案是次优的，因为它需要对整个列表进行排序，这是不需要的。你只需要最小的元素，没有必要对其余的进行排序。我可能会建议你看看std::partial_sort，或者直接转到突击队并重复它（O(n)而不是O(n*log(n))排序）。

来源

2012-11-02 14:24:10

+1“突击队”的方法 – linello

另外的std :: nth_element（。！线性复杂度平均值） – PSIAlt

正如Luchian Grigore所说，你不应该对点列表进行排序。但是，我想在这里解决您的语法问题。

您不能有一个比较运算符作为类成员它比较两个其他对象。你只有两种可能性来定义一个比较操作符：

的成员函数bool T::operator<(const U& rhs) const与this是左侧操作数。（我认为常量引用是可选的，但当然强烈推荐。）请注意，T == U不一定是正确的。
非会员功能bool operator<(const T& lhs, const U& lhs) const再次T == U不一定是真实的。

所以你不能有，你想拥有它可以访问到三个对象的比较操作符：两个操作数和有点像“上下文”，可以参数多态比较。

为了解决我知道下面的两个解决方案的问题（有可能不止于此）：

开始使用比较操作时设置附加参数为全局变量。当然，这是非常肮脏的（全局变量在OOP中总是很脏）并且使排序不可重入。由于它太脏，我永远不会推荐它（但它仍然是可能的解决方案），因此我不会在这里给出一个示例代码。
使用谓词而不是operator <。有多种方式可以做到这一点。这里有两个：

如果你的C++ 0x/C++ 11可供选择：使用lambda函数可以从客户端上下文捕捉附加参数（如果您运行std::sort）：
```
Point origin = ...; 
std::sort(..., [origin](const Point & a, const Point & b){ 
    return distance(a, origin) < distance(b, origin); 
}); 
```
如果您没有C++ 0x/C++ 11可用：您仍然可以定义一个自定义谓词，以不使用lambda函数的自定义方式比较这两个对象。你必须定义一个比较辅助类：
```
// Helper class: 
struct PointDistanceComparator { 
    PointDistanceComparator(Point origin) : origin(origin) {} 
    bool operator() (const Point & a, const Point & b) const { 
     return distance(a, origin) < distance(b, origin); 
    } 
private: 
    Point origin; 
}; 

// Client code: 
Point origin = ...; 
std::sort(..., PointDistanceComparator(origin)); 
```
当然你也可以（像你这样）优化代码，不使用平方根的距离的计算。示例代码应该只给你一个关于如何参数化一般比较的想法。

来源

2012-11-02 15:08:16 leemes

用于lambda解决方案的+1 – NoSenseEtAl

如果您需要查询的坐标列表中很多时候，你可能要考虑使用KD树为最近邻搜索。这将有O（log n）时间复杂度。构建和查询Kd树约15-20行（可读）C++代码。看看Kd-tree wikipedia article 也看看std::nth_element，你可以使用它来有效地建立你的Kd树（选择枢轴点和分区的容器（左和右childeren，请参阅维基百科文章中的Python代码）。

更新：我创建了一个C++ N-dimensional K-d tree implementation与K近邻搜索它包括一些单元测试，告诉你如何使用它

来源

2012-11-03 03:12:06 gvd

用于几何数据结构+1或者[QuadTree]（https：/ /en.wikipedia.org/wiki/Quadtree）。 :) – leemes

查找列表中最接近的点到一个对象名单

回答

相关问题