[algorithm] 선체 자체를 계산하지 않고 점 집합에 대한 convex hull 내부에 점이 있는지 확인합니다.



2 Answers

점은 다른 점의 볼록 선체 외곽에 있으며 그 점에서 다른 점까지의 모든 벡터의 방향이 원 / 구 / 초원의 절반보다 작은 경우에만 해당됩니다.

Question

점 P가 점 X로 구성된 볼록 선체 내부에 있는지 테스트하는 가장 간단한 방법은 무엇입니까?

볼록 선체 자체를 명시 적으로 계산하지 않는 고차원 공간 (40 차원까지)에서 작동하는 알고리즘을 원합니다. 어떤 아이디어?




나는 16 차원에서 같은 문제를 겪었다. 너무 많은 얼굴을 생성해야했기 때문에 qhull도 제대로 작동하지 않았기 때문에 필자는 새로운 초 점과 참조 데이터 사이에 분리 초평면을 찾을 수 있는지 테스트하여 직접 접근 방식을 개발했습니다 (이를 "HyperHull"이라고 함)) .

분리 초평면을 찾는 문제는 볼록 이차 프로그래밍 문제로 변형 될 수 있습니다 ( SVM 참조). 나는 파이썬에서 cvxopt를 사용하여 170 줄 이하의 코드 (I / O 포함)를 사용했다. 이 알고리즘은 문제가 존재하더라도 모든 차원에서 수정없이 작동하며, 선체의 점 수를 높이는 차원이 높습니다 ( 폴리 토프의 임의 점의 볼록 선체 참조). 선체가 명시 적으로 구성되지는 않았으므로 점만 내부에 있는지 여부에 관계없이 알고리즘은 빠른 선체와 비교하여 더 높은 차원에서 매우 큰 이점을 갖습니다.

이 알고리즘은 '자연스럽게'병렬화 될 수 있으며 속도는 프로세서 수와 같아야합니다.




원래 게시물은 3 년 전 이었지만 아마도이 답변은 도움이 될 것입니다. Gilbert-Johnson-Keerthi (GJK) 알고리즘은 두 볼록 다각형 사이의 최단 거리를 찾습니다. 각 꼭지점은 생성기 집합의 볼록한 선체로 정의됩니다. 볼록 선체 자체는 계산할 필요가 없습니다. 특수한 경우에 대해 질문하는 경우가 있는데, 폴리토프 중 하나는 하나의 요점에 불과합니다. 왜 GJK 알고리즘을 사용하여 P와 점 X의 볼록 선체 사이의 거리를 계산해 볼까요? 그 거리가 0이면 P는 X 내부 (또는 적어도 경계에 있음)입니다. 지원 코드와 함께 ClosestPointInConvexPolytopeGJK.m이라는 Octave / Matlab의 GJK 구현은 http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.html 에서 제공됩니다. GJK 알고리즘에 대한 간단한 설명은 Sect. 2, http://www.99main.com/~centore/CourourSciencePapers/GJKinConstrainedLeastSquares.pdf . 저는 31 차원 공간에서 매우 작은 세트 X에 대해 GJK 알고리즘을 사용했으며 좋은 결과를 얻었습니다. GJK의 성능이 다른 사람들이 추천하는 선형 프로그래밍 방법과 비교하면 (어떤 비교가 흥미로울지라도) 불확실하다. GJK 방법은 볼록 선체를 계산하거나 선형 불평등의 관점에서 선체를 표현하는 것을 피하는데, 둘 다 시간 소모적 일 수 있습니다. 희망이 답변은 도움이됩니다.



Related