C语言 在二维矢量数组中找到右上角的元素

Question

我有一个由9个向量组成的3x3点阵数组。现在我想找到最"左上"(标记为O)和最"右上"(标记为D)的元素。整个数组不是矩形的，数组也没有排序。所以它可能看起来像这样:

array[0] x= 771 y=324
array[1] x= 968 y=323
array[2] x= 868 y= 397
array[3] x= 1065 y= 368
array[4] x= 1164 y= 326
array[5] x= 768 y= 470
array[6] x= 966 y= 471
array[7] x= 1000 y= 452
array[8] x= 1165 y= 472
O----x----D
|    |    |
|    |    |
x----x----x
|    |    |
|    |    |
x----x----x

我真的不知道从哪里开始。我要同时比较x和y吗?

   FindD(int& x, int& y)
    {
      for (int i = 0; i < array.size(); i++)
      {
        for (int j = 0; j < array.size(); j++)
        {
          if(i != j)
          {
            //compare the array elements
          }
        }
      }
    }
FindO(int& x, int& y)

编辑:我应该指出点不是任意放置在平面上的。它们总是以3x3的模式出现，但点之间的距离相差一些像素。此外，整个模式可能会被放置一点旋转。这就是为什么我要找到最左上和右上的元素。获取旋转角度

Answer 1

O----x----D
|    |    |
|    |    |
T----x----T
|    |    |
|    |    |
x----x----x

假设"稍微旋转"意味着上面标记为T的点不能有比你正在寻找的点更高的y值，假设你的坐标从左下角开始，向上的y值增加，向右的x值增加:

找出三个y值最高的点，其中x值最低的点为左点

Answer 2

创建一个计算数组最小值和最大值的函数。传递所有x点数组和y点数组，找到最小x，最大y和最大x。答案将是(min x,max y)和(max x, max y).

Answer 3

我将使用简单的坐标操作来定义左上角和右上方点。根据您的编辑和评论，我将定义:

• 左上角有x+y的最小值
• 右上方点x-y值最小

问题就变成了数组中最小/最大值的简单选择。

Answer 4

给你。您可以使用自己的谓词来查找任何点。

#include <stdio.h>
struct Point
{ 
    int x;
    int y;
};

int upper_right(  struct Point a, struct Point b )
{
    return ( b.x < a.x ) || ( !( a.x < b.x ) && ( b.y < a.y ) );
}
int upper_left(  struct Point a, struct Point b )
{
    return ( a.x < b.x ) || ( !( b.x < a.x ) && ( b.y < a.y ) );
}
struct Point * max_element( const struct Point *a, 
                            size_t n, 
                            int predicate( struct Point, struct Point ) )
{
    const struct Point *max = a;
    if ( n )
    {
        for ( size_t i = 1; i < n; i++ )
        {
            if ( predicate( a[i], *max ) ) max = a + i;
        }
    }
    return ( struct Point * )max;
}
int main(void) 
{
    struct Point a[] =
    {
        {  771, 324 },
        {  968, 323 },
        {  868, 397 },
        { 1065, 368 },
        { 1164, 326 },
        {  768, 470 },
        {  966, 471 },
        { 1000, 452 },
        { 1165, 472 }
    };
    const size_t N = sizeof( a ) / sizeof( * a );
    struct Point *max = max_element( a, N, upper_left );
    printf( "The upper left point is { %d, %d }n", max->x, max->y );
    max = max_element( a, N, upper_right );
    printf( "The upper right point is { %d, %d }n", max->x, max->y );
    return 0;
}

程序输出为

The upper left point is { 768, 470 }
The upper right point is { 1165, 472 }