3D 볼록 다각형 사이의 거리

Question

두 개의 볼록 다각형이 3D에 있습니다. 그것들은 서로 다른 비행기에서 평평하기 때문에 한 쌍의 얼굴입니다.

두 폴리곤 간의 가장 가까운 거리를 계산하는 가장 간단한 방법은 무엇입니까?

편집 : 첫 번째 다각형에 끝 점이 있고 두 번째 다각형에 다른 끝점이있는 가능한 가장 짧은 줄의 길이입니다. 찾고있는 거리는이 가능한 가장 짧은 선의 길이입니다.

Answer 1

이것은 선형 제약 조건과 2 차 목표 함수를 사용하는 간단한 경계 최적화입니다. 그라디언트 디센트와 같이 사용할 수있는 알고리즘이 많이 있습니다.

Answer 2

첫 번째 객체의 모든 꼭지점을 반복 한 다음 해당 루프에서 두 번째 객체의 모든 꼭지점을 반복합니다. 가장 안쪽 루프에서 두 개의 현재 정점 사이의 거리를 비교하고 가장 낮은 거리를 저장합니다. 나는 항상 이렇게 이런 식으로하고 당신이 엄청나게 큰 메쉬를 가지고 있지 않는 한, 그것은 거의 즉각적입니다.

Answer 3

당신이 시도한 것이 분명하지 않습니다.

This 그 자체가 세그먼트로 보입니다.

그러면 모든 가장자리 쌍을 확인하면됩니다. 최적화를 시도하기 전에 먼저 구현하려고합니다.

한 중심에서 다른 중심으로 벡터를 고려하고 그 방향으로 어떤 의미의 가장자리 만 고려하면 최적화가 될 수 있습니다.

Answer 4

음, 몇 가지 가능성이 있습니다. 두 개의 다각형 사이의 짧은 선은 같을 수

1. 둘 사이 정점 에지와 두 개의 에지 정점 사이
2. (두 직교 평면상의 폴리곤 상상) 사이 정점
3. 사이
4. 다각형의 내부는
5. 또는 다각형

케이스를 교차 s 1-3은 모두 각 모서리 + 정점 - 쌍을 선분으로 처리하고 distance between all line-segment pairs을 열거하여 처리됩니다.

사례 4의 경우 distance between each vertex and the other polygon's plane을 찾으십시오. 정점에서 평면의 가장 가까운 점까지의 선이 다른 다각형 안에 있는지 확인합니다. 그렇지 않은 경우, 다음 다른 폴리곤에 최단 선이 이미 경우 1
2에 신세를 진 그 주변에있을 것입니다

(모두 다각형 위해이 검사를 할 수 있는지 확인)

사례 5의 경우 적어도 하나의 선분이 다른 다각형의 영역과 교차해야합니다. 둘레가 교차하는 경우 사례 1-3에서 이미 파악했을 것입니다. 정점이 영역을 교차하면 경우 4에서 잡았습니다. intersection of each edge with the other polygon's plane을 확인하고 교차점이 다른 다각형 안에 있는지 확인하십시오.
(모두 폴리곤이 검사를 할 수 있는지 확인)

이 모든에있는 최소 거리를 가지고, 우리가 완료됩니다.

Answer 5

이 스레드에서 제안한 대부분의 사람들은 "하나의 다각형의 모든 점/가장자리를 가져 와서 다른 점/가장자리와 비교"합니다. 만약 당신이하는 일이 상당히 간단한 두개의 폴리곤을 비교하고, 그렇게 빨리 할 필요가 없다면 아마 잘 될 것입니다.

그러나 비교적 쉽고 간편한 방법을 원한다면. Ben Voigt가 제안한대로 2 차 최적화 방법 (즉, Quadratic Programming)을 사용합니다. 기본적으로 다각형은 선형 제한 조건 세트입니다. 즉, 솔루션 포인트가 다각형의 모든 가장자리의 안쪽을 향해야합니다 (즉, 부등식 제약 조건). 그리고 최적화 할 비용 함수는 유클리드 거리에 불과합니다. 즉, 표준 공식의 Q는 단위 행렬입니다. 일단 이런 문제로 던지면, 이것을 해결하는 라이브러리를 사용할 수 있습니다 (많은 라이브러리가 있습니다). 또는 책에서 그것을 공부하고 자신의 코드를 롤 할 수 있습니다 (코드 작성이 매우 쉬운 알고리즘입니다).).

간단한 다각형 - 다각형 테스트가 더 복잡한 3D 모양 (예 : 다각형으로 된 단색)을 향한 첫 번째 단계 인 경우이를 수행하는 실제 방법이 필요한 경우. 그런 다음, 이미 그렇게하는 패키지를 사용해야합니다. Here은 많은 충돌 침투 깊이 또는 이와 동등하게 최소 거리를 나타내는 충돌 감지 라이브러리 세트입니다.