CODEWITHSUNDEEP
c++algorithmstl
Damir
Damir

Reputation: 56249

Find the closest point from list to one referent list

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

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

Upvotes: 1

Views: 736

Answers (3)

leemes
leemes

Reputation: 45745

As Luchian Grigore already said, you shouldn't sort the list of points. However, I want to address your syntactical problem here.

You can't have a comparison operator as a class member which compares two other objects. You only have two possibilities to define a comparison operator:

  1. A member function bool T::operator<(const U& rhs) const with this being the left hand side operand. (The const-reference is optional, I think, but highly recommended of course.) Note that T == U doesn't have to be true.

  2. A non-member function bool operator<(const T& lhs, const U& lhs) const again with T == U not necessarily to be true.

So you can't have a comparison operator which has access to three objects as you want to have: the two operands and somewhat like a "context" which can parametrize the comparison.

To solve the problem I know the following two solutions (there might be more than that):

  1. Set the additional parameter as a global variable when starting to use the comparison operator. Of course, this is very dirty (globals are always dirty in OOP) and makes the sorting non-reentrant. Since it is way too dirty I would never recommend it (but it still is a possible solution), thus I won't give an example code here.

  2. Use a predicate instead of an operator <. There are multiple ways to do so. Here are two:

    If you have c++0x / c++11 available: Use a lambda function which can capture the additional parameter from the client context (where you run std::sort):

    Point origin = ...;
std::sort(..., [origin](const Point & a, const Point & b){
    return distance(a, origin) < distance(b, origin);
});

    If you don't have c++0x / c++11 available: You can still define a custom predicate to compare the two objects in a customized way without lambda functions. You have to define a comparator helper class:

    // 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));

    Of course you can (like you did) optimize the code to not use a square root for the calculation of the distance. The example code should only give you an idea on how to parametrize a comparison in general.

Upvotes: 2

gvd
gvd

Reputation: 1831

If you need to query the list of coordinates many times you might want to consider using a Kd-tree for nearest neighbor search. This will have O(log n) time complexity. Building and querying a Kd-tree is about 15-20 lines of (readable) C++ code. Have a look at the Kd-tree wikipedia article Also have a look at std::nth_element , you can use this to efficiently build your Kd-tree (to choose the pivot point and partition the container (left and right childeren, see python code in wikipedia article).

Update: I create a C++ N-dimensional K-d tree implementation with K-nearest neighbor search. It includes some unit tests that show you how to use it.

Upvotes: 1

Luchian Grigore
Luchian Grigore

Reputation: 258698

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).

Upvotes: 5

Related Questions