대략 구형이어야하는 도형의 서페이스를 묘사하는 점들의 모음이 있습니다.이 점 내에 다른 점이 있는지를 결정하는 방법이 필요합니다. 나는 이전에 정확한 구체로 형상을 근사해 왔지만, 이것은 너무 부정확 한 것으로 입증되었으며보다 정확한 방법이 필요합니다. 단순성과 속도는 완전한 정확도보다 유리하며, 좋은 근사법으로 충분합니다.포인트가 3 차원 모양 안에 있고 그 표면이 점군으로 정의 된 경우 어떻게 테스트 할 수 있습니까?
포인트 클라우드를 3D 메쉬로 변환하는 기술을 접했지만, 내가 찾은 대부분의 것들은 매우 복잡하고 가능한 한 단순한 것을 찾고 있습니다.
아이디어가 있으십니까?
구름의 중심을 계산하고 그 중심을 원점이 중심이되는 극좌표 시스템으로 변환하면 어떨까요?
그런 다음 검사 할 점을 동일한 좌표계로 변환하십시오.
Delaunay 삼각 측량으로 표면을 표현할 수 있다고 가정 할 때, 조사하는 지점과 각도가 가장 작은 세 점을 결정하십시오.
세 점으로 결정된 삼각형에 조사 할 점을 투영하고 중심점에서 투영 된 점의 거리가 실제 점의 거리보다 큰지 확인합니다.
본질적으로 볼록 선체의 삼각형 메쉬를 구성하고 있지만 한 번에 하나의 삼각형을 필요에 따라 구성해야합니다. 실행 속도가 중요한 경우, 이동하면서 생성 된 삼각형을 캐시 할 수 있습니다.
스티븐 수드 티 (Steven Sudit)는 a useful optimization도 추천합니다.이 경로를 사용하면 좋습니다.
이것은 좋은 생각인데, 많은 감사합니다! 나는 그것을 지금 시도하고 그것이 효과가 있는지 보게 될 것이다. 이미 다른 알고리즘의 최적화를 위해 각 점의 인접 점 목록이 있습니다.이 알고리즘을 사용하면 속도를 높이기 위해 재활용 할 수도 있습니다. – Ben
나는 그것에 대해 약간 생각하고 나는 3 명이 항상 충분해야한다고 생각합니다. 이것은 표면이 삼각형의 관점에서 정의 될 수 있다는 생각에 기반합니다. 점이 중심에 더 가까운 삼각형 평면의 한면에 있으면 한도 내에 있습니다. 물론,이 가정이 틀린 경우 - 빈 공간과 오버행이있을 수있는 경우 -이 중 어느 것도 유지되지 않습니다. 그렇다면 다시, 나는 무엇을하는지 모른다. 더 많은 포인트를 추가하는 것만으로는 충분하지 않습니다. –
또는 올바른 용어로 Delaunay 삼각형으로 정의 할 수있는 볼록 선체라고 가정합니다. –
Bill Carey의 방법이 올바른 방향이라고 생각하지만 가능한 최적화를 제안하고 싶습니다.
모양이 대략 구형이기 때문에 구형의 구형과 구형의 구의 반지름을 미리 계산할 수 있습니다. 이렇게하면 점의 거리가 더 작은 구체 안에 있으면 명확한 히트이며 외부의 영역 밖에 있다면 명확한 실수입니다.
이렇게하면 쉬운 문제를 매우 신속하게 해결할 수 있습니다. 더 힘든 사람들을 위해, Carey의 방법이 필요합니다.
확실히 좋은 최적화입니다. 이 답변에 기여한 참조를 추가 할 수 있습니까? –
@Bill, 방금 한 것 같아. :) –
@Bill : 각 답변의 왼쪽 하단에있는 "링크"링크를 참조하십시오. 마크 업 또는 html을 사용하여 "See Steven 's nice optimization"을 만들 수 있습니다. 게시물에 링크 유형 ... 그게 내가 평소에 이런 일들을 관리하는 방법입니다. – dmckee
kd-tree는 가장 가까운 세 점을 찾는 부분과 관련이 있습니다. Ben이이 작업을 수행하는 다른 방법이있는 것 같습니다. –
극좌표 시스템에서 kd 트리를 만들 수 있습니까? 나는 그들과 충분히 알고 지내지 못했다. 그렇다면 유용 할 수 있습니다. –
@Bill : 제가 아는 한, kd- 나무는 데카르트 좌표를 나타냅니다. 그렇다면 항상 변환 할 수 있습니다. 그렇지 않다면, 나는 그들이 혼합 된 단위 (각도 대 거리)의 문제를 어떻게 다루는 지 궁금 할 것이다. –
클라우드가 수정 되었습니까? 표면이 볼록합니까? 포인트 테스트를 얼마나 자주해야합니까? –
클라우드는 '장기간'으로 고정되어 있지 않지만 시스템의 '스냅 샷'에서 수행되므로 이러한 계산의 목적으로 사용됩니다. 게임처럼 실시간으로 실행할 필요가 없습니다. 테스트는 약 2 초마다 한 번 수행됩니다. – Ben