■

#include 

#include 

#include 

#include 

#include 

#include 

#define MIN_INIT (20000)

typedef struct _XY {

  int x;

  int y;

} XY;

XY xy_preblocklast = {4,4}; // 前回x,y

//! @brief xy座標の並び替え

//  @param[inout] xy     xy座標

//  @param[in]    xynum  xy座標の数

//  @param[in]    type   x優先=0, y優先=1

void SortNearPoint(XY* xy, int xynum, int type) {

  std::vector ret_xy; // xy座標:結果

  std::list check_xy; // xy座標:チェック

  for (int i = 0 ; i < xynum; i++) { // for (データ数)

    check_xy.push_back(xy[i]);       //  チェック対象

  }

  int diff_min;                      // x差 + y差 : 最小

  int diff_min_part;                 // x差:最小 | y差:最小

  int xy_part;                       // 比較対象 (x | y)

  XY  xy_abs = {0,0};                // x差, y差

  std::list::iterator xy_target; // xy座標:候補

  XY  xy_pre = xy_preblocklast;      // xy座標:前回

  for (int k = 0; k < xynum; k++) {  // for (xy の数だけ)

    diff_min      = MIN_INIT;           //  初期値:2万

    diff_min_part = MIN_INIT;           //  初期値:2万

    std::list::iterator it = check_xy.begin();   // チェック対象:先頭要素

    while (it != check_xy.end()) {             // for (xy の数だけ 〜 1回ずつ減らす)

      xy_abs.x = abs(it->x - xy_pre.x);        //  前回値との差

      xy_abs.y = abs(it->y - xy_pre.y);        //  前回値との差

      if ((xy_abs.x + xy_abs.y) <= diff_min) { //  if (最も差が小さい)

        if (type == 0) {      // if (x 優先)

          xy_part = xy_abs.x; //     x の差が小さい方

        } else {              // if (y 優先)

          xy_part = xy_abs.y; //     y の差が小さい方

        }

        if (xy_part <= diff_min_part) {          //   if (最もy軸の差が小さい)

          diff_min      = xy_abs.x + xy_abs.y;   //       最も小さいxyの差

          diff_min_part = xy_part;               //       最も小さいxの差 | yの差

          xy_target     = it;                    //       次のxy座標:候補

        }

      }

      ++it; // 次のチェック対象

    }

    xy_pre = *xy_target;           // 前回xy座標

    ret_xy.push_back(*xy_target);  // xy座標:結果

    check_xy.erase(xy_target);     // チェック済み要素を削除

  }

  memmove(xy, &ret_xy[0], sizeof(XY)*xynum); // 結果をコピー

}

int main() {

  XY xy[9] = {

    {1,1}, {2,1}, {3,2},

    {3,3}, {2,2}, {2,3},

    {1,2}, {1,3}, {3,1}

  };

  printf("[before]\n");

  for(int i=0; i<9; i++) {

    printf("[%d] x=%d, y=%d\n", i, xy[i].x, xy[i].y);

  }

  SortNearPoint(xy, 9, 0);

  printf("[after]\n");

  for(int i=0; i<9; i++) {

    printf("[%d] x=%d, y=%d\n", i, xy[i].x, xy[i].y);

  }

  XY xy2[9] = {

    {1,1}, {2,1}, {3,2},

    {3,3}, {2,2}, {2,3},

    {1,2}, {1,3}, {3,1}

  };

  SortNearPoint(xy2, 9, 1);

  printf("[after]\n");

  for(int i=0; i<9; i++) {

    printf("[%d] x=%d, y=%d\n", i, xy2[i].x, xy2[i].y);

  }

}