볼록한 선 - 단조 체인 알고리즘 오류

Question

Monotone chain algorithm을 사용하여 다각형 주위에 볼록 선체를 만듭니다. 때로는 잘 작동하지만 일부 모양에서는 실패합니다. 이 예에서 살펴 보자 : 왼쪽으로 http://i.imgur.com/KN40LgV.png

는 알고리즘을 적용 전에 모양 이며, 오른쪽으로 후 입니다. 어딘가에 약간의 계산 오류가있는 것 같습니다. 알아낼 수 없습니다. 여기

내 소스 코드 (자바 스크립트)에 대한 링크입니다 : http://pastebin.com/GPVm9dQp

을 그리고 여기가 기준으로 사용하는 것이 파이썬에서 구현 한 것입니다 : 그것으로 너무 깊이 파고없이 http://pastebin.com/RgMKH3XN

Answer 1

,하지 어떤 점에서 x- 위치로 점 목록을 정렬 했습니까?