algorithm - 판정 - 폐곡선 알고리즘




지정된 수의 점으로 볼록 다각형을 포함하는 가장 작은 것을 찾습니다. (2)

볼록 polgyon과 N이라는 숫자가 주어진다면 가장 작은 폴리곤을 어떻게 찾습니까?

  1. 원래 다각형의 모든 점을 포함합니다.
  2. 정확히 N 개의 꼭짓점이 있습니다.

예를 들어, 점들의 집합을 가지고 그들 (녹색)에 대한 convex hull을 계산한다고 가정합니다. 이제 모든 점들을 포함하는 가장 작은 사변형 (빨강)을 찾고 싶습니다.

네 모서리를 가진 다른 다각형이 더 크거나 모든 점을 포함하지 않는 것을 쉽게 볼 수 있습니다. 그러나 일반적인 경우에이 폴리곤을 어떻게 찾을 수 있습니까?

편집하다:

가장 작은 원주가 다른 결과를 줄지는 모르겠지만 가장 작은 폴리곤을 사용하면 가장 작은 영역을 나타내는 것을 의미합니다.

불행히도 대답 중 하나에서 '가장자리 제거'접근 방식으로 작동하지 않는 두 개의 예제 그림을 추가했습니다.

배경 정보 :

목표는 이미지 인식으로 모양을 정확하게 결정하는 것입니다. 예를 들어 직육면체의 사진을 찍습니다. 2D 사진의 상자 안에있는 모든 점은 6 각진 볼록 다각형에 포함됩니다. 그러나 실제 모양에는 완벽한 모서리가없고 카메라가 약간의 흐림을 추가하기 때문에이 다각형의 가장자리가 둥글게됩니다. 볼록한 점에서 모서리 받기 질문에서 첨부 된 이미지를 참조하십시오.


당신은 당신의 질문에서 "가장 작은"개념을 정의 할 필요가 있습니다. 당신의 정의가 무엇이든,이 질문은 전산 기하학 문헌에서 많이 연구되었습니다. 핵심 검색 문구는 k-gon을 둘러싸최소한의 문구입니다.

  • Mictchell et al .: "k-gon을 둘러싸는 최소 경계선"2006 ( CiteSeer 링크 )
  • Aggarwal 외 : "최소 영역 외곽선 다각형"1985 ( CiteSeer 링크 )
  • O'Rourke 등 : "최소 삼각형을 찾기위한 최적의 알고리즘"1986, Algorithmica ( ACM 링크 )

일반 알고리즘은 단순하지 않습니다 (최소 영역 삼각형 또는 사각형 알고리즘은 간단 함에도 불구하고). 목표에 따라 "가장 작은"수학적 개념을 포기하고 경험적 방법으로 향해야합니다.


While number of edges > N do
  remove the shortest edge by replacing its endpoints 
  with the intersection point of the adjacent edges




computational-geometry