기하 알고리즘이란

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

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

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

먼저 수학에서 기울기를 구할때 (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];

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

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

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

기하알고리즘이란? https://wondangcom.com/453?category=717978

두선분의 교점 찾기 https://wondangcom.com/466

반직선의 교점찾기1 https://wondangcom.com/903

반직선의 교점찾기2  https://wondangcom.com/930