무작위로 링크 된 임의의 점 집합이 주어지면 링크 선이 교차하지 않도록 위치를 지정하는 방법은 무엇입니까?

Question

포인트 세트가 있습니다. 좌표는 미리 결정되지 않았으므로이를 만들 때 설정할 수 있지만 링크는 미리 결정됩니다. 점에는 하나 이상의 링크가있을 수 있지만 0은 아닙니다.

나는 이들 사이의 링크 선이 교차하지 않는 위치에서 이러한 점을 시각적으로 표현할 수 있기를 원합니다. 지금까지 연구 한 내용에서 평면 그래프와 다소 유사하지만 단 하나의 링크 만있는 점이 있으며 평면 그래프가이를 나타낼 수 있는지는 잘 모르겠습니다.

내가하고 싶은 일을하는 좋은 방법이 있는지 확실하지 않지만 수학이 내 강점이 아니라는 것을 인정합니다. 지금까지의 나의 '가장 좋은'생각은 어떻게 든이 교차점을 감지하고 그 교차점을 어떻게해서 든 교차 위치를 고려하여 특정 교차점이 발생하지 않도록 다시 배치하는 방향으로 점을 이동시키는 것입니다. 교차로가 더 이상 발견되지 않을 때까지 모든 포인트. 그러나 내가 대신 사용할 수있는 좀 더 효율적인 수학적 알고리즘이있을 수 있습니다.

효율적이든 아니든 여기 모든 조언에 관심이 있습니다.

Answer 1

쉬운 문제는 아닙니다. 다음은 Google search results for “algorithm to draw a planar graph”입니다. Boost C++ 라이브러리는 some support for drawing planar embeddings (an example 포함)입니다. 물론 C++을 사용하고 문제를 태그 한 C#을 사용하지 마십시오.