Gridmap의 특정 NxN 패턴을 확인하는 빠른 방법

Question

해결해야 할 다음과 같은 문제가 있습니다. 간단하지만 큰 그리드 맵 (크기 : mX-times-mY)이 있습니다. 나는 단지 타일이 장애물에 의해 점유되었거나 자유 롭다고 구별합니다.

지금의 내가 크기 n 배-N의 상대적으로 작은 슬라이딩 윈도우를 사용하는 가정 해 봅시다, 그래서 N < < MX, n은 < < 내. 해당 n-times-n 창에서 점유 된 타일과 사용 가능한 타일의 가능한 모든 조합에 대해 식별자를 할당합니다 (숫자 만 말해 보겠습니다). 그런 다음 내 큰지도의 일부분에 대한 "스냅 샷"을 해당 창 크기로 가져옵니다.

내 질문 :지도에서 추출한 현재 패턴의 식별 번호를 확인하는 가장 쉽고/또는 가장 빠른 방법은 무엇입니까?

설명 : 저는 2x2 창 (2x2 행렬)을 가지고 있습니다. 2^(2x2) = 16 개의 가능한 패턴 조합이 있습니다.

Pattern #1 #2 #3 #4 #5 #6 #7 #8 

      00 #0 0# 00 00 ## #0 00 
      00 00 00 #0 0# 00 #0 ## 

Pattern #9 #10 #11 #12 #13 #14 #15 #16 

      0# #0 0# 0# #0 ## ## ## 
      0# 0# #0 ## ## 0# #0 ## 

with # = obscured 
    0 = free 

어떻게 쉽고 빠르게이 aboves 예에서 패턴 번호 (10)임을 식별 할 수있는, 내가 패턴 맵에서

#0 
0# 

를 추출 가정?

내 아이디어 지금까지 :

1 : 모든 패턴을 통한 단순 루핑

루프는 어쩌면 모두 패턴의 차이가 영 행렬 인 경우 확인하여, 올바른 것을 찾을 때까지.

2

: 식별자 로우 합 및 열 합계를 사용하여

I 모든 n 행 및 모든 N 개의 열을 합산하고 다차원 배열 서브 인덱스로서 그 합계를 사용한다. 위 예제의 경우 : sumRow1 = 1 sumRow2 = 1 sumCol1 = 1 sumCol2 = 1 내 패턴이 patternNumbers [1] [1] [1] = 10에 저장됩니다. 또 다른 예는 패턴 16입니다. 패턴 번호에 저장 됨 [2] [2] [2] [2] = 16.

더 큰 창에 유리한 장점 : 2 * n 합계 만 계산하면 바로 그 합계를 사용하여 찾고 있던 패턴을 처리 할 수 ​​있습니다. 에 대한. 크고 큰 단점 : 많은 빈 항목이 남아있는 (2 * n) 차원 배열이 필요합니다. 따라서 상대적으로 큰 오버 헤드입니다.

이전에이 작업을 수행 한 사람이 있습니까? 어떤 아이디어가 이것을 해결하는 방법? 나는 또한 어떠한 종류의 대칭 (회전 또는 선)도 고려하지 않았다.

도움을 주시면 대단히 감사하겠습니다. 나는 나에게 다른 사람에 의해 지적되었다 상대적으로 쉬운 해결책을 찾을처럼

Answer 1

음, 외모 : 특정 순서로 모든 행 또는 모든 열을 (!, 당신의 선택을 중요하지 않습니다) 취함으로써

을 - 모든 패턴에 대해 동일해야하며 하나의 긴 벡터로 정렬하면 일반 이진 표현식을 얻습니다. 이진수를 십진수로 변환하면 "고유 식별자"가 생깁니다.

Example 1: 

00 
#0 

can also be written as 
00 
10 

now reorder the rows to 

0010 = 2 

============================= 

Example 2: 

## 
00 

can also be written as 
11 
00 

now reorder the rows to 

1100 = 12