-2

I have an array of std::vector<cv::Point> that looks like-

[49, 500]
[49, 129]
[441, 501]
[49, 374]
[440, 374]
[440, 259]
[440, 128]
[49, 260]

Let consider array elements as [x, y]. Now I need to get 4 elements from the array having-

  1. lowest x with highest y
  2. lowest x with lowest y
  3. highest x with lowest y
  4. highest x with highest y

currently, I am using functions to sort based on conditions and then fetch a point.

bool SortForMinXMaxY(const Point & a, const Point &b) 
{
    return (a.x < b.x || a.y > b.y) ;
}

What should be the standard approach with C++ and OpenCV to achieve the goal?

nsssayom
  • 364
  • 1
  • 5
  • 21
  • Did you already have a look [here](http://en.cppreference.com/w/cpp/algorithm)? – user0042 Nov 15 '17 at 18:28
  • `>> lowest x value and highest y value` You seem to want AND but using OR here `return (a.x < b.x || a.y > b.y);` – Killzone Kid Nov 15 '17 at 18:38
  • && won't work here. Please rethink. @ Killzone Kid – nsssayom Nov 15 '17 at 19:00
  • @user0042 : I have looked there. But I have no clue which method should I use. Can you be a little more helpful, please? – nsssayom Nov 15 '17 at 19:02
  • @nsssayom Look at [this](en.cppreference.com/w/cpp/algorithm/lower_bound) or [this](http://en.cppreference.com/w/cpp/algorithm/upper_bound) maybe? – user0042 Nov 15 '17 at 19:04
  • "lowest x value and highest y value" this is obviously not well defined. You'll need some metric or sth. – Micka Nov 15 '17 at 19:08
  • @user0042 I tried stable_sort. Returns the same. And not sure about lower_bound. – nsssayom Nov 15 '17 at 19:11
  • 1
    maybe you could find the point as "the point with lowest distance to the top left corner of the bounding rectangle", but no idea how to use that in a sorting. maybe just sth. like the closer2tlCorner point to the bounding rect of those two points? – Micka Nov 15 '17 at 19:12
  • @Micka Desired output for the failed case is [48, 498] – nsssayom Nov 15 '17 at 19:12
  • 1
    As @Micka says, what does "lowest x and highest y" mean? How does a value with a very low x, but only a middling y compare to a value with a slightly higher x, but a considerably higher y? Do you just want to compare x-y? – Martin Bonner supports Monica Nov 15 '17 at 19:15
  • @MartinBonner I simply want to find out the point with Largest Y value and with Smallest X value. – nsssayom Nov 15 '17 at 19:19
  • 1
    So given the points (0,0) and (1,1) which one do you want? – Martin Bonner supports Monica Nov 15 '17 at 19:26
  • but in your failed sample, the lowest x value is 47, not 48 and the highest y value is 502, not 498. Try return (a.x - a.y < b.x - b.y); However sorting will imho be slower than searching, if you only need a single point and not the complete sorted set of points. – Micka Nov 15 '17 at 19:27
  • @Micka: I am searching for a POINT not the highest and lowest values. I am looking for a point that has lowest X and at the same time highest Y possible. – nsssayom Nov 15 '17 at 19:31
  • So you basically just need the bounding box? What about cv::boundingRect(Points); ? You can then easily retrieve the four rectangle vertices – Miki Nov 15 '17 at 19:34
  • 1
    well, the lowest x is 47 and since there is no other point with 47, this is the winner? You must tell the algorithm your metric on how x and y work together if there is no point with LOWEST x (47 in example) and at the same time HIGHEST y (502 in example) but only points that lie in between. I wanted to show you that your criteria isn't well defined for your problem. Try the a.x-a.y < b.x-b.y thing, maybe that is enough (it will punish the diagonal, though) Imho the right metric would be the L2 distance to top left bounding box coordinate. – Micka Nov 15 '17 at 19:36

3 Answers3

3

The logic used in the compare function is not correct. It does not meet the requirements of strictly weak ordering.

Change it to:

bool SortForMinXMaxY(const Point & a, const Point &b) 
{
   if ( a.x != b.x )
   {
      return (a.x < b.x);
   }
   return (a.y > b.y);
}
R Sahu
  • 204,454
  • 14
  • 159
  • 270
  • No luck. Returns the same output as mine. – nsssayom Nov 15 '17 at 18:59
  • 1
    @nsssayom, I think there is a mismatch between your description of what you want to accomplish and the name of the function. I would change the last line to `return (a.y < b.y);` to match the description. – R Sahu Nov 15 '17 at 19:24
  • There is apparently no mismatch and your last edit returns the same output as my code did. – nsssayom Nov 15 '17 at 19:26
  • @nsssayom, please post a [mcve]. That would be helpful in providing further help. – R Sahu Nov 15 '17 at 19:29
1

Your problem (finding lowest x value and highest y value) is ILL-POSED, since the lowest x value may be another point than the highest y value. You must not ask for both at the same point, but be clearer what you actually want. There are a number of possibilities:

  1. The highest y amongst the points with lowest x

    [](Point const&a, Point const&b)
{ return a.x==b.x? a.y<b.y : a.x>b.x; }

  2. the lowest x amongst the points with highest y

    [](Point const&a, Point const&b)
{ return a.y==b.y? a.x>b.x : a.y<b.y; }

  3. the point with maximum difference y-x

    [](Point const&a, Point const&b)
{ return a.y-a.x < b.y-b.x; }

From your example, I guess it's the last one of these that you actually want, as [48,498] has neither the lowest x nor the highest y, but the largest difference.

Finally, for merely finding the maximum of (some function of) some values, you don't need to sort them, but merely do a single pass:

 auto extremum = std::max_element(Points.begin(), Points.end(),
                                  [](Point const&a, Point const&b)
                                  { return a.y-a.x < b.y-b.x; });
Walter
  • 44,150
  • 20
  • 113
  • 196
0

The C++ sort function your are calling is quicksort, so each elemento will be evaluated multiple times. You need a more strict to make sure each possibility is evaluated by the function.

bool SortForMinXMaxY(const Point & a, const Point &b) 
{
   if ( a.x == b.x )
   {
      return (a.y > b.y);
   }
   if ( a.y == b.y)
   {
      return (a.x < b.x);
   }
   return (a.x < b.x || a.y > b.y);
}
Thadeu Melo
  • 947
  • 14
  • 40