rotating_calipers

회전 캘리퍼 모듈

회전 캘리퍼는 파이썬 모듈이 동일한 이름의 알고리즘을 구현하는 파이썬 모듈입니다.

회전 캘리퍼 알고리즘

알고리즘은 1978 년 Michalel Shamos에 의해 처음 발명되었으며 1983 년 그의 논문에 그것을 소개 한 Godfried Toussant 덕분에 "Rotating Calipers"라는 이름을 얻었습니다.

이 방법은 아이디어가 볼록한 다각형 외부 주변의 스프링로드 버니어 캘리퍼를 회전하는 것과 유사하기 때문에 그 이름을 따서 명명되었습니다. 캘리퍼의 하나의 블레이드가 다각형의 가장자리에 평평해질 때마다, 그것은 반대쪽 날에 닿는 점 또는 가장자리와 함께 대형 쌍을 형성합니다. 다각형 주변의 캘리퍼의 완전한 "회전"은 모든 항체 쌍을 감지합니다. 그래프로 간주되는 모든 쌍의 세트는 스라클을 형성합니다. 캘리퍼 회전 방법은 스위프가 X- 또는 y 좌표가 아닌 선의 경사를 가로 질러 스위프 라인 알고리즘의 투영 듀얼로 해석 될 수 있습니다.

위의 설명은 wikipedia 페이지에서 https://en.wikipedia.org/wiki/rotating_calipers에서 조정되었습니다

동기 부여

"회전 캘리퍼스"알고리즘은 대학 프로젝트를 위해 구현되었습니다. 놀랍게도 나는 파이썬에서 효율적인 솔루션을 찾는 데 많은 어려움을 겪었습니다. 그렇기 때문에 파이썬에서 빠른 "회전 캘리퍼"구현이 필요한 모든 사람과 공유하고 싶었습니다.

복잡성

회전 캘리퍼는 선형 시간에 실행되면 입력에 볼록한 선체가 필요합니다. wihch는 O (nlogn)에서 실행되는 Graham의 알고리즘을 사용하여 계산됩니다. 모든 Algorihm (Graham의 알고리즘 + 회전 캘리퍼) 시간 복잡성은 O (nlogn) + o (n) = O (nlogn)입니다.

설치 방법

Linux :

1. 터미널 열기
2. 실행 : PIP는 회전 캘리퍼를 설치합니다

사용 방법

사용의 예는 여기에서 찾을 수 있습니다