C 도트 행렬에서 최대 다각형을 결정하는 알고리즘

밤새 나를 괴롭히는 질문이 있습니다. 점의 집합을 감안할 때 C 도트 행렬에서 최대 다각형을 결정하는 알고리즘

는 말 :

가장 큰 다각형은 4 × 4의 광장입니다. 이를 위해 :

가장 큰

0 0 1 1 1 
0 1 1 1 1 
1 1 1 1 1

은 ... 사다리꼴이지만, 불규칙한있을 것, 그리고 다른 변화

어떻게 가장 큰 수를 결정하기 위해? (가장 큰 것은 다른 폴리곤으로 묶을 수 없음을 의미합니다.) 어떤 종류의 알고리즘을 사용해야합니까?

또한 그들은 지역, 경계, 볼록 같은 다른 속성을 필요로 (T/F), 그리고 불변 회전 수 ...

이이 명령에 제공하지만 난 정말 이해가 안 돼요 정확히이 약 ...

통화 부호화 및 2 × 50 × 50의 크기 사이 임의의 2 차원 배열 (모두 치수는 상이 할 수있다), 모든 의 요소가 0 또는 1 전화 이웃m 값이 1 인 배열의 최대 8 개 멤버 중 하나를 인코딩하고 두 인덱스가 모두 m의 대응 인덱스와 최대 1만큼 다릅니다. 특정 인코딩을 사용하면 유도는 다음과 같이 모든 자연수 d (이 인코딩) 깊이 d의 다각형의 세트의 결정 :

가 자연수 부여 d하자 및 가정 모두 D ₀ < D의 세트 깊이의 다각형 d 이 결정되었습니다. 그 다각형을 결정하는 모든 1의 인코딩을 0으로 변경합니다. 그런 다음 깊이 d의 다각형 집합을 과 같은 방법으로 1을 이웃과 연결하여 해당 인코딩에서 얻을 수있는 다각형 집합으로 결정합니다 우리는 최대 폴리곤 (즉, 다른 폴리곤에 포함되지 않은 폴리곤 인 은 1을 이웃 객체의 일부와 연결하여 해당 인코딩에서 얻음)을 얻습니다. 끝에

출처

2013-10-05 Liduo

코드를 표시하십시오. – Gangadhar

흥미로운 질문입니다. 대부분의 것을 포함하는 "섬"을 찾으십시오. 재귀 적 검색과 같습니다. –

그들은 항상 채워질 것입니까? "가장 큰", 가장 큰 지역 또는 가장 큰 경계를 의미합니까? 또한이 문제를 직접 해결하려고 시도 했습니까? – Blender

Create some integer B, set it to zero. 

For every point p: 
    If p has not been marked as "been": 
     Mark p as "been" 
     BFS/DFS from p and count the number of adjacent reachable points. Also mark each of these points as "been". 
     If the number of reachable points + 1 is greater than B: 
      B = the number of reachable points + 1

는, B는 (포인트 "커버") 다각형의 최대 크기 =.

출처

2013-10-06 01:48:03 khoek