스케일링 임의의 방향 및 치수가 지정된 3D 상자 교차없는 힘을위한

Question

임의의 치수, 변환 및 회전이있는 3D 상자 세트가 있습니다. 3 차원 구성 요소에 대해 하나의 상수로 상자를 확장하여 상자를 교차하지 않게해야합니다.

현재 교차점을 확인하고 교차가 없을 때까지 반복적으로 비율을 줄임으로써이 작업을 반복적으로 수행하고 있습니다. 그러나 이것은 실행하기에는 너무 오래 걸리고 많은 시간을 할애해야합니다.

아무도 단일 히트에서 필요한 크기 조정을 찾는 방법을 알고 있지 않습니다. 대략적인 솔루션을 가장 환영합니다.

많은 분들께 감사드립니다.

Rob.

Answer 1

사용자가 이용할 수있는 상자에 대한 추가 정보가없는 경우 검색을 수행해야합니다. 그러나 일반적으로 선형 검색을 사용하는 것보다 신속하게 수용 가능한 답변에 가까워 지도록 검색을 이진화 할 수 있습니다.

이렇게하려면 허용 오차 & 만족스럽고 다음과 같은 것을 사용하세요.

lower_bound <- 0 
upper_bound <- 1 

while (scaling with upper_bound results in no collisions) 
    lower_bound <- upper_bound 
    upper_bound <- 2 * upper_bound 

while (|upper_bound - lower_bound| > ε) 
    mid_point <- (upper_bound + lower_bound)/2 
    if (scaling with mid_point results in collisions) 
     upper_bound <- mid_point 
    else 
     lower_bound <- mid_point 

returnlower_bound