회전 캘리퍼스

Rotating calipers
회전 캘리퍼(Rotating Caliper) 방법을 사용하여 폴리곤의 볼록한 선체 주위의 프로브 시퀀스.

계산 기하학에서 캘리퍼스의 회전 방법은 알고리즘 설계 기법으로, 점 집합의 폭이나 직경을 찾는 등 최적화 문제를 해결할 수 있다.

이 방법은 스프링이 달린 버니어 캘리퍼를 볼록한 다각형의 바깥쪽으로 회전시키는 것과 유사하기 때문에 그렇게 이름이 붙여졌다.[1] 캘리퍼의 한쪽 칼날이 폴리곤의 가장자리에 평평하게 놓여 있을 때마다, 그것은 반대쪽 칼날에 닿는 지점이나 가장자리가 있는 반향성 쌍을 형성한다. 폴리곤 주위의 캘리퍼의 완전한 "회전"은 모든 항정신병 쌍을 감지한다. 모든 쌍의 집합은 그래프로 보여지며, 스래클을 형성한다. 회전 캘리퍼스의 방법은 스위프가 점의 x 좌표나 y 좌표를 가로지르는 것이 아니라 선의 경사를 가로지르는 스위프 라인 알고리즘의 투영적 이중으로 해석할 수 있다.

역사

반정점 쌍과 그 지지 평행선.

회전 캘리퍼스 방식은 1978년 마이클 샤모스의 논문에서 처음 사용되었다.[2] 샤모스는 이 방법을 사용하여 볼록 폴리곤에 있는 모든 반향성 폴리곤 쌍을 생성하고 볼록 폴리곤의 직경을 ( ) 시간으로 계산한다. 고드프리드 뚜생트는 "회전 캘리퍼스"라는 문구를 만들었고, 이 방법이 다른 많은 계산 기하학 문제를 해결하는 데 적용 가능하다는 것을 보여주었다.[3]

회전 캘리퍼스, 두 볼록 폴리곤 사이의 다리 찾기

샤모스의 알고리즘

샤모스는 자신의 논문(pp 77–82)에서 볼록 폴리곤에 모든 항정신병 쌍의 정점을 생성하는 회전 캘리퍼스 방법에 대해 다음과 같은 알고리즘을 제시했다.[2] 

/* p[]는 표준 형태, 즉 시계 반대 순서로 되어 있다.       뚜렷한 정점, 일직선 정점 없음.    ANGLE(m, n)은 시계방향 각도를 반환하는 절차다.       평행한 위치에서 회전할 때 광선에 휩쓸려 나간다.       Pm,Pm+1을 Pn,Pn+1에 평행한 위치로 이동    우리는 모든 지수가 모드 N으로 감소한다고 가정한다(N+1 = 1). */ GetAll AntiPodalPairs(p[1..n])     // P1 반대쪽 정점을 찾아 첫 번째 반포장 쌍 찾기     i = 1     j = 2     하는 동안에 각(i, j) < 파이         j++     양보하다 i, j      /* 이제 다각형을 중심으로 진행하십시오.          평행한 가장자리. L선이 통과함          Pi, Pi+1 및 M은 Pj, Pj+1을 통과한다.     */      // 모든 P가 스캔될 때까지 j에 반복     현재의 = i         하는 동안에 j != n         만일 각(현재의, i + 1) <= 각(현재의, j + 1)             j++             현재의 = j         다른             i++             현재의 = i         양보하다 i, j          // 이제 평행한 가장자리 관리         만일 각(현재의, i + 1) = 각(현재의, j + 1)             양보하다 i + 1, j             양보하다 i, j + 1             양보하다 i + 1, j + 1             만일 현재의 = i                 j++             다른                 i++

이 알고리즘의 또 다른 버전은 1985년 프리파타와 샤모스에 의해 텍스트에 나타나 각도의 계산을 피했다.[4] 

GetAll AntiPodalPairs(p[1..n])     i0 = n     i = 1     j = i + 1     하는 동안에 (면적(i, i + 1, j + 1) > 면적(i, i + 1, j))         j = j + 1         j0 = j     하는 동안에 (j != i0)         i = i + 1         양보하다 i, j         하는 동안에 (면적(i, i + 1, j + 1) > 면적(i, i + 1, j)             j = j + 1             만일 ((i, j) != (j0, i0))                 양보하다 i, j             다른                  돌아오다         만일 (면적(j, i + 1, j + 1) = 면적(i, i + 1, j))             만일 ((i, j) != (j0, i0))                 양보하다 i, j + 1             다른                  양보하다 i + 1, j

적용들

Pirzadeh는[5] 회전 캘리퍼스 방법의 다양한 적용을 설명한다.

거리

  • 볼록 폴리곤의[6][7] 지름(최대 폭)
  • 볼록 폴리곤의[8] 폭(최소 폭)
  • 두 볼록 폴리곤[9][10] 사이의 최대 거리
  • 두 볼록 폴리곤[11][12] 사이의 최소 거리
  • 두 볼록 폴리곤 사이의 가장 넓은 빈(또는 분리) 스트립(지원 벡터 머신 기반 기계 학습에서 발생하는 문제의 단순화된 저차원 변형)
  • 두 볼록 폴리곤[13] 사이의 그레넌더 거리
  • 최적의 스트립 분리(의료 영상화 및 솔리드 모델링에 사용)[14]

경계 상자

삼각측량

다중 폴리곤 연산

  • 두 볼록 폴리곤의 결합
  • 두 볼록 폴리곤에 대한 공통 접선
  • 두 볼록 폴리곤의[16] 교차점
  • 두 볼록 폴리곤의 임계 지지선
  • 두 볼록 폴리곤의[17] 벡터 합(또는 밍코우스키 합)
  • 볼록형 다각형 2개의 볼록형 선체

트래버설스

다른이들

  • 기계 학습 분류에[21] 대한 비모수 결정 규칙
  • 컴퓨터 시야의[22] 가시성 문제를 위한 개구부 각도 최적화
  • 수백만 개의 생물학적[23] 세포에서 가장 긴 세포 찾기
  • 사격장 2인 정밀도 비교
  • 스캔 이미지에서 뇌의 부분 분류

참고 항목

참조

  1. ^ 뚜생 홈페이지의 "회전 캘리퍼스"
  2. ^ a b Shamos, Michael (1978). "Computational Geometry" (PDF). Yale University. pp. 76–81.
  3. ^ Toussaint, Godfried T. (1983). "Solving geometric problems with the rotating calipers". Proc. MELECON '83, Athens. CiteSeerX 10.1.1.155.5671. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  4. ^ Shamos, Franco P. Preparata, Michael Ian (1985). Computational Geometry An Introduction. New York, NY: Springer New York. ISBN 978-1-4612-7010-2.
  5. ^ Pirzadeh, Hormoz (1999). "Computational geometry with the rotating calipers". McGill Library.
  6. ^ 비나이 K. Bhattacharya와 Godfried T. Toussaint, "유한 평면 세트의 직경을 계산하기 위한 빠른 알고리즘" Visual Computer, Vol. 3, No. 6, 1988년 5월 페이지 379–388.
  7. ^ 비나이 K. Bhattacharya와 Godfried T. 뚜생 "볼록 폴리곤 직경 알고리즘의 카운터 예", IEEE 패턴 분석 및 기계 인텔리전스에 관한 IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-4, No. 3, 1982년 5월, 페이지 306–309.
  8. ^ 마이클 E. 훌레와 갓프리드 T. Toussaint, "세트 폭 계산", IEEE Transactions on Pattern Analysis & Machine Intelligence, Vol. 10, No. 5, 1988년 9월 페이지 761–765.
  9. ^ Godfried T. 뚜생과 짐 A. McAlear, "두 개의 유한 평면 세트 사이의 최대 거리를 찾기 위한 단순한 O(n log n) 알고리즘," 패턴 인식 통지서, Vol. 1, 1982, 페이지 21–24.
  10. ^ 비나이 K. Bhattacharya와 Godfried T. Toussaint, "두 개의 유한 평면 세트 사이의 최대 거리 계산을 위한 효율적인 알고리즘," Journal of Algorithm, vol. 14, 1983, 페이지 121–136.
  11. ^ Godfried T. 뚜생과 비나이 K. Bhattacharya, "두 개의 유한 평면 세트 사이의 최소 거리 계산을 위한 최적의 알고리즘," 패턴 인식 서신, 제 2, 1983년 12월, 페이지 79–82.
  12. ^ "Rotating Calipers". 2015-03-30. Archived from the original on 2015-03-30. Retrieved 2017-03-22.{{cite web}}: CS1 maint : bot : 원본 URL 상태 미상(링크)
  13. ^ MARTINEZ, HUGO M. (January 1, 1978). "Review of: "PATTERN SYNTHESIS", by U. Grenander, Springer-Verlag, New York, 1976. 509 pp". International Journal of General Systems. 4 (2): 126–127. doi:10.1080/03081077808960672. ISSN 0308-1079.
  14. ^ Barequet and Wolfers (1998). "Optimizing a Strip Separating Two Polygons". Graphical Models and Image Processing. 60 (3): 214–221. doi:10.1006/gmip.1998.0470.
  15. ^ Teichmann, Marek (1989). "Wedge placement optimization problems". {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  16. ^ Godfried T. 뚜생 "볼록 폴리곤 교차용 단순 선형 알고리즘, 비주얼 컴퓨터, 1985년 1권 118–123.
  17. ^ 토마스 로자노 페레스 "우주계획: 구성 공간 접근방식," IEEE 컴퓨터상의 거래, Vol. 32, No. 2, 1983, 페이지 108–120.
  18. ^ 비나이 K. Bhattacharya와 Godfried T. Toussaint, "최단 트랜스포탈 계산", Computing, vol. 46, 1991, 페이지 93–119.
  19. ^ 비나이 K. 바타차랴, 주렉 치조비치, 피터 에기드, 이반 스토즈메노비치, 고드프리드 T. Toussaint, 그리고 Jorje Urrutia, "세트의 최단 횡단 컴퓨터", 국제 컴퓨터 기하학 및 응용 저널, 제2권, 제4권, 1992년 12월, 페이지 417–436.
  20. ^ 장마르크 로버트와 고드프리드 T. Toussaint, "단순 객체의 선형 근사", 계산 기하학: 이론과 적용, 1994, 페이지 27-52.
  21. ^ Rasson and Granville (1996). "Geometrical tools in classification". Computational Statistics & Data Analysis. 23 (1): 105–123. doi:10.1016/S0167-9473(96)00024-2.
  22. ^ Bose, P.; Hurtado-Diaz, F.; Omaña-Pulido, E.; Snoeyink, J.; Toussaint, G. T. (2002-08-01). "Some Aperture-Angle Optimization Problems". Algorithmica. 33 (4): 411–435. CiteSeerX 10.1.1.16.7118. doi:10.1007/s00453-001-0112-9. ISSN 0178-4617.
  23. ^ "Incorrect Diameter Algorithms for Convex Polygons".