Reputation: 56249
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
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:
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.
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):
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.
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
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
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