전 세계지도의 흑백 사진이 있습니다.도시가 연결된 최대 토지 질량을 찾는 알고리즘?
좌표 (i, j)로 인덱싱 된 이진 값 (물에 대해서는 0, 랜드에 대해서는 1)의 그리드로 픽셀을 변환합니다. 지금, 나는 무작위로 땅에 점을 찍고 이번에는 미국 텍사스 어딘가에 있다고 말한다. 나는 물을 교차하지 않고 에 여행 할 수있는 모든 포인트의 (i, j) 좌표를 알고 싶다. 이 경우 북미와 남미의 모든 지역 (모든 주변 섬 제외)의 모든 (i, j)가됩니다.
당신의 도움에 대한
많은 감사 (이 뒤에 동기는 내가 병렬 C의 SIR 감염 모델을 구현하기 위해 노력하고 있음.)입니다.
편집 : 어떤 대략적인 방법 (. 일부 작은 근해 섬 실수로 포함 된 경우 나 지나치게 법석을 떨게 아니에요) 쿼드 트리와 같은 메쉬 방법으로 아마도이있는 경우가 나는 또한 흥미가 있지 않을까? 다시 한번 감사드립니다.
당신은 flood fill algorithm을 찾고 있습니다. 재귀 적으로 또는 스택을 수동으로 유지 관리하거나 큐를 사용하여 수행 할 수 있습니다.
고마워요 @ 토마스, 알고리즘을 살펴 봤지만 근본적으로 픽셀 별 검사를하고 있습니다. 느린 것 같습니다. 일부 오차 범위를 허용 할 수있는 경우 (예 : 작은 섬이 포함되어있는 경우 너무 소란스럽지 않음), 쿼트 트리를 통한 메쉬 접근법을 기반으로 한 알고리즘이 없습니까? – mchen
실제로 충분히 빠르지 않으셨습니까? 이것은 각 픽셀을 최대 한 번만 검사하므로 픽셀 수는 선형입니다. 여행 할 수있는 포인트를 _all_ 좌표로 지정하도록 요청 했으므로 더 효율적으로 수행 할 수 없으며, 일반적으로 픽셀 수는 선형입니다. 이러한 조회를 많이해야하는 경우지도를 연결된 구성 요소로 사전 처리하여 일정 시간 내에 조회에 응답 할 수 있습니다. – Thomas
다시 한번 감사드립니다. 알고있는 병렬 구현이 있습니까? MPI 또는 OpenMP (또는 둘 다)를 통해 문제가되지 않습니다. 감사합니다. – mchen
[flood fill] (http://en.wikipedia.org/wiki/Flood_fill)을 사용해보십시오. – irrelephant
간단한 홍수 채우기 알고리즘이이 트릭을 수행하는 것처럼 보입니다. 선택할 수있는 수십 가지 구현이 있습니다. –