강의실/정보영재

오늘은 기하알고리즘이 무엇인지 정리를 해 보았습니다.

알고리즘에서 사용하는 기하학은

수학에서 사용하는 기하학과는 약간 다르게 접근해야 하는 부분도 있습니다.


먼저 수학에서 기울기를 구할때 (y2-y1) / (x2-x1) 과 같이 구하는 경우

알고리즘에 이러한 공식으로 대입할때에는 (x2-x1) 이 0 이 되는지 등을 판별하고 이때에 다른 처리를 해 주어야 하는등...

알고리즘 자체가 많이 복잡해 집니다.

또한 0.3 과 같은 경우 수식으로 표현이 간단하지만...

프로그램으로 처리 할때에는 이진법 사용으로 0.29999999.... 와 같은 값으로 밖에는 표현을 하지 못합니다.


이러한 처리 방법에 대한 다른 부분에 의해서 기하 알고리즘이 수학적인 기하와는 약간은 다른 방향에서 바라보는 것이 기하알고리즘의 원리입니다.


이러한 기하 알고리즘은 4차산업혁명 시대에 인공지능이나 그래픽 처리등 많은 분야에서 중요한 학문으로 다루어 지고 있습니다.


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


기하 알고리즘이란?

- 기하 문제를 푸는 알고리즘


기하 알고리즘 문제에는 다음과 같은 경우가 있다.

- 두 선분이 교차하는지 확인 하는 방법

- 여러 개의 점들을 꼭지점으로 하는 단순 폐쇄 다각형 만들기

- 주어진 점이 다각형 내부에 존재하는지 확인하는 방법

- 주어진 점들을 둘러싸는 가장 작은 볼록 다각형 찾기

- 주어진 점들 중에서 최단 경로 찾기


기하 요소의 표현 방법으로는 다음과 같다.


struct point{

   int x

   int y

}

선분 : 두 점을 직선으로 연결

struct line{

  struct point p1;

  struct point p2;

}

다각형 : 점의 집합으로 표현

struct point Pgon[n];


기본 용어를 살펴 보면 다음과 같다.

선분용어


다음에는 두 선분의 교차 검사를 하는 방법에 대해 살펴 보겠습니다.


인천 서구 정보올림피아드 대비반 운영 - 원당컴퓨터 학원




이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
6 0
  • Deborah 2018.07.18 09:46 신고    

    오.. 오늘도 강의 노트를 공개 하시는 건가요? 중요한 자료가 되는 내용을 잘 보고 가요.

  • 휴식같은 친구 2018.07.18 11:51 신고    

    기하라는 말만 들어도 멀미가 날것 같은데요.ㅎ
    이걸 알고리듬으로 구현하는거군요.
    잘 보고 갑니다.

  • *저녁노을* 2018.07.19 04:32 신고    

    ㅎㅎ잘 보고 갑니다.
    즐거운 하루 되세요

  • 몰드원 2018.07.19 06:18 신고    

    포스팅 잘 보고 갑니다
    날씨가 무척이나 덥고 하네요
    건강유의 하시고 좋은 하루 보내세요~

  • 핑구야 날자 2018.07.19 06:42 신고    

    기하 알고리즘에 대해서 잘 알고 갑니다 즐거운 하루 보내세요

  • 공수래공수거 2018.07.19 07:18 신고    

    좀 어려운 내용이네요 ㅎ
    시원한 하루 되세요^^