convex hull을위한 Jarvis의 March (gift-wrapping) 시작

Question

나는 convexwull을 찾기 위해 점 집합에 giftwrapping 알고리즘을 구현하려고합니다.

볼록 선체의 다음 점은 발견 된 마지막 점의 관점에서 가장 왼쪽 점 (위키 피 디아 출신)입니다. 그러나, 나는 지금까지 한 점만 가지고 있기 때문에 어떻게 두 번째 점을 찾아야하는지 잘 모르겠습니다.

발견 된 마지막 점이 p '이고 p'이전의 점이 p ''인 경우, 가장 새로운 점이 벡터 (p ", p ')와 가장 큰 각도를 형성하는 점 p라고 생각했습니다. 그러나 두 번째 점을 찾을 때 p ''가 없습니다.

Answer 1

seanmcl이 말했듯이 이것은 OCaml 질문이 아닙니다. Wikipedia를 읽으면, 가장 최근의 점 pi를 중심으로 가장 큰 각도를 찾고, 선의 모든 점들이 선의 한쪽 (또는 선상)에있는 pi를 지나는 선을 기준으로 볼 때, . 두 번째 요점은 수직선을 사용할 수있는 것처럼 보입니다 (가장 왼쪽 또는 가장 오른쪽 점으로 시작하는 경우). 그 후 가장 최근의 두 지점을 통해 선을 사용할 수 있습니다.