기하 (Geometry)

Geometry in PS

• 기하문제란 무엇인가?

• 기하문제는 왜 어려운가?

  • 구현이 더럽다.
  • 예외 케이스가 많다.
  • 수학적인 지식을 많이 필요로 하는 경우가 있다.

• 기하문제를 왜 풀어야하는가?

  • 남들이 못푸니까 풀면 확실히 메리트가 있다.
  • 리저널 대회에서 유명한 기하 문제들이 그대로 나오는 경우들도 많다. (예를 들면 치킨집이라거나...)
  • 생각보다 쉬운 기하문제들도 많다.

기하문제 분류

• 순수 기하문제 (수학)

  • delaunay triangulation
  • voronoi diagram
  • boolean operations on polygons

• 복잡한 자료구조를 필요로 하는 기하문제

  • k-d tree

• 해결 과정에서 기하 라이브러리가 필요한 문제

  • 기하 라이브러리가 있어야 그래프를 만들 수 있는 문제

라이브러리에 있으면 좋을 것들?

• 기본적인 구조체

  • Point
  • Line (Segment)
  • Circle
  • Polygon
  • Plane (2-d, 3-d, 구면, cylinder, cone, ...)

• Basic Methods

  • area, ccw
  • intersection (point, line, circle, polygon 사이의..)
  • boolean operations on polygons
  • closest pair of points

• Advanced Methods

  • polygon triangulation
  • delaunay triangulation
  • voronoi diagram
  • shortest path (with obstacles...)

링크

• (자유게시판) 기하문제 팁: 직선-직선 교점 구하기 등