2 차원 기와 격자 경계 검출

2 차원 기와 격자 경계 검출
1. 칸 당 ENWS 네 개의 인접 칸 만 고려
네 개의 인접 격자 ENSW 번 호 는 0 ~ 3 입 니 다.
2. 현재 방향 D (0 ~ 3): 현재 칸 이 이전 칸 에서 선택 한 ENSW (0 ~ 3) 중 하나 라면 이 선택 은 현재 방향
3. 다음 정책 선택:
다음 우선 순위 로 판단 (D + 3)% 4, (D + 4)% 4, (D + 5)% 4, (D + 6)% 4
(첫 번 째 는 오른손 옆 이 고 마지막 은 원래 의 길 로 돌아 가 는 것 이다)
만약 이 네 가지 점 이 모두 아니라면, 이 점 은 고립 점 이다.
4. 헤드 노드
검 측 된 첫 번 째 경계 점 은 머리 노드 로 하고 머리 노드 와 인접 한 외부 점 (또는 경계) 을 이전 점 으로 간주한다.
W - > E, N - > S 순 으로 측정 하면 머리 노드 의 방향 은 E 입 니 다.
5. 끝
다시 머리 결점 을 만나면 끝난다.
 
 

#include 

enum Dir {
  E = 0,
  N,
  W,
  S,

  DirMax
};

enum { Empty = 0, Full = 1, Flag = 2 };

struct Point {
  int x;
  int y;

  bool operator==(const Point& p) const { return x == p.x && y == p.y; }
  bool operator!=(const Point& p) const { return !(*this == p); }

  //      
  bool CheckPoint(int* map, int w, int h) {
    if (x < 0 || y < 0) return false;
    if (x >= w || y >= h) return false;
    return map[y * w + x] != Empty;
  }

  //    
  void GetNearPoints(Point near[DirMax]) const {
    // E
    near[E].x = x + 1;
    near[E].y = y;

    // N
    near[N].x = x;
    near[N].y = y - 1;

    // W
    near[W].x = x - 1;
    near[W].y = y;

    // S
    near[S].x = x;
    near[S].y = y + 1;
  }

  //     
  Point GetNextPoint(int* map, int w, int h, Point near[DirMax], Dir& d) {
    for (int i = 0; i < DirMax; ++i) {
      Dir next_d = Dir((d + i + (DirMax-1)) % DirMax);
      if (near[next_d].CheckPoint(map, w, h)) {
        d = next_d;
        return near[next_d];
      }
    }

    //   ,     
    return *this;
  }
};

int main() {
  int map[][9] = {
{0, 0, 0, 1, 1, 1, 0, 0, 0},
{0, 0, 1, 1, 1, 1, 1, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 0},
{1, 1, 1, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 0}, 
{0, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 1, 1, 1, 1, 1, 0, 0, 0}, 
{0, 0, 0, 0, 0, 1, 1, 1, 1}};

  int w = 9;
  int h = 12;

  //     
  Point head = {0, 0};
  bool findHead = false;
  for (int i = 0; i < h && !findHead; ++i) {
    for (int j = 0; j < w; ++j) {
      head.x = j;
      head.y = i;
      if (head.CheckPoint(&map[0][0], w, h)) {
        findHead = true;
        break;
      }
    }
  }

  // (             ,          )
  if (!findHead) return 1;
  
  Point cur = head;
  Dir d = E;
  Point near[DirMax];
  do {
    map[cur.y][cur.x] = Flag;

    cur.GetNearPoints(near);
    cur = cur.GetNextPoint(&map[0][0], w, h, near, d);

  } while (cur != head);

  //   
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      std::cout << map[i][j];
    }
    std::cout << std::endl;
  }

  return 0;
}
/*
    :
000222000
002212200
022122220
222220000
000220000
000200000
000200000
022222220
021111120
021112220
022222000
000002222
*/