查找列表中的最近点一所指名单 [英] Find the closest point from list to one referent list

问题描述

我对INT的坐标列表像

I have list of pairs of int coordinates like

list<pair<int,int> > coordinates;

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

I need to find the closest point to one Point origin,

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

我可以用自定义的比较对象和分类找到，但我想知道是否有更快的方式与分？我试过

I can find with custom comparator object and sorting but I am wondering is there quicker way with min ? I tried

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;
};

但＆LT;需要采取只有一个参数。如何做到这一点？

but < needs to take only one argument. How to do this ?

推荐答案

您的解决方案是最佳方案，因为它需要排序的整个列表，这是没有必要的。你只需要最小元素，没有必要的休息排序。我可能会建议你看看的std :: partial_sort 或者只是去突击队，并遍历它（ O（N）作为反对 O（N *的log（n））排序）。

Your solution is sub-optimal because it requires sorting the whole list, which isn't needed. You only need the minimum element, there's no need to sort the rest. Might I suggest you look into std::partial_sort or just go commando and iterate through it (O(n) as opposed to O(n*log(n)) sorting).

这篇关于查找列表中的最近点一所指名单的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！