[수학, 알고리즘, 지형, 유역, 수리, 수문][서울대 졸업논문]크루스칼 알고리즘과 불규칙 삼각망을 이용한 능선추출 알고리즘 개발

소개

모든 구조물은 목적에 적합한 설계를 위하여 설계에 영향을 미치는 요소들에
대한 정확한 고려가 필요하다. 특히, 저수지나 댐 등의 수공구조물index{수공구조물}의
경우는 정확한 유량의 산출이 여타 구조물에 비해 큰 영향을
미치게 된다. 유역index{유역}과 하천 특성index{하천특성}은 유역의 강수-유출간의 관계규명과 홍수량index{홍수량}을 추정하는데
필요한 기초 자료이며, 이를 통해 유index{유량}량을 산출할 수 있다. 유량은 대상
유역의 투수 특성, 유로의 특성 등으로 구성되는 유출 특성에 큰 영향을
받기는 하나 근본적으로는 유역의 면적index{유역면적}에 영향을 받는 강수량index{강수량}이 가장
기본적인 요소가 된다. 그러므로 유역을 정확히 결정할 수 있다면 그만큼
정확한 유량을 산출할 수 있게되고, 궁극적으로는 구조물의 정확한 설계에
기여하게 된다.

기존에는 유역을 얻기 위해 등고선index{등고선}을 이용하여 사람이 직접 유역을 가려내는
방법을 사용하였으나 이는 시간이 오래걸리며 부정확하고
인위적이어서 이에 대한 개선의 필요성이 대두 되었고 이를
해결하기 위해 GIS(Geographic Information System)index{GIS}을 이용한
유역의 추출index{유역추출}방법이 개발되었다.

그러나 GIS를 이용한 방법 역시 DEMindex{DEM}자료를 얻기 위하여 등고선 자료를
통해 불규칙 삼각망index{불규칙삼각망(TIN)}(TIN, Triangular Irregular Networks)를 만드는
인위적인 과정이 필요하고, 이 과정을 거치지 않기 위해 기존의 DEM 자료를
직접 이용할 수도 있으나 이를 위해서는 자료의 방대함으로 인하여 고성능의
컴퓨터가 필요하고 연산 수행 시간이 길어지는 등의 단점을 가지고 있다.

따라서, 본 연구에서는 기존의 유역 추출 방법들을 비교 분석하고,
등고선 자료로 부터 직접 불규칙 삼각망을 생성하고 이를 DEM으로 바꾸는
과정 없이, 최소신장트리index{최소신장트리}를 구하기 위해 개발된 크루스칼 알고리즘을
이용하는 방법으로 수행하려 한다.

목차

초록}

목차}

그림 목차}

표 목차}

서론}

연구사}
크루스칼 알고리즘과 불규칙 삼각망}

{3.1}불규칙 삼각망
{3.2}크루스칼 알고리즘}
능선추출알고리즘의 개발}
{4.1}알고리즘의 개요}
{4.2}메이트 탐색}
{4.3}삼각형간 경중률 측정}
{4.4}크루스칼 알고리즘의 구현}

알고리즘의 수행과 기존 방식과의 비교}
{5.1}미원면의 유역 추출 결과}

결론}
참고문헌}
Abstract}
소스코드}
{A.1}PreparationTIN}
{A.2}FractalTerrain}
{A.3}Util}
{A.4}MatingMulti}
{A.5}Weight}
{A.6}KruskalMulti}
{A.7}GetRidge}
{A.8}Database}

본문내용

유역이란 출수점(Outlet Points)에 이르는 유출량에 기여하는 지역을
말한다. 유역을 추출하기 위하여 격자망을 사용하는 GIS를
이용하여 유역을 구하는 방법이 일반적이다. 그러나 본 연구에서는
격자망을 작성하지 않고 원본 등고선 자료로 부터 불규칙 삼각망을
생성하고 이를 크루스칼 알고리즘을 사용하여 재조합하여 유역을
추출하였다. 이 유역 추출 방법은 불규칙 삼각망으로부터 수치고도모형을
만드는 단계를 생략할 수 있고 별도의 연산이 없이 유역의 출구를 알아낼
수 있는 장점이 있다. 개발된 알고리즘을 바탕으로 미원면의 시험 지역에
대해서 알고리즘을 적용하여 본 결과, 유역 추출이 가능함을
확인하였다. 그러나 지형의 기복을 보정할 수 있는 알고리즘이
아직 개발되지 않아 대유역을 추출하는데에는 한계를 보여, 이에 대한
보완이 필요하다.

참고자료

· 서울대학교 지역시스템 공학과