조합 연산 지오메트리 항목 목록

조합 연산 기하학 항목 목록에는 기하학적 객체의 관점에서 문제를 별개의 실체로 기술하는 연산 기하학 주제를 열거하고 있으며, 따라서 그 해결 방법은 조합 문자의 이론과 알고리즘이 대부분이다.

기하학적 객체를 연속적인 실체로 다루고 자연 특성의 방법과 알고리즘을 수치 분석에 적용하는 계산 기하학의 또 다른 풍미를 보려면 수치 계산 기하학 항목 목록을 참조하십시오.

시공/표현황

• 폴리곤의 부울 연산
• 볼록 선체
• 하이퍼플레인 배열
• 폴리곤 분해
  • 다각형 삼각측량
    • 최소 볼록 분해
    • 최소 볼록 커버 문제(NP-hard)
    • 최소 직사각형 분해
  • 테셀레이션 문제
• 형상해부 문제
• 스트레이트 스켈레톤
• 찌르기 라인 문제
• 삼각측량
  • 델라우나이 삼각측량
  • 점 집합 삼각측량
  • 다각형 삼각측량
• 보로노이 다이어그램

극단적 모양

• 최소 경계 상자(가장 작은 경계 상자, 가장 작은 경계 상자)
  • 2-D 케이스: 가장 작은 경계 사각형(가장 작은 주변 사각형)
  • 이 문제에는 두 가지 일반적인 변형이 있다.
    • 컴퓨터 그래픽의 많은 영역에서 경계 상자(흔히 bbox로 약칭)는 문제가 되는 물체를 둘러싸는 축을 조정하기 위해 평행으로 측면으로 구분된 가장 작은 상자라고 이해된다.
    • 포장과 같은 다른 용도에서는 물체(또는 물체)가 들어갈 수 있는 가장 작은 상자("포장")를 찾는 것이 문제다.여기서 상자는 "포장된" 객체에 대해 임의의 방향을 가정할 수 있다.
• 최소 경계 구(가장 작은 범위 구)
  • 2-D 사례: 최소 경계 원
• 가장 큰 빈 직사각형(최대 빈 직사각형
• 가장 큰 빈 구체
  • 2-D 사례: 최대 빈 원(빈 원 중 가장 큼)

상호 작용/검색

• 충돌 감지
• 선 세그먼트 교차점
• 점 위치
  • 폴리곤의 점
• 다각형 교차로
• 레인지 검색
  • 직교 범위 검색
  • 심플렉스 범위 검색
• 레이 캐스팅(컴퓨터 그래픽의 레이 트레이싱과 혼동하지 않음)

근접성 문제

• 가장 가까운 점 쌍
• 가장 근접한 점 문제
• 점 집합의 지름
• 델라우나이 삼각측량
• 보로노이 다이어그램

가시성

• 가시성(지오메트리)
• 미술관 문제 (박물관 문제)
• 가시성 그래프
• 워치맨 경로 문제
• 컴퓨터 그래픽 응용 프로그램:
  • 숨겨진 표면 결정
  • 은선제거
• 레이 캐스팅(컴퓨터 그래픽의 레이 트레이싱과 혼동하지 않음)

기타

• 해피엔딩 문제
• 햄 샌드위치 문제
• 조립 문제를 만들다.
• 일치하는 문제를 만들다.
• 클리의 측정 문제
• 동위원소 폴리곤과 동위원소 폴리헤드라의 문제점
  • 직교 볼록 선체
• 경로 계획
  • 장애물 사이의 경로
  • 폴리곤의 최단 경로
• 폴리곤 격납
• 강력한 기하학적 계산으로 두 가지 주요 문제 해결: 컴퓨터 실수의 고정밀 표현과 입력 데이터의 가능한 기하학적 퇴보(수학)