작은 포인트 바운딩 박스로 3D 포인트 클라우드를 분할하십시오.

Question

저는 C# WPF로 작업하고 있습니다.

문제가 해결 될 때까지 알고리즘을 찾고 있습니다. 아마도 그렇게 사소하지 않고 3D 그래픽이 될 것입니다.

3D 공간에서 2D 표면을가집니다 (점 구름으로 표현할 수도 있음).

이 표면을 특정 상자 (예 : 300 x 300 x 15)에 맞아야하는 더 작은 비트로 분할해야합니다.

최소 볼륨 경계 상자와 같이 축이 정렬되지 않지만 특정 볼륨보다 큰 상자를 작은 상자로 분할하는 알고리즘으로 3d에서 작동하는 알고리즘을 찾고 있습니다.

OBB의 최적화 문제와 많은 반복이 의심 스럽지만이 문제를 해결할 방법이 없습니다.

그림은 조금 문제를 설명합니다. 빨간색과 검정색 상자는 축 정렬을 강요받지 않으며 < 또는 = 최대 상자 크기 (크기 및 볼륨이 아님) 여야합니다.

는 귀하의 지원에 대한 여러분 모두 감사합니다!

Answer 1

디스크로 모양을 덮을 경우 문제가 NP 하드로 알려져 있습니다. f.e. https://en.wikipedia.org/wiki/Geometric_set_cover_problem. 나는 세트 커버 문제에 대한 당신의 주장이 더 나은 것이 아니라는 것을 강하게 믿습니다. 따라서 선형 또는 다항 시간으로 작업하는 대략 정확한 알고리즘에 의존해야합니다. 솔루션에서 희생 할 수있는 조건에 따라 알려진 솔루션을 사용하여 완전히 다른 작업에 도달 할 수 있습니다. 그래서 당신이 어떻게이 과제에 임했는지 설명하고 해결하고자하는 실제 과제가 무엇인지에 대해 설명하면 대략적인 해결책이 귀하의 경우에 충분한 지 토론 할 수 있습니다.

예를 들어, 차선의 크기와 방향을 가진 지향 상자로 포인트 세트를 차선 최적화 (하지만 충분히 좋음)하는 것이 좋을 경우 (그러나 충분히 좋음) 다음과 같이 빠른 생성 알고리즘을 사용할 수 있습니다 (fe https://en.wikipedia.org/wiki/%CE%95-net_(computational_geometry) 및 https://en.wikipedia.org/wiki/Delone_set 참조) 및/또는 각 하위 집합에 대해 충분히 지향 된 경계 상자의 탐욕적인 근사로 부분 집합으로 점 집합을 세분하는 욕심을 피할 수 있습니다.

또한 실제로 나 자신을 실제로 사용하지는 않았지만 솔루션에 대한 제약 조건을 아는 작업의 대략적인 솔루션을 생각해야한다면 프레임 워크 접근 방식으로 사용되어야한다고 생각하는 https://arxiv.org/abs/1409.7425과 함께 생각할 것입니다. 당신과 비슷한 작업 군에 대한 근사 해를 구하기 위해서. 보시다시피, 여러분에게 명시 적으로 유용한 것을 보시거나 어쩌면 솔루션을 사용할 준비가 된 구글에 유용한 단어를보실 수 있습니다.