항목 배치 알고리즘

Question

화면에 무작위로 배치 할 수있는 요소 (검정색) 위에 여러 툴팁 (주황색)이있는 "복잡한"문제가 있습니다. 툴팁은 요소 방향을 가리키는 네면 중 하나의 중간에 삼각형이있는 큰 사각형입니다. 기본적으로 삼각형은 요소의 가운데에 있지만 가까이있는 한 이동할 수 있으므로이 요소를 참조하는 것이고 다른 요소는 참조하지 않는다는 것을 쉽게 이해할 수 없습니다.

문제는 툴팁이 서로 겹치지 않아야하고 화면을 벗어날 수 없다는 것입니다.

Image of my tooltip problem

내가 먼저 기본 위치 (삼각형이 아래로 가리키는)에 모든 툴팁 배치에 대해 생각하고, 그들이 화면에서 또는 다른 하나를 겹치는 경우 다음 확인하고, 만약 그렇다면, 다른 위치를 시도합니다. 그러나이 기법 (아마도 가장 단순한 기법)을 사용하면 툴팁을 배치하고 나면 다른 배치가 적합하지 않을 경우 대체하지 않을 것이므로 너무 복잡한 배치가되므로 최상의 배치를 보장하지는 않습니다.

이 유형의 문제를 해결하는 방법에 대한 조언이나 아이디어가 있습니까?

감사합니다.

Answer 1

이것은지도 라벨링 문제의 인스턴스처럼 보입니다. 위키 백과는 an article about it입니다.

Answer 2

그래픽을 그리기 위해 algorithms에서 수행되는 것과 유사한 반발 성 전하의 일종의 물리적 시뮬레이션을 사용하여 모든 툴팁을 배치 할 수 있습니다. 모든 툴팁 사이의 강한 반발력을 시뮬레이트하고 툴팁과 이미지의 가장자리 사이에서 강력한 반발력을 시뮬레이트하면서 각 툴팁을 부드러운 스프링이 달린 객체로 블랙 박스에 모델링 할 수 있습니다. 모든 위치가 수렴 될 때까지 모든 힘을 계산하고 툴팁을 반복적으로 이동합니다. 당신은 역 스퀘어 (inverse square), 역 큐브 (inverse cube) 등으로 힘 스케일을 만들어서 좋은 결과를 얻을 수 있습니다.

구현하는 데 다소 어려움이있을 수 있지만 간단한 경우에는 적절한 결과를 제공해야합니다. 너무 많은 툴팁을 추가하면 이미지가 꽉 차게되므로 좋은 해결책이 항상 존재한다는 것을 보장하는 것은 불가능할 것입니다.